about Quick Sort

Question

Hi I have written this code but it will print these stack traces in the console please help me thanks! (Aslo "p" and "q" are the first and last index of our array ,respectively)

public class JavaQuickSort {

public static void QuickSort(int A[], int p, int q) {
    int i, last = 0;

    Random rand = new Random();
    if (q < 1) {
        return;
    }
    **swap(A, p, rand.nextInt() % (q+1));**

    for (i = p + 1; i <= q; i++) {
        if (A[i] < A[p]) {
            swap(A, ++last, i);
        }

    }
    swap(A, p, last);
    QuickSort(A, p, last - 1);
    QuickSort(A, last + 1, q);
}

private static void swap(int[] A, int i, int j) {
    int temp;
    temp = A[i];
    **A[i] = A[j];**
    A[j] = temp;


}
public static void main(String[] args){
    int[] A = {2,5,7,3,9,0,1,6,8};
    **QuickSort(A, 0,8 );**
    System.out.println(Arrays.toString(A));
}
}

the Stack traces :

run:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -3
        at JavaQuickSort.swap(JavaQuickSort.java:38)
        at JavaQuickSort.QuickSort(JavaQuickSort.java:22)
        at JavaQuickSort.main(JavaQuickSort.java:45)
Java Result: 1
BUILD SUCCESSFUL (total time: 2 seconds)

I also bold those statements that cause these stack traces. like ==> ** ...**

EDITED:

public class JavaQuickSort {

public static void QuickSort(int arr[],int lo,int hi) {
    int n = arr.length;
    if(n<=1)
        return;
    **int r = partition(arr);**
    **QuickSort(arr,lo , r-1);**
    QuickSort(arr, r+1, hi);
}

private static void swap(int[] A, int i, int j) {
    int temp;
    temp = A[i];
    **A[i] = A[j];**
    A[j] = temp;


}
public static int partition(int arr[]){
      int i, last = 0;
 Random rand = new Random();
    int n = arr.length;
    if (n <= 1)
        return arr[0];

    **swap(arr, 0, rand.nextInt(n));**

    for (i =1; i <n; i++) {
        if (arr[i] < arr[0]) {
            swap(arr, ++last, i);
        }

    }
    swap(arr, 0, last);
    return last;
}
public static void main(String[] args){
    int[] A = {2,5,7,3,9,0,1,6,8};
    **QuickSort(A, 0,8 );**
    System.out.println(Arrays.toString(A));
}
}

I have edited my post for being more understandable also it will print these stack traces and I bold the lines that cause these stack traces!!!

the stack traces :

run:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
        at JavaQuickSort.swap(JavaQuickSort.java:27)
        at JavaQuickSort.partition(JavaQuickSort.java:39)
        at JavaQuickSort.QuickSort(JavaQuickSort.java:19)
        at JavaQuickSort.QuickSort(JavaQuickSort.java:20)
        at JavaQuickSort.QuickSort(JavaQuickSort.java:20)
        at JavaQuickSort.QuickSort(JavaQuickSort.java:20)
        at JavaQuickSort.QuickSort(JavaQuickSort.java:20)
        at JavaQuickSort.main(JavaQuickSort.java:52)
Java Result: 1
BUILD SUCCESSFUL (total time: 2 seconds)

please help me thanks

EDITED :

I have written this code with paying attention to the forst answer of this post but it wont sort my array!!!

public class JavaQuickSort {

public static void QuickSort(int arr[], int lo, int hi) {
    if (hi > lo) {
         Random rand = new Random();
        int pivotIndex = lo + rand.nextInt(hi-lo+1);
        int pivotnewIndex = partition(arr, lo, hi,pivotIndex);
        QuickSort(arr, lo, pivotnewIndex - 1);
        QuickSort(arr, pivotnewIndex + 1, hi);
    }
}

private static void swap(int[] A, int i, int j) {
    int temp;
    temp = A[i];
    A[i] = A[j];
    A[j] = temp;


}

public static int partition(int arr[],int lo,int hi,int pivotIndex)
{
    int pivotValue = arr[pivotIndex];
    swap(arr, hi, pivotIndex);
    int storeIndex = lo;
    for(int i = lo;i<hi;i++){
        if (arr[i]<=pivotValue)
        swap(arr, storeIndex, i);
        storeIndex = storeIndex ++;
    }
    swap(arr, storeIndex, hi);
    return storeIndex;

}

public static void main(String[] args) {
    int[] A = {2, 5, 7, 3, 9, 0, 1, 6, 8};
    QuickSort(A, 0, 8);
    System.out.println(Arrays.toString(A));
}
}

