Randomized Quick Sort: Code & Run Time

[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?

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

 

[dduardo]

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

 

[abacus]

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

 

[dduardo]

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.

 

[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.

 

[abacus]

so something like this?

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]);
}

 

[dduardo]

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

 

[abacus]

Yeah I guess it's not working.

*updated below

 

[dduardo]

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.

 

[abacus]

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

The error I keep getting is randQuickSort identifier not found.

 

[dduardo]

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

 

[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.

#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:

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

 

[dduardo]

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.

 

[abacus]

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

#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.

 

[Hurkyl]

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?

 

[abacus]

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?

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

 

[Hurkyl]

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?)

 

[abacus]

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

 

[Hurkyl]

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)

 

[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)

 

[Hurkyl]

That's the idea; if you can see the values the program is using, you can see when and where it has wrong values, making it easier to find the bug.

 

[dduardo]

abacus, at this point I think a debugger is going to be useless to you until you really understand what's going on. Programming isn't just about throwing random stuff at the computer and hoping it does something. You must understand the logic behind the program and be able to predict what will happen.

My suggestion is to write down on a piece of paper an unordered array with 5 random numbers. Ex: {4,1,7,3, 5}. Go line by line of your program and write down what every variable contains. Track how the unordered array is slowly sorted. This is the only way you'll understand what your program is doing. When you understand how your program works you should be able to modify it until it works the way you expect it to.

A debugger does the work for you of outputting the current state of each variable. Although it is convient, a debugger is useless if you don't know what your looking for.