Brandacus - 10 months ago 84

Java Question

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 Source

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)];
```