1

I have implemented the quicksort algorithm that uses the first element of the list as pivot and it worked fine. now I refactored to pick a random index as pivot element, swap with the first element and do the quicksort subroutine. somehow, it does not work, I do not get the sorted array. here is my code, which is self-explanatory, but I am happy to explain if any clarification needed.

public class Qsort {
       public static void quickSort2(int[] arr, int i, int j){
        if (i<j){
            int part =randPartition(arr, i, j);
            quickSort2(arr, i, part-1);
            quickSort2(arr, part+1, j); 
        }
    }
    public static int randPartition(int[] arr, int start, int end){
        //int pivId = (int)(Math.random()*(end-start)+1)+start; -- *****
        int pivId = start;
        //System.out.println("pivId is "+ pivId + "; start is " + start + "; end is " + end);
        System.out.println("arr is "+ Arrays.toString(arr));
        int pivot = arr[pivId];
        swap(arr, start, pivId);
        int i = start;

        for (int j = start+1;j<=end;j++){
            if (arr[j]<pivot){
                    i++;
                    swap(arr,i,j);
            }
        }
        swap(arr, start,i);
        return i;
    }

   private static void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1]=arr[index2];
        arr[index2]=temp;
    }

   public static void main(String[] args) {
        int[] data2 = new int[]{10,11,9,7,5};
        System.out.println("Unsorted array data " + Arrays.toString(data2));
        quickSort2(data2, 0, data.length-1);
        System.out.println("Sorted array data " + Arrays.toString(data2));
      }
}

I have commented out the random pivot calculation in the code with *****. I dont see any problem with it, but having the random pivot calculation destroys the code

brain storm
  • 30,124
  • 69
  • 225
  • 393
  • Have you tried using a debugger / debug logging to figure out why it isn't behaving as you expected? – zapl Dec 20 '13 at 01:04
  • Try using `int pivId = end;` – Elliott Frisch Dec 20 '13 at 01:50
  • @ElliottFrisch: `int pivId = start` works fine. but I my question is about random pivoting, the line that is commented out in the code, does not give correct solution – brain storm Dec 20 '13 at 01:58
  • @ElliottFrisch: `pivId=start` works fine for me, what is the output you get? – brain storm Dec 20 '13 at 02:17
  • 1
    Could you supply a failing case? I switched round the commenting on the pivot selection lines, fixed a compilation bug in main, and got the following output: `Unsorted array data [10, 11, 9, 7, 5] arr is [10, 11, 9, 7, 5] arr is [5, 7, 9, 11, 10] arr is [5, 7, 9, 11, 10] Sorted array data [5, 7, 9, 10, 11]` – Patricia Shanahan Dec 20 '13 at 03:02
  • 1
    I suspect the code you're showing is not the code that actually failed, because what you gave us doesn't compile. The call to `quickSort2` in `main` invokes `data.length`, and there is no array `data`. When I fixed that, added `import java.util.Arrays;` at the top, and replace `pivId = start;` with the random version, it compiles and appears to work fine in every one of 20 trials. – pjs Dec 20 '13 at 19:02

1 Answers1

0

the rest of your code is OK,but

int pivId = (int)(Math.random()*(end-start)+1)+start; -- *****

has some problems. Consider end == start, then u got pivID == 1+start.

BUPTOrange
  • 56
  • 1
  • 6