49921

problems with merge sort in java

i'm brand new to stackoverflow and i need some help with writing a program to mergesort an arraylist of comparables. i have worked on this code for hours to no avail. the program needs to work correctly, because i am doing it for a computer science class, and the very next assignment requires us to test the efficiency of different sorts. here's the code:

Merge Method:

public static void merge(ArrayList <Comparable> a, int first, int mid, int last){ ArrayList <Comparable> b = new ArrayList(); for(int k = first; k <= last; k++){ b.add(a.get(k)); } System.out.println("b now contains " + b); int middle =b.size() /2; for(int i = first; i <= last; i++){ //System.out.println("mid: " + b.size() /2); //System.out.println("b: " + b); //System.out.println("a: " + a); //System.out.println("i: " + i); if(middle == b.size()){ a.set(i, b.remove(0)); middle--; }else if(middle == 0){ a.set(0, b.remove(0)); }else if(b.get(0).compareTo(b.get(middle)) < 0){ System.out.println("moving " + b.get(0) + " from b[0] to a[" + i + "] because " + b.get(0) + " is less than " + b.get(middle)); a.set(i, b.remove(0)); middle--; System.out.println("b now contains " + b); }else{ System.out.println("moving " + b.get(middle) + " from b[" + b.size() /2 + "] to a[" + i + "] because " + b.get(0) + " is greater than " + b.get(middle)); a.set(i, b.remove(middle)); //middle--; System.out.println("b now contains " + b); } } System.out.println(); System.out.println("Merge"); System.out.println(a); System.out.println(); }

Mergesort Method:

public static void mergeSort(ArrayList <Comparable> a, int first, int last){ if(first < last){ int mid = first + (last - first) /2; System.out.println("mergeSorting " + a.subList(first, last + 1)); mergeSort(a, first, mid); System.out.println("mergeSorting " + a.subList(first, mid + 1)); mergeSort(a, mid + 1, last); System.out.println("merging " + a.subList(first, mid + 1) + " and " + a.subList(mid + 1, last + 1)); merge(a, first, mid, last); } System.out.println(); System.out.println("base case"); System.out.println(); }

I think that there is a problem with the merge method, but i'm not sure.

my code seems to be sorting the list incorrectly, i.e:

Input: [7,1,9,9,5,4,8,9,10,4] Output: [4,8,9,4,10,10,5,9,9,7]

Answer1:

The mergeSort algorithm is ok. I just defined the type of ArrayList to avoid the warning

public static void mergeSort(ArrayList <Comparable> a, int first, int last){ if(first < last){ int mid = first + (last - first) /2; // System.out.println("mergeSorting " + a.subList(first, mid )); System.out.println("First"+first); System.out.println("Mid"+mid); System.out.println("Last"+last); System.out.println("MergeSortCall"); System.out.println("firstVector " + a.subList(first, mid+1)); System.out.println("secondVector " + a.subList(mid + 1,last+1)); mergeSort(a, first, mid); mergeSort(a, mid + 1, last); merge(a, first, mid, last); System.out.println("mergeVector " + a.subList(first,last+1)); } }

The second part is really difficult to know exactly what is wrong so I replaced it for something much simpler using basically your notation. Note that the second part is just a "merge" algorithm. It is supposed to be really simple. Anyway, using this you can compare with your results (sorry it is difficult to understanding the logic of the second part and this is your homework, isn't it?). I'm using two vectors to improve the readability, but only one as you did is necessary.

public static void merge(ArrayList <Comparable> a, int first, int mid, int last){ ArrayList <Comparable> vectorFirst = new ArrayList<Comparable>(); ArrayList <Comparable> vectorSecond = new ArrayList<Comparable>(); for(int k=first;k<=mid;k++){ vectorFirst.add(a.get(k)); } for(int k=mid+1;k<=last;k++){ vectorSecond.add(a.get(k)); } int i=first; int j=mid+1; int k=first-1; while((i<=mid)&(j<=last)){ if(vectorFirst.get(i-first).compareTo(vectorSecond.get(j-mid-1))==-1){ k=k+1; a.set(k,vectorFirst.get(i-first)); i=i+1; } else{ k=k+1; a.set(k,vectorSecond.get(j-mid-1)); j=j+1; } } if(i==mid+1){ while(j<=last){ k=k+1; a.set(k,vectorSecond.get(j-mid-1)); j=j+1; } } else{ while(i<=mid){ k=k+1; a.set(k,vectorFirst.get(i-first)); i=i+1; } } }

Recommend

  • How to add multiple columns in Apache Spark
  • sorting three number in a specific order
  • How to Count the Number of a Specific Character in a Cell with Excel VBA
  • Java Sort functions
  • How can we extract the main verb from a sentence?
  • How to apply async task into this
  • SQL - count occurrences of gender
  • Cannot invoke my method on the array type int[]
  • How to merge keras sequential models with same input?
  • hibernate sets dirty flag (and issues update) even though client did not change value
  • drawing random circles, storing their coorindates in an array
  • How can Delete be both a DDL and a DML statement
  • Primefaces ManyCheckbox inside ui:repeat calls setter method only for last loop
  • sending/ receiving email in Java
  • Trying to switch camera back to front but getting exception
  • Rearranging Cells in UITableView Bug & Saving Changes
  • How to delete a row from a dynamic generate table using jquery?
  • Proper way to use connect-multiparty with express.js?
  • Free memory of cv::Mat loaded using FileStorage API
  • How get height of the a view with gone visibility and height defined as wrap_content in xml?
  • JTable with a ScrollPane misbehaving
  • Angular 2 constructor injection vs direct access
  • FormattedException instead of throw new Exception(string.Format(…)) in .NET
  • unknown Exception android
  • Is there any way to bind data to data.frame by some index?
  • Checking variable from a different class in C#
  • Easiest way to encapsulate a HTML5 webpage into an android app?
  • Programmatically clearing map cache
  • Busy indicator not showing up in wpf window [duplicate]
  • Sorting a 2D array using the second column C++
  • costura.fody for a dll that references another dll
  • Observable and ngFor in Angular 2
  • How to Embed XSL into XML
  • failed to connect to specific WiFi in android programmatically
  • UserPrincipal.Current returns apppool on IIS
  • Conditional In-Line CSS for IE and Others?
  • java string with new operator and a literal
  • How can I use threading to 'tick' a timer to be accessed by other threads?
  • How do I use LINQ to get all the Items that have a particular SubItem?