# Randomized Quick Sort

1. Aug 11, 2004

### abacus

My textbook has the following code as a Quick Sort. It also discusses a randomized quick sort which should have a faster run time, but doesn't show the code for it. What would the code be like? Is only the pivot changed?

Code (Text):

void quickSortStep(Sequence& S, int leftBound, int rightBound) {
if (leftBound >= rightBound) return;           // 0 or 1 elements
Object pivot = S.atRank(rightBound).element(); // select last as pivot
int leftIndex = leftBound;                 // will scan rightward
int rightIndex = rightBound - 1;           // will scan leftward
while (leftIndex <= rightIndex) {
while ((leftIndex <= rightIndex) &&           // scan right to larger
S.atRank(leftIndex).element() <= pivot)
leftIndex++;
while ((rightIndex >= leftIndex) &&           // scan left to smaller
S.atRank(rightIndex).element() >= pivot)
rightIndex--;
if (leftIndex < rightIndex)               // both elements found
S.swapElements(S.atRank(leftIndex), S.atRank(rightIndex));
}                         // until indices cross
// pivot at leftIndex
S.swapElements(S.atRank(leftIndex), S.atRank(rightBound));
quickSortStep(S, leftBound, leftIndex-1);       // recur on both sides
quickSortStep(S, leftIndex+1, rightBound);
}

http://cpp.datastructures.net/source/ch10/CPP/Sort.h-QuickSort.html

2. Aug 11, 2004

### dduardo

Staff Emeritus
In a randomized quicksort algorithm, you randomly pick the pivots in order to avoid the worst case scenario of O(n^2).

3. Aug 11, 2004

### abacus

so I can just set Object pivot = rand(); ?

4. Aug 11, 2004

### dduardo

Staff Emeritus
The pivot would have to be between your lower and upper bound.

If your doing a quicksort on an array you could do this to find the position of the random pivot based on the lower bound:

PIVOT = LOWER + rand()%(UPPER-LOWER + 1)

0 <= rand()%(UPPER-LOWER) =< UPPER

I would then switch the value of the PIVOT with the value of LOWER in order to make the rest of the algorithm just like a normal quicksort.

EXAMPLE:

BEFORE

0123456789 <= ARRAY INDICES
2349871092 <= ARRAY VALUES

PIVOT = LOWER + rand()%(UPPER-LOWER+1)
LOWER = 0
UPPER = 9
PIVOT = 0 + rand()%(9-0+1) = rand()%10 = 2

TEMP = ARRAY[LOWER]
ARRAY[LOWER] = ARRAY[PIVOT]
ARRAY[PIVOT] = TEMP

AFTER
=|----->------|
0123456789 <= ARRAY INDICES
4329871092 <= ARRAY VALUES

The rest is the same as the regular quicksort.

Last edited: Aug 11, 2004
5. Aug 11, 2004

### Goalie_Ca

A better choice would be to take the median of both enpoints and the middle element and use insertion sort of partitions less then (8,9 or 10) in length.

6. Aug 12, 2004

### abacus

so something like this?

Code (Text):

