Randomized Quick Sort

Question

I have written the following code for randomized quicksort. This selects a random indexed element as the pivot_item in the partition function. Whenever i run the code, p is being set as either 0 or 1 only and not all the indexes from 0 to n-1 like it should be. You can verify this by removing COMMENT 1 Why is this happening and how can i fix this?

Also, the array is being sorted properly only after the index 1 as you can see in the output. Why is this and how can i fix this?

My last problem is that no matter how many times i run the program, i get the same elements in the array to start off with. Isn't rand() supposed to generate new random numbers every time? So why am i getting the same array to be sorted every time? How can i fix this?

My code:

#include<iostream>
#include<cstdlib>
using namespace std;

int partition(int low,int high,int a[])
{
int p=sizeof(a)/sizeof(a[0]);
int index=rand()%p+0;
//COMMENT 1       cout<<endl<<index<<"----"<<endl;
int temp1=a[index];
a[index]=a[low];
a[low]=temp1;
int left,right,pivot_item=a[low];
left=low;
right=high;

while(left<right)
{
while(a[left]<=pivot_item)
left++;
while(a[right]>pivot_item)
right--;
if(left<right)
{
int temp=a[right];
a[right]=a[left];
a[left]=temp;
}
}
a[low]=a[right];
a[right]=pivot_item;
return right;
}

void quicksort(int low,int high,int a[])
{
int pivot;
if(low<high)
{
pivot=partition(low,high,a);
quicksort(low,pivot-1,a);
quicksort(pivot+1,high,a);
}
}

int main()
{
int n;
n=50;
int a[n];
int i;
for(i=0;i<n;i++)
a[i]=rand()%60;

quicksort(0,n-1,a);
cout<<endl;

for(i=0;i<n;i++)
cout<<a[i]<<endl;
return 0;
}

Output:

59
55
0
2
6
2
7
7
2
9
9
9
8
1
11
12
18
16
29
23
19
16
13
22
27
27
30
31
29
33
37
21
38
42
35
42
43
44
44
46
46
46
50
50
43
52
55
55
53
57

Answer 1

Common problem, you are not getting the size of the actual array to be sorted:

int partition(int low,int high,int a[]) // a is just a pointer!
{
    int p=sizeof(a)/sizeof(a[0]); // size of pointer/size of element

You will need to pass in the size of the array. This is why that sizeof trick is awful. Instead, you could use:

template <typename T, std::size_t N>
size_t array_size(T (&)[N])
{ return N; }

Then applying array_size(a) will give you a compiler error, since a is not an array. This construct appears in many libraries (probably boost, will paste a link here once I check), and will be in The Standard in C++17.

There are also better facilities for generating random numbers here, and here for a good explanation why rand() is bad.

Answer 2

First, initialize the srand in the main, e.g. with srand(time(NULL)), to get a decent random. If you don't do this, you'll get the same "random" sequence on each run of the program. (You'll have to #include <time.h> for this.)

Second, as pointed out in the comments, you should choose the pivot with

index = low + (rand() % (high - low));

This is because the size of the subarray for which you're choosing the pivot is high-low+1, which in general is different from the size of the original array (which is what you seemed to try to compute with the sizeof magic).

Update. As pointed out by Pete Becker, it might be a good idea to not use srand in the early stages of development (for the purposes of debugging). However, it goes without saying that it's critical that you use srand if you want randomized quicksort.