Example of Quicksort using Hoarse partition and random partition algorithms.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

quicksort.c:

```/* Framework for the sorting programs.
* Program: 04
* Author: Alejandro G. Carlstein
* Description: This program will implement quicksort
* (using the pseudocode from the book), applying
* the Hoare partition function, and randomization.
* This program should run with data where all the values
* are equal, and also when the data is in sorted
* (or reverse sorted) order.
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_SIZE 1000000

#define DBG_LV1 0
#define DBG_LV2 0

void Quicksort(int array[], int p, int r);
int Hoare_partition(int array[], int p, int r);
int Randomized_partition(int array[], int p, int r);
void Exchange(int *a, int *b);
int Get_random(int min, int max);

int data[MAX_SIZE];

int n;

int main(int argc, char* argv[]){

int i;

int n;

int m = 0;

int begin = 1;

int ia_keys[MAX_SIZE];

srand (time (NULL));

/* Read in the data */
n = 0;
while (scanf('%d', &data[n]) == 1)
++n;

/* Print ou t the data */
if (DBG_LV2)
for (i = 0; i < n; ++i)
printf('[%d] %d\n', i, data[i]);

Quicksort(data, 0, n);

/* Print out the data */
for (i = 0; i < n; ++i)
if (DBG_LV2){
printf('[%d] %d\n', i, data[i]);
}else{
printf('%d\n', data[i]);
}//end if

if (DBG_LV2)
printf('+[10]: %d \n', data[10]);

return 0;
}

/*
* Quicksort
*/
void Quicksort(int array[], int p, int r){

if (DBG_LV1)
printf('Quicksort(p: %d, r: %d)\n', p, r);

int q;

if (p < r){

q = Randomized_partition(array, p, r);

Quicksort(array, p, q);

Quicksort(array, q + 1, r);

}// end if

}

/*
* Hoare partition Book
*/
int Hoare_partition(int array[], int p, int r){

if (DBG_LV1)printf('Hoare_partition_book(p: %d, r:%d)\n', p, r);

int b_done = 1;

// pivot value
int x = array[p];

int i = p - 1;

int j = r + 1;

if (DBG_LV2)
printf('i: %d, j: %d\n', i, j);

while (b_done){

do{
--j;
}while (array[j] < x);

do{
++i;
}while (array[i] > x);

if (DBG_LV2)
printf('+i: %d, j: %d\n', i, j);

if (i < j){

Exchange(&array[i], &array[j]);

}else{

b_done = 0;

}//end if

}// end while

return j;
}

/*
* Randomized partition
*/
int Randomized_partition(int array[], int p, int r){

if (DBG_LV1)
printf('Randomized_partition(p: %d, r: %d)\n', p, r);

int i = Get_random(p, r);

Exchange(&array[i], &array[r]);

return Hoare_partition(array, p, r);

}

/*
* Exchange swap the values holded by two variables
*/
void Exchange(int *a, int *b){

if (DBG_LV1)
printf('Exchange(value a: %d, value b: %d)\n', *a, *b);

int temp;

temp = *a;
*a = *b;
*b = temp;
}

/*
* get random number
*/
int Get_random(int min, int max){

if (DBG_LV1)
printf('Get_random(min: %d, max: %d)\n', min, max);

int rtn = 0;

if (max > min){

rtn = (rand() % (max - min)) + min;

}else{

fprintf(stderr, '[X] ERROR: minimum value cannot exceed maximun value\n');

exit(1);

}//end if

return rtn;
}```

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

© 2010, Alejandro G. Carlstein Ramos Mejia. All rights reserved.