java - Data Structures -

-

i coding program going compute number of inversions in array. requirement use divide-and-conquer algorithm. have used merge sort afterwards stuck. need create method called count in order count inversions using recursion. here need help... thank in advance

    import java.util.*;  public class inversions {     public static void main(string[] args)     {         integer[] = {2, 6, 3, 5, 1};         mergesort(a);         system.out.println(arrays.tostring(a));     }      public static void mergesort(comparable [ ] a)     {         comparable[] tmp = new comparable[a.length];         mergesort(a, tmp,  0,  a.length - 1);     }       private static void mergesort(comparable [ ] a, comparable [ ] tmp, int left, int right)     {         if( left < right )         {             int center = (left + right) / 2;             mergesort(a, tmp, left, center);             mergesort(a, tmp, center + 1, right);             merge(a, tmp, left, center + 1, right);         }     }       private static void merge(comparable[ ] a, comparable[ ] tmp, int left, int right, int rightend )     {         int leftend = right - 1;         int k = left;         int num = rightend - left + 1;          while(left <= leftend && right <= rightend)             if(a[left].compareto(a[right]) <= 0)                 tmp[k++] = a[left++];             else                 tmp[k++] = a[right++];          while(left <= leftend)    // copy rest of first half             tmp[k++] = a[left++];          while(right <= rightend)  // copy rest of right half             tmp[k++] = a[right++];          // copy tmp         for(int = 0; < num; i++, rightend--)             a[rightend] = tmp[rightend];     }     public int count(int[] a, int n){}  }

added changes in code.

import java.util.*;  public class inversions {     public static int countinversions = 0;     public static void main(string[] args)     {         integer[] = {2, 6, 3, 5, 1};         mergesort(a);         system.out.println(arrays.tostring(a));         system.out.println(countinversions);     }      public static void mergesort(comparable [ ] a)     {         comparable[] tmp = new comparable[a.length];         mergesort(a, tmp,  0,  a.length - 1);     }       private static void mergesort(comparable [ ] a, comparable [ ] tmp, int left, int right)     {         if( left < right )         {             int center = (left + right) / 2;             mergesort(a, tmp, left, center);             mergesort(a, tmp, center + 1, right);             merge(a, tmp, left, center + 1, right);         }     }       private static void merge(comparable[ ] a, comparable[ ] tmp, int left, int right, int rightend )     {         int leftend = right - 1;         int k = left;         int num = rightend - left + 1;          while(left <= leftend && right <= rightend)             if(a[left].compareto(a[right]) <= 0)                 tmp[k++] = a[left++];             else {                 countinversions+=((leftend-left)+1); // counts inversions                 tmp[k++] = a[right++];             }          while(left <= leftend)    // copy rest of first half             tmp[k++] = a[left++];          while(right <= rightend)  // copy rest of right half             tmp[k++] = a[right++];          // copy tmp         for(int = 0; < num; i++, rightend--)             a[rightend] = tmp[rightend];     } }

in above code, counting inversions when 2 arrays merging. example 1st sub-array contains [1, 6] , 2nd sub-array has [2, 3]. when these merged inversion count 2 i.e. [6>2] & [6>3]. when condition comes a[left] > a[right] count number of elements remaining on right sub-array because less a[left] , add them countinversions.


Comments

Post a Comment

Popular posts from this blog

java - Run spring boot application error: Cannot instantiate interface org.springframework.context.ApplicationListener -

-
i have spring project , try make use spring boot , run @ embadded tomcat following : https://spring.io/guides/gs/rest-service/ this application //@configuration //@enableaspectjautoproxy @springbootapplication @componentscan(basepackages = "gux.prome") public class application { public static void main(string[] args) { springapplication.run(application.class, args); } } if use maven command: mvn spring-boot:run , project starts fine, need debug , run main method @ intelij, exception occurs: exception in thread "main" java.lang.illegalargumentexception: cannot instantiate interface org.springframework.context.applicationlistener : org.springframework.boot.logging.classpathloggingapplicationlistener @ org.springframework.boot.springapplication.createspringfactoriesinstances(springapplication.java:414) @ org.springframework.boot.springapplication.getspringfactoriesinstances(springapplication.java:394) @ org.springframework.bo...
Read more

reactjs - React router and this.props.children - how to pass state to this.props.children -

-
i'm using react-router first time , don't know how think in yet. here's how i'm loading components in nested routes. entry point .js reactdom.render( <router history={hashhistory} > <route path="/" component={app}> <route path="models" component={content}> </route> </router>, document.getelementbyid('app') ); app.js render: function() { return ( <div> <header /> {this.props.children} </div> ); } so child of app content component sent in. i'm using flux , app.js has state , listens changes, don't know how pass state down this.props.children. before using react-router app.js defines children explicitly, passing state natural don't see how now. using couple of react helper methods can add state, props , whatever else this.props.children render: function() { var children = react.ch...
Read more

Excel VBA "Microsoft Windows Common Controls 6.0 (SP6)" Location Changes -

-
i have excel workbook used generate quotations customers. there main page user inputs data, , there buttons generate various pdfs , send them customer. however, 1 user consistently getting error preventing generating , sending pdfs. i beleive "microsoft windows common controls 6.0 (sp6)". it's installed on users' computers. on mine, location "c:\windows\syswow64\mscomctl.ocx" on others "c:\windows\system32\mscomctl.ocx" the user experiencing issues on 32-bit machine, "mscomctl.ocx" file should in system32. have manually put in there, , pointed common controls reference in vba it. issue seems keep reverting looking in syswow64. since folder doesn't exist, can't find it, , can't produce pdfs. i thought perhaps issue user running older version of office (2007) there users on 2013 , 2016. thought perhaps mixture of 64-bit , 32-bit users. user gets sent workbook other users (as quotation process goes further, gets passed ...
Read more