java - QuickSort Random Pivot Not Sorting -

java - QuickSort Random Pivot Not Sorting -

as title implies, working on java implementation of quicksort. read in algorithms textbook (sedgewick text), choosing random pivot reduces chance worse case performance when array sorted. when used first element(all way left) pivot, consistently received sorted array. however, when chose random pivot, began unsorted nonsense. can tell me mistakes making? give thanks in advance.

static void quicksort(string arr[], int left, int right) { if (left < right) { int index = partition(arr, left, right); quicksort(arr, left, index - 1); quicksort(arr, index + 1, right); } } static int partition(string[] a, int p, int r) { random rand = new random(); int randomnumber = rand.nextint(a.length); string pivot = a[randomnumber]; int left = p - 1; // index left side // next loop maintains these conditions // 1. every element of a[p..i] less or equal pivot. // 2. every element of a[i+1..j-1] greater pivot. // 3. a[r] equals pivot. (int j = p; j < r; j++) { // j index right side // find out side a[j] goes into. if left side, // have // increment size of left side , a[j] // position i. // if right side, a[j] want it, // incrementing // j in loop header suffices. if (a[j].compareto(pivot) <= 0) { left++; // a[j] belongs in left side, create 1 // larger swap(a, left, j); } } // dropped out of loop because j == r. every element of a[p..i] // less or equal pivot, , every element of a[i+1..r-1] // // greater pivot. if set pivot position i+1, // // have want: a[p..i] less or equal pivot, a[i+1] // equals pivot, , a[i+2..r] greater pivot. swap(a, left + 1, r); // homecoming index of pivot ended up. homecoming left + 1; } // swap elements @ 2 indices , j in array a. static void swap(string[] a, int i, int j) { string t = a[i]; a[i] = a[j]; a[j] = t; }

you choosing pivot randomly entire array, when should element of sublist on called partition:

int randomnumber = p+rand.nextint(r-p); string pivot = a[randomnumber];

once have chosen pivot should swap first or lastly element of sublist. makes easier write partition algorithm.

java arrays sorting quicksort partitioning