java - Merge sort wrong output -
i'm having 2 problems merge sort code in java.
when input array [3,4,2,1,0,6,8], i'm getting output [0, 1, 2, 3, 4, 6, 0], wrong.
i suspect way have written code not optimal be. please let me know if can find improvements. know there tons of mergesort algorithms on web, i'm asking way i've written code. thanks!
import java.util.arrays; public class main { static int[] mergesort(int[] arr) { if (arr == null) return null; if (arr.length <= 1) return arr; int length = arr.length; int mid = arr.length / 2; int[] left = arrays.copyofrange(arr, 0, mid); int[] right = arrays.copyofrange(arr, mid, length); int[] sortedleft = mergesort(left); int[] sortedright = mergesort(right); int leftsmallestindex = 0; int rightsmallestindex = 0; int leftlength = left.length; int rightlength = right.length; int[] sortedarr = new int[length]; outer: (int = 0; < length; i++) { if (leftsmallestindex >= leftlength) { while (rightsmallestindex < rightlength) { sortedarr[i] = sortedright[rightsmallestindex]; rightsmallestindex++; break outer; } } if (rightsmallestindex >= rightlength) { while (leftsmallestindex < leftlength) { sortedarr[i] = sortedleft[leftsmallestindex]; leftsmallestindex++; break outer; } } if (sortedleft[leftsmallestindex] < sortedright[rightsmallestindex]) { sortedarr[i] = sortedleft[leftsmallestindex]; leftsmallestindex++; } else { sortedarr[i] = sortedright[rightsmallestindex]; rightsmallestindex++; } } return sortedarr; } public static void main(string[] args) { // write code here int[] = new int[] {3,4,2,1,0,6,8}; system.out.println(arrays.tostring(mergesort(a))); } }
your statement break outer; causing control go out of loop , not continue loop (i guessing trying continue loop, using break outer; statement).
this causes loop update 1 remaining element sortedright or sortedleft sorted array , others missed, causing 0 @ end of loop.
you not need this, can loop till - leftsmallestindex < leftlength && rightsmallestindex < rightlength , while loops defined inside loop, outside it.
example -
import java.util.*; import java.math.*; class { static int[] mergesort(int[] arr) { if (arr == null) return null; if (arr.length <= 1) return arr; int length = arr.length; int mid = length / 2; int[] left = arrays.copyofrange(arr, 0, mid); int[] right = arrays.copyofrange(arr, mid, length); int[] sortedleft = mergesort(left); int[] sortedright = mergesort(right); int leftsmallestindex = 0; int rightsmallestindex = 0; int leftlength = left.length; int rightlength = right.length; int[] sortedarr = new int[length]; int = 0; (; leftsmallestindex < leftlength && rightsmallestindex < rightlength;i++) { if (sortedleft[leftsmallestindex] < sortedright[rightsmallestindex]) { sortedarr[i] = sortedleft[leftsmallestindex]; leftsmallestindex++; } else { sortedarr[i] = sortedright[rightsmallestindex]; rightsmallestindex++; } } while (rightsmallestindex < rightlength) { sortedarr[i] = sortedright[rightsmallestindex]; rightsmallestindex++; i++; } while (leftsmallestindex < leftlength) { sortedarr[i] = sortedleft[leftsmallestindex]; leftsmallestindex++; i++; } return sortedarr; } public static void main(string[] args) { int[] = new int[] {3,4,2,1,0,6,8}; system.out.println(arrays.tostring(mergesort(a))); outer : for(int = 0;i < 10 ; i++) { while(true) { system.out.println(i); break outer; } } } } at end, added example (a simple version of trying using break outer; should understand happenning) .
Comments
Post a Comment