same logic isn't working for doing quick sort in c and java-CodePudding

this is how i implemented the partition function in c

int partition(int arr[], int start, int end)
{
    int i = start;
    int j = end;

    int pivot = arr[i];

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

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

        if (i < j)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    int temp = arr[start];
    arr[start] = arr[j];
    arr[j] = temp;

    return j;
}

and it works for me the array gets sorted

i tried to do the same implementation but in java


    /**
     * Partition int.
     *
     * @param arr   the arr
     * @param start the start
     * @param end   the end
     * @return the int
     */
    public static int partition(int[] arr, int start, int end) {

        // array indexes
        int i = start; //0
        int j = end; // 0
        int pivot = arr[i];

        // 90 70 100 20 30 50 120
        while(i < j) {
            while (arr[i] < pivot){
                i  ;
            }

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

            if(i < j){
                // swap
                int temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
        int temp = arr[start];
        arr[start] = arr[j];
        arr[j] = temp;
        return j;
    }

but it doesn't work out it gives me java.lang.StackOverflowError this exception though my main and quickSort functions are the same in c and java

it only works in java if i deleted this part of the function

    int temp = arr[start];
    arr[start] = arr[j];
    arr[j] = temp;

so that my function in java looks like this

    public static int partition(int[] arr, int start, int end) {

        // array indexes
        int i = start; //0
        int j = end; // 0
        int pivot = arr[i];

        // 90 70 100 20 30 50 120
        while(i < j) {
            while (arr[i] < pivot){
                i  ;
            }

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

            if(i < j){
                // swap
                int temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
        return j;
    }

}

i'm asking why ? what is the difference to make the same logic isn't working for both java and c what is the reason for that please

CodePudding user response：

If I copy paste your code and use the extra code and the input 10, 5, 3, 7, 2 from the image, the code will throw and ArrayIndexOutOfBoundsException (not a java.lang.StackOverflowError)

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5

during the while check in the last line here

do {
    i  ;
} while(arr[i] <= pivot); // Index 5 out of bounds for length 5 happens here

This means that you algorithm is still wrong in the sense, that it does not check for array bounds correctly and runs out of bounds.

So why would that be different in Java than in C when same logic is used? That is because Java will throw an exception right away when an out of bounds access occurs, while C will allow that access and if you are lucky and you don't get a segfault, your code will just check the value at that out of bounds memory location. So the same bug exists in your C code, but luckily for this input it just happens to work, and it seems that it even swaps the last 2 values because of it and the result is actually right.

Long story short, Java is just more strict and thus generally safer to program in, and it has uncovered a bug in your quicksort implementation that C just ignored.

EDIT: It was suggested that you change do while loops to while loops. And my addition would be to also add bounds check So you get

    while (i < j) {
            while(i < arr.length - 1 && arr[i] <= pivot) {
                i  ;
            }

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

Then the output is correct for the input 10, 5, 3, 7, 2 (and for some other inputs that I tested), but now it actually starts throwing java.lang.StackOverflowError if you have more than one number with the same value in the array. For example for this input 3, 10, 5, 3, 7, 2. That means that in your quicksort implementation you do not account correctly for the possibility that 2 values (or more) might actually be the same in the array.

So my suggestion would be to debug your quicksort implementation in Java with the Debug option that all Java IDEs should have. Place some breakpoints and observe the values. Fix the code. Use also additional test cases, until you get it right (empty array, array with a single element, array with just two elements with the same value and so on).

CodePudding user response：

You need to remove the last swap at the end and use plain while loops.

Your C code doesn't partition correctly. Say, the array [2, 3, 4, 1] will not change after your C partitioning, but it should become [1, 2, 3, 4] (first everything smaller than the pivot 2, then 2 and finally everything larger than 2).

Here is a gist for you.

EDIT. I tested a wrong version first and therefore thought it's okay as is. But no, it should be adjusted a bit.