the output:

run:
[2, 9, 3, 8, 0, 6, 7, 1, 5]
BUILD SUCCESSFUL (total time: 2 seconds)

I need your help really I confused !!!

Answer 1

Some problems with your code are:

• Don't create a new Random instance for one time uses. Just create it once, store it in say a static field, and then use it to generate many random numbers for your application.
• When creating a random index for the pivot, it must lie between p and q inclusive.
• Use Random.nextInt(int n) overload to generate a random number in a given range
• Perhaps use lo and hi instead of p and q, and int[] arr instead of int A[]
• You can get the length of an array with its .length member

As for the quicksort algoritm itself, it doesn't look like anything I've seen before. I recommend studying the standard imperative implementation and adapting that.

See also

• Wikipedia/Quicksort

---

Update

Unfortunately you have mixed up the pseudocodes from Wikipedia somewhat. You want to adapt this algorithm:

  function partition(array, left, right, pivotIndex)
     pivotValue := array[pivotIndex]
     swap array[pivotIndex] and array[right] // Move pivot to end
     storeIndex := left
     for i  from  left to right - 1 // left ≤ i < right  
         if array[i] ≤ pivotValue 
             swap array[i] and array[storeIndex]
             storeIndex := storeIndex + 1
     swap array[storeIndex] and array[right] // Move pivot to its final place
     return storeIndex

  procedure quicksort(array, left, right)
     if right > left
         select a pivot index //(e.g. pivotIndex := left+(right-left)/2)
         pivotNewIndex := partition(array, left, right, pivotIndex)
         quicksort(array, left, pivotNewIndex - 1)
         quicksort(array, pivotNewIndex + 1, right)

Note that the above algorithm selects the middle element of the subarray between left and right for the pivot index. Since you want a randomized quicksort, you want to choose a random index between left and right inclusive, so the formula needs to be changed as follows:

  pivotIndex := left + (random number between 0 and right-left inclusive)

So, for example, if left = 5 and right = 7, then you want pivotIndex to be 5 + x where x is a random number between 0 and 7-5=2 inclusive.

Since Random.nextInt(n) has an exclusive upper bound, translating this to Java would be something like:

int pivotIndex = lo + rand.nextInt(hi - lo + 1);

---

Final correction

You've made a common mistake for beginners here:

    // HORRIBLE FORMATTING! Don't do this!
    if (arr[i]<=pivotValue)
    swap(arr, storeIndex, i);
    storeIndex = storeIndex ++;

If you noticed the pseudocode above, both statements are supposed to be part of the if body, but the above code, when properly indented and with braces added, is really this:

    // PROPER FORMATTING! Reveals bug instantly!
    if (arr[i]<=pivotValue) {
        swap(arr, storeIndex, i);
    }
    storeIndex = storeIndex ++;

The fix, therefore is to move the storeIndex increment to the if body like this:

    // Corrected according to pseudocode!
    if (arr[i]<=pivotValue) {
        swap(arr, storeIndex, i);
        storeIndex = storeIndex ++;
    }

Or you can also just do:

    // Nice and clear!
    if (arr[i]<=pivotValue) {
        swap(arr, storeIndex++, i);
    }

The lessons from this latest update is:

• Always indent your code properly
  • A good IDE can make this a breeze, you really have no excuse
• Make a habit of putting braces on if statements, even when they're not strictly necessary
  • Many subtle bugs are due to omission of braces
• Use post/pre-increments sensibly
  • Like many things, they can be abused beyond comprehension, but used appropriately and idiomatically they lead to concise and readable code

---

One last thing

When I mentioned .length of arrays, I meant that instead of this:

int[] A = {2, 5, 7, 3, 9, 0, 1, 6, 8};
QuickSort(A, 0, 8); // BAD! Don't hardcode array length!

You should do this:

int[] arr = {2, 5, 7, 3, 9, 0, 1, 6, 8};
QuickSort(arr, 0, arr.length - 1); // GOOD!

Answer 2

The random generator produces positive and negative values. That's why eventually you call swap with a negative q value.

Answer 3

swap(A, p, rand.nextInt() % (q+1));

The random integer generated may be below p, clearly you would want it to be something between p and q.

Answer 4

As this is not homework, and I'd take the homework category to encompass self-learning, you should just use the standard Arrays.sort(int[]).