Example of Quicksort using Hoarse Partition and Random Partition Algorithms

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.

Share

Example of Heapsort Algorithm

Example of Heapsort algorithm.

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.

heapsort.c:

/* Framework for the sorting programs.
 * Program: 02
 * Author: Alejandro G. Carlstein
 * Description: This program will read a set of integers from standard 
 * input and sort them by implement a heap sort using the pseudocode 
 * from the book Introduction to Algorithms' by Thomas H. Cormen. 
 * Then print them out in sorted order (smallest to largest).
 */

#include <stdio.h>

#define MAX_SIZE 1000000
#define LEFT(i) ((i << 1) + 1)
#define RIGHT(i) ((i << 1) + 2)
#define DIV_BY_2(i) (i >> 1)

void Max_heapify(int array[], int i, int heap_size);
void Build_max_heap(int array[], int heap_size);
void Exchange(int *a, int *b);
void Heapsort(int array[], int length);

int data[MAX_SIZE];
int n;

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

	int i;
	int heap_size;

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

	/* Sort the numbers low to high */
	Heapsort(data, n);

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

	return 0;
}

/*
 * Max_heapify helps to rebuild the heap region
 */
void Max_heapify(int array[], int i, int heap_size){

	int l, r, temp, largest;

	l = LEFT(i);

	r = RIGHT(i);	

	// Find Largest value
	largest = (l < heap_size && array[l] > array[i]) ? l : i;

	if (r < heap_size && array[r] > array[largest]) largest = r;

	if (largest != i){

		// Exchange 
		Exchange(&array[i], &array[largest]);

		// Rebuild heap region		
		Max_heapify(array, largest, heap_size);	

	}// end if	

}

/*
 * Build_max_heap helps to build the initial heap
 */
void Build_max_heap(int array[], int heap_size){

	int i = DIV_BY_2(heap_size);

	for (; i > -1; i--){

		Max_heapify(array, i, heap_size);

	}//end for

}

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

		int temp;

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

/*
 * Heapsort sort an array from the smallest element to the largest
 */
void Heapsort(int array[], int length){

	int i;
	int	heap_size = length ;

	Build_max_heap(data, length);

	for (i = (length - 1) ; i > 0; --i){

		// Exchange the largest item in the heap region
		// to the beginning of the sorted region
		Exchange(&data[0], &data[i]);

		// Reduce the heap region, increase the sorted region
		heap_size--;

		// Rebuild the heap region
		Max_heapify(data, 0, heap_size);

	}//end for

}

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

Share

Example of Bubble Sort Algorithm

Example of Bubble Sort algorithm

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.

bubblesort.c:

/**
 * Framework for the sorting programs. 
 * Modified by: Alejandro G. Carlstein
 * Program Number: 1
 * Description: This code will implement an insertion sort algorithm
 *              which will follow the following steps:
 *              1. Copy item at current position
 *              2. Shift previous position item to current position
 *                 while item (in previous positions) is greater than
 *                 the item copied and there are previous items 
                   to compare with the key item
 *              3. Insert copied item in the previous position in which 
 *                 the previous item is found to be
 *                 smaller than the copied item
 *                 
 */
#include <stdio.h>
#define MAX_SIZE 1000000
int data[MAX_SIZE];
int n;

int main()
{
  int i;
  int j;
  int key_item;

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

  /* Sort the numbers low to high */
  for (i = 1; i < n; i++){

  	key_item = data[i];

  	for (j = i; (j > 0) && (data[j - 1] > key_item); j--){

 	  data[j] = data[j - 1];

 	}//end for 

 	data[j] = key_item;

  }//end for

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

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

Share