Xuzheng Wang
Xuzheng Wang

Reputation: 531

Quicksort in JavaScript and Java

I just found a strange problem. I tried to use JavaScript to implement a quicksort based on code written in Java, however, the result was not what I expected. Java code :

public class Sort {
    public static void main (String[] args){
        int[] number = {1,10,2,2,2,3,5,7,8,2};
        for (int i = 0; i < number.length ; i++) {
            System.out.println(quickSort(number)[i]);//1,2,2,2,2,3,5,7,8,10
        }
    }
    static int[] quickSort(int[] number){
        int length = number.length;
        int start = 0;
        int end = length -1;
        number = quick_sort (start,end,number);
        return number;
    }
    private static int[] quick_sort(int start,int end,int[] number) {

        int pivot = number[(start+end)/2];
        int s = start;
        int e = end;
        while (s <= e) {
            while(number[s] < pivot) {
                s++;
            }
            while(number[e] > pivot) {
                e--;
            }
            //swap the value
            if (s <= e) {
                int temp = number[s];
                number[s] = number[e];
                number[e] = temp;
                //move both sides cursor
                s++;
                e--;
            }

        }

        // recursively sorting lower half
        if (start < e) {
            quick_sort(start, e, number);
        }
        //recursively sorting higher half
        if (end > s) {
            quick_sort(s, end, number);
        }
        return number;
    }
}

JavaScript :

function main() {
    var numbers  = [1,10,2,2,2,3,5,7,8,2];
    var length = numbers.length;
    var start = 0;
    var end = length - 1;
    alert(quickSort(start, end, numbers));//2,3,5,8,7,2,1,2,2,10  <----- not sorted
}

function quickSort(start, end, numbers) {
    var s,e,temp,pivot;
    s = start;
    e = end;
    pivot = numbers[(start+end)/2];
    while(s<=e){
        while(numbers[s] < pivot ) {
            s++;
        }
        while(numbers[e] > pivot) {
            e--;
        }
        if(s<=e) {
            temp = numbers[s];
            numbers[s] = numbers[e];
            numbers[e] = temp;
            e--;
            s++;
        }
    }
    if(start < e) {
        quickSort(start, e, numbers);
    }
    if(end > s) {
        quickSort(s, end, numbers);
    }
    return numbers;
}
main();

Code written in Java gives the result of 1,2,2,2,2,3,5,7,8,10, in the other hard, code written in JavaScript produces the result of 2,3,5,8,7,2,1,2,2,10, which is different from original array but still not sorted correctly. Any thoughts about this? Thanks in advance

Edit:

Thanks for the responses, I was looking into logic rather than basics.

Upvotes: 0

Views: 134

Answers (1)

Andy Turner
Andy Turner

Reputation: 140319

(start+end)/2 isn't necessarily an integer in JS. It works with Math.floor((start+end)/2).

Upvotes: 5

Related Questions