1

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/

0

2 Answers 2

3

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)];
Sign up to request clarification or add additional context in comments.

1 Comment

Thank you! I'm used to Java rounding ints, so I'll be more careful next time :)
2

JS varriable dont have clearly type so be careful, your problem here:

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

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.