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.

Share

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.

*

Click to Insert Smiley

SmileBig SmileGrinLaughFrownBig FrownCryNeutralWinkKissRazzChicCoolAngryReally AngryConfusedQuestionThinkingPainShockYesNoLOLSillyBeautyLashesCuteShyBlushKissedIn LoveDroolGiggleSnickerHeh!SmirkWiltWeepIDKStruggleSide FrownDazedHypnotizedSweatEek!Roll EyesSarcasmDisdainSmugMoney MouthFoot in MouthShut MouthQuietShameBeat UpMeanEvil GrinGrit TeethShoutPissed OffReally PissedMad RazzDrunken RazzSickYawnSleepyDanceClapJumpHandshakeHigh FiveHug LeftHug RightKiss BlowKissingByeGo AwayCall MeOn the PhoneSecretMeetingWavingStopTime OutTalk to the HandLoserLyingDOH!Fingers CrossedWaitingSuspenseTremblePrayWorshipStarvingEatVictoryCurseAlienAngelClownCowboyCyclopsDevilDoctorFemale FighterMale FighterMohawkMusicNerdPartyPirateSkywalkerSnowmanSoldierVampireZombie KillerGhostSkeletonBunnyCatCat 2ChickChickenChicken 2CowCow 2DogDog 2DuckGoatHippoKoalaLionMonkeyMonkey 2MousePandaPigPig 2SheepSheep 2ReindeerSnailTigerTurtleBeerDrinkLiquorCoffeeCakePizzaWatermelonBowlPlateCanFemaleMaleHeartBroken HeartRoseDead RosePeaceYin YangUS FlagMoonStarSunCloudyRainThunderUmbrellaRainbowMusic NoteAirplaneCarIslandAnnouncebrbMailCellPhoneCameraFilmTVClockLampSearchCoinsComputerConsolePresentSoccerCloverPumpkinBombHammerKnifeHandcuffsPillPoopCigarette