void RandQuickSort(int Array[], int l, int r) {

int piv=l+(rand()%(r-1+1);
swap(Array[1],Array[piv]);
int i = l+1;
int j = r;
while (1) {
while(Array[i] <= Array[1] && i<r) ++i;
while (Array[j] <= Array[l] && j>l) –-j;
if (i >=j) {
swap(Array[j],Array[l]);
return j;
}
else Swap(Array[i],Array[j]);
}

Last edited: Aug 12, 2004
7. Aug 12, 2004

### dduardo

Staff Emeritus
The real test is if it works. Have you tried compiling it?

From the looks of it there is somthing wrong with the first line of your function. What's -1+1? Do you mean -l+1

8. Aug 12, 2004

### abacus

Yeah I guess it's not working.

*updated below

Last edited: Aug 12, 2004
9. Aug 12, 2004

### dduardo

Staff Emeritus
You give up too quickly. For example:

RandQuickSort(k);

This line is obviously wrong. Look at your function definition:

void RandQuickSort(int Array[], int l, int r)

It has 3 arguments.

10. Aug 12, 2004

### abacus

randQuickSort(k, k[0], k[9]); would saying k[0](left) and k[9] (right) signify their positions in the array?

Last edited: Aug 12, 2004
11. Aug 12, 2004

### dduardo

Staff Emeritus
1. Why are you using the array values of the lower and upper bound? I would think you would just use the positions themselves.
2. C/C++ is case sensitive. RandQuickSort != randQuickSort

12. Aug 12, 2004

### abacus

Sorry, I thought that calling on the values would have indicated the positions. How would I call on the positions l, r or would I need to declare the two ints in main first?

Right now I seem to compile without error, some warnings, and there seems to be a memory leak.

Code (Text):

#include <iostream>

using namespace std;

void randQuickSort(int Array[], int l, int r);

int main()
{
int k[10];
int r=0;
for(int i=0; i < 10; i++){
cin>> k[i];
}

cout << "Unsorted:" <<k <<endl;

randQuickSort(k, i, r-1);

cout<< "Done with sort.\n";
cout<< "Displaying sorted input:\n";

for(int j=0; j < 10; j++){
cout << k[j];
}
}

void swap(int a, int b)
{
int temp;
temp=a;
a = b;
b=temp;
}

void randQuickSort(int Array[], int l, int r)
{
int piv=l+(rand()%(r-l+1));
swap(Array[1],Array[piv]);
int i = l+1;
int j = r;
while (Array[i] <= Array[j]) {
while ((Array[i] <= Array[j]) && i <= piv)
i++;
while ((Array[j] <= Array[i]) && j >= piv)
j--;
if (Array[i] < Array[j])
swap (i,j);
}
swap(l,r);
randQuickSort(Array, l, i-1);
randQuickSort(Array, l+1, r);
}

And why did earlier you suggested this, where would that go under my sort function:
Code (Text):

int temp = Array[l];
Array[l] = Array[piv];
Array[piv] = temp;

Last edited: Aug 12, 2004
13. Aug 13, 2004

### dduardo

Staff Emeritus
It seems as if you don't know how quicksort works. I recommend you take the example in your book and examine it by running it through a debugger. Step through the code line by line. If you don't know how to use a debugger ask me.

You should only have to change one line of code to make quicksort randomized.

14. Aug 13, 2004

### abacus

I think I'm getting close, now there are no memory errors and it outputs something, but it outputs the order I inputted.

Code (Text):

#include <iostream>

using namespace std;
void quickSort(int numbers[], int array_size);
void randQuickSort(int numbers[], int left, int right);

int main()
{
int k[10];                       //array size of 10
int r=0;
cout<<"Enter 10 values in unsorted order : \n";
for(int i=0; i < 10; i++){
cin>> k[i];                  //user inputs values
}

randQuickSort(k, i, r-1);         //sort function being used

cout<<"\nThe Sorted order is : \n";

for(int j=0; j < 10; j++){
cout <<k[j] <<"";            //sorted order output
}
cout<<endl;
}

void quickSort(int numbers[], int array_size)
{
randQuickSort(numbers, 0, array_size - 1);
}

void randQuickSort(int numbers[], int left, int right)
{
if(left>=right) return;
int pivot = numbers[left+rand()%10];               //pivot = left + rand()%(right-left + 1)
int leftIndex  = left;
int rightIndex  = right-1;
while (left <= right)
{
while ((numbers[right] >= pivot) && (left < right))
right--;
if (left != right)
{
numbers[left] = numbers[right];
left++;
}
while ((numbers[left] <= pivot) && (left < right))
left++;
if (left != right)
{
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = leftIndex ;
right = rightIndex ;
if (left < pivot)
randQuickSort(numbers, left, pivot-1);
if (right > pivot)
randQuickSort(numbers, pivot+1, right);
}

I'm sorry to have been a bother to you dduardo, thanks for your patience. I just wanted to get it working completely by tonight.

15. Aug 13, 2004

### Hurkyl

Staff Emeritus
When your function looks like it's doing nothing, it frequently is, in fact, doing nothing. Can you think of any reason why your function might do nothing?

16. Aug 13, 2004

### abacus

I thought that would somehow call the positions of the left and right.

17. Aug 13, 2004

### Hurkyl

Staff Emeritus
What values are you passing for left and right?
(Yes, yes, I know you're passing i for left and r-1 for right; what values do they have?)

18. Aug 13, 2004

### abacus

I was thinking 0 and 9, but that had the same effect.

19. Aug 13, 2004

### Hurkyl

Staff Emeritus
Do you know what values actually got passed?

Have you used a debugger like dduardo suggested? If you don't have a debugger available, you can achieve a similar effect by sprinkling cout statements all over your code. For instance, as the first line in your function, you could put:

cout << "Quicksort called: left = " << left << " and right = " << right << endl;
cout << "Array is:";
for(i = left; i <= right; ++i) cout << " " << k << endl;

(I'm assuming that you're intending right to refer to an index inside the array, instead of the first index outside the array)

20. Aug 13, 2004

### abacus

I don't know how to use a debugger

as for the example you posted in only shows whatever I had inputed
randQuickSort(k, value,value)