mergesort - Merge Sort Iterative Implementation - Not working -

-

i have below merge sort iterative implementation, somehow, not working. debugged it, couldn't find cause.

merge'ing function remain same recursive case, array dividing logic different, if i'm correct.

please rectify, if i'm going in wrong direction.

i think have problem when try use same object represent different intervals: @ mergesort_iterative loop , when adding new elements list1 using "info" object temporal variable , add list1 collection.

in java, object variables references when add object collection not adding copy of reference being modified , inserted again.

info.left = left; info.right = mid; list1.add(info);  info.left = mid + 1; info.right = right; list1.add(info);

to fix should create 2 objects in order 2 perform inserctions:

info = new mergeposinfo(); info.left = left; info.right = mid; list1.add(info);  info = new mergeposinfo(); info.left = mid + 1; info.right = right; list1.add(info);

on other hand, once problem described above solved, should iterate on list2 shorter wider intervals , left right positions , algorithm not generating list2 in order.

you need modify mergesort_iterative:

public static void mergesort_iterative(int[] numbers, int left, int right) {     int mid;     if (right <= left)         return;      linkedlist<mergeposinfo> list1 = new linkedlist<mergeposinfo>();     linkedlist<mergeposinfo> list2 = new linkedlist<mergeposinfo>();      for(int = left; <= right; i+=2)     {         mergeposinfo info = new mergeposinfo();         info.left = i;         info.right = (i+1<=right)?(i+1):i;         info.mid = -1;         list1.add(info);         list2.add(info);     }      int l = right-left+1;     for(int partssize = 2; partssize <= l/2; partssize*=2)     {         int ll1 =    list1.size();         for(int = 0; < ll1; i+=2)         {             mergeposinfo info2 = new mergeposinfo();             info2.left = list1.get(0).left;             info2.right = list1.get(1).right;             info2.mid = (info2.left+info2.right)/2;              list1.remove(0);             list1.remove(0);              list1.add(info2);             list2.addlast(info2);         }     }       (int = 0; < list2.size(); i++) {         system.out.println("merge [" + integer.tostring(list2.get(i).left) + " , "  + integer.tostring(list2.get(i).right) + "]" );         domerge(numbers, list2.get(i).left, list2.get(i).mid+1,                 list2.get(i).right);     }  }

as add lines domerge:

public static void domerge(int[] numbers, int left, int mid, int right) {        int[] temp = new int[25];        int i, left_end, num_elements, tmp_pos;         left_end = (mid - 1);        tmp_pos = left;        num_elements = (right - left + 1);         if(num_elements == 2)        {            if(numbers[left]>numbers[right])            {                int buffer = numbers[left];                numbers[left] = numbers[right];                numbers[right] = buffer;            }            return;         }        ...

as can see solution provided works when "numbers" length 2^k. can try fix , if can't give last change.

i left system.out.println("merge [" + integer.tostring(list2.get(i).left) + " , " + integer.tostring(list2.get(i).right) + "]" );

line can understand how merge sort works.


Comments

Post a Comment

Popular posts from this blog

java - nested exception is org.hibernate.exception.SQLGrammarException: could not extract ResultSet Hibernate+SpringMVC -

-
i trying fetch records database , having above error this classs appropriate getters , setters public class user { private int id; private string username; private string password; private string email; i have create database , inserted data below configuration <bean id="datasource" class="org.apache.commons.dbcp2.basicdatasource" destroy-method="close"> <property name="driverclassname" value="com.mysql.jdbc.driver"/> <property name="url" value="jdbc:mysql://localhost:3306/usersdb"/> <property name="username" value="root"/> <property name="password" value=""/> </bean> this complete stacktrace severe: servlet.service() servlet [appservlet] in context path [/spring] threw exception [request processing failed; nested exception org.hibernate.exception.sqlgrammarexception: not ...
Read more

sql - Postgresql tables exists, but getting "relation does not exist" when querying -

-
Image
i have postgresql db number of tables. if query: select column_name information_schema.columns table_name="my_table"; i list of columns returned properly. however, when query: select * "my_table"; i error: (programmingerror) relation "my_table" not exist 'select *\n "my_table"\n' {} any thoughts on why can columns, can't query table? goal able query table. you have include schema if isnt public one select * <schema>."my_table" or can change default schema show search_path; set search_path my_schema; check table schema here select * information_schema.columns for example if table on default schema public both works ok select * parroquias_region select * public.parroquias_region but sectors need specify schema select * map_update.sectores_point
Read more

asp.net mvc - breakpoint on javascript in CSHTML? -

-
i have .cshtml file has javascript tag. within script tag have few lines of javascript. first line of javascript refers property in @viewbag. other javascript lines plain script without mvc related references. observation: can place breakpoints (visual studio 2015) on each of these javascript lines. however, breakpoints has white dot in center of breakpoint symbol (red circle) except line @viewbag reference (this particular line not have white dot in center). it seems breakpoint without white dot hit during run-time. question: can explain going on here? white dot mean? why plain red breakpoint line line hitting breakpoint? the visual studio debugger expecting debug actual server-side code within .cshtml file opposed client-side javascript within it. iirc, visual studio allow debug javascript code expected in internet explorer (and possibly edge), other browsers want use either third-party tool or developer tools (f12) within browser. an easy approach take advant...
Read more