QuickSort not working, think swap is the issue, Disclaimer I must use the quicksort method provided to me

ngzg611
try {
            for (i = 0; i < data.length; i++) {
                working[i] = data[i];
            }

            FileWriter fw3 = new FileWriter("quicksort.dat");

            long startTime3 = System.nanoTime();

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

            long endTime3 = System.nanoTime();

            long totalTime3 = endTime3 - startTime3;

            System.out.println("The time to complete the quick sort was :" + totalTime3 + " nano seconds");

            for (i = 0; i < working.length; i++) {
                fw3.write(Integer.toString(working[i]) + "\n");
            }
            System.out.println("The file has been sorted by quick sort and output to quicksort.dat \n");

            fw3.close();
        } catch (IOException e) {
            System.out.println(e);
        }




static void quickSort(int data[], int left, int right) {

        int i, j;
        int partition;
        if (right > left) {
            partition = data[right];
            i = left - 1;
            j = right;

            for (;;) {
                while (data[++i] < partition);
                while (data[--j] > partition);
                if (i >= j) {
                    break;
                }
                swap(data[i], data[j]);
                swap(data[i], data[right]);
                quickSort(data, left, i - 1);
                quickSort(data, i + 1, right);

            }
        }
    }

    static void swap(int left, int right) {
        int array[] = new int[19];
        int temp = array[left];
        array[left] = array[right];
        array[right]=temp;

This is just snippets of the code whole program is other sorts. I get an out bounds error every time it gets down to the quicksort function. I use 19 as my array because that is how big the file is I have tried 20 to see if it fixes it with no luck.

EDIT: I provided updated code down below to reflect changes that were made I still get an out of bounds error.

    static void quickSort(int data[], int left, int right) {

    int i, j;
    int partition;
    if (right > left) {
        partition = data[right];
        i = left - 1;
        j = right;

        for (;;) {
            while (data[++i] < partition);
            while (data[--j] > partition);
            if (i >= j) {
                break;
            }
            swap(data, i, j);
            swap(data, i, right);
            quickSort(data, left, i - 1);
            quickSort(data, i + 1, right);

        }
    }
}


static void swap(int array[], int left, int right) {
     int temp = array[left];        
     array[left] = array[right];    
     array[right] = temp;          

}
racraman

You have declared swap as :

void swap(int left, int right)

So the arguments are the indexes into the array.

However, you call it with :

swap(data[i], data[j]);

So you are passing the VALUES in the array.

Try changing the call to :

swap(i, j);

EDIT TO ADD:

It must be pointed out that the issue above is just ONE issue with the sorting algorithm presented. Another problem is that the swap algorithm does not actually swap anything. It creates a local array variable array, operates on that and then returns (so discarding that local variable).

If your assignment is to output a sorted list of numbers, and that the numbers must be sorted using the sorting code presented - then that assignment is impossible because the sorting code presented is hopelessly flawed as a sorting algorithm; it does NOT sort (as you have found yourself), and has blatant severe issues compared to a correct implementation of quicksort (eg, you can compare to the answer here : https://stackoverflow.com/a/63811974/681444 )

EDIT TO ADD FOLLOWING REVISED CODE:

The revised sorting code is STILL hopelessly busted. It is not a correct implementation of QuickSort, and still does not sort correctly.

For example, I tried running it with the final element being the largest :

int data[] = {23, 8, 19, 35, 2, 12, 7, 64 };

Result : No sorting - the method hit the if (i >= j) {break;} with i==7 and j==6 straight off and so did nothing.

By contrast, the method in the answer I linked to above sorted correctly, so you can compare the method you have been given against that - or against other established articles (eg, do an internet search for java quicksort, there are plenty around)

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related