Brandacus Brandacus - 2 months ago 15
Java Question

Why is my Java Quicksort not porting into Javascript?

I have quicksort implemented in Java, but when I ported it over to JS, it isn't sorted correctly. What gives??

Test case: {5,86,69,73,11,17,5,86,1,74,34,3,1000,1}

After sorting

Java: 1 1 3 5 5 11 17 34 69 73 74 86 86 1000

JS: 1 3 1 34 86 74 1000 5 5 11 69 17 73 86

Java Code

public class QuickSort {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
//int[] newArray = Arrays.copyOfRange(oldArray, startIndex, endIndex);
int[] arr = new int[]{5,86,69,73,11,17,5,86,1,74,34,3, 1000, 1};

quickSort(arr, 0, arr.length - 1);

for(int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}

private static void quickSort(int[] arr, int lowerIndex, int higherIndex) {

int i = lowerIndex;
int j = higherIndex;
// calculate pivot number, I am taking pivot as middle index number
int pivot = arr[lowerIndex+(higherIndex-lowerIndex)/2];
// Divide into two arrays
while (i <= j) {
/**
* In each iteration, we will identify a number from left side which
* is greater then the pivot value, and also we will identify a number
* from right side which is less then the pivot value. Once the search
* is done, then we exchange both numbers.
*/
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
swap(arr, i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if (lowerIndex < j)
quickSort(arr, lowerIndex, j);
if (i < higherIndex)
quickSort(arr, i, higherIndex);
}

private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}

}


JS Code

var arr = [5,86,69,73,11,17,5,86,1,74,34,3,1000,1];

quickSort(arr, 0, arr.length - 1);

function quickSort(arr, lowerIndex, higherIndex) {
var i = lowerIndex;
var j = higherIndex;
var pivot = arr[lowerIndex + (higherIndex - lowerIndex)/2];

while(i <= j) {
while(arr[i] < pivot) {
i++;
}

while(arr[j] > pivot) {
j--;
}

if(i <= j) {
swap(arr, i, j);
i++;
j--;
}
}

if(lowerIndex < j)
quickSort(arr, lowerIndex, j);

if(i < higherIndex)
quickSort(arr, i, higherIndex);

}

function swap(arr, i, j) {
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}


JSFiddle: https://jsfiddle.net/a4oLk4hc/

Answer

I have updated your fiddle here, which should now be working for you. The problem with your port was this line:

var pivot = arr[lowerIndex + (higherIndex - lowerIndex)/2];

This is because in javascript dividing by two might result in a decimal of 0.5. In order to fix this problem use Math.floor() to ensure the value is rounded correctly. For example:

var pivot = arr[Math.floor(lowerIndex + (higherIndex - lowerIndex) / 2)];