Back to Code List
c++

Sorting Methods

This file shows implementation of several well used sorting algorithms and outputs the times for each with various array sizes. While this is a c++ file, the concepts are the same regardless of the language. Included are the c++ standard sort, quick sort, bubble sort, merge sort, insertion sort, and selection sort.

   main.cpp

#include <algorithm>
#include <ctime>
#include <iostream>

const int SMALL = 100;
const int MED = 5000;
const int LARGE = 50000;

void initNewArr(int, int *);
void outputFirst30(int *);
void doSort(int, int, int *);

void stdSort(int, int *);
void bubbleSort(int, int *);
void insertionSort(int, int *);
void selectionSort(int, int *);
void mergeSort(int, int *);
void quickSort(int, int *);

void merge(int*, int, int, int);
void mergesort(int*, int, int);

void swap(int &, int &);
void QuickSort(int*, int, int);
int SplitArray(int*, int, int, int);

int main () {
	int smallArr[SMALL];
	int medArr[MED];
	int *largeArr = (int*)malloc(sizeof(int)*LARGE);

	// get some nice randomized numbers to sort!
	unsigned int t = unsigned int(std::time(NULL));
	srand(t);

	// init each arr with high random numbers
	//initNewArr(100,smallArr);
	//initNewArr(5000,medArr);
	//initNewArr(500000,largeArr);

	doSort(0,SMALL,smallArr);
	doSort(1,SMALL,smallArr);
	doSort(2,SMALL,smallArr);
	doSort(3,SMALL,smallArr);
	doSort(4,SMALL,smallArr);
	doSort(5,SMALL,smallArr);

	std::cout << std::endl << std::endl;
	
	doSort(0,MED,medArr);
	doSort(1,MED,medArr);
	doSort(2,MED,medArr);
	doSort(3,MED,medArr);
	doSort(4,MED,medArr);
	doSort(5,MED,medArr);

	std::cout << std::endl << std::endl;

	doSort(0,LARGE,largeArr);
	doSort(1,LARGE,largeArr);
	doSort(2,LARGE,largeArr);
	doSort(3,LARGE,largeArr);
	doSort(4,LARGE,largeArr);
	doSort(5,LARGE,largeArr);

	std::cout << std::endl << std::endl;

	free(largeArr);
	return 0;
}

void initNewArr(int size, int *arr) {
	for (int i=0;i<size;i++) { arr[i] = rand()*(RAND_MAX+1)+rand(); }
}

void outputFirst30(int *arr){
	std::cout << std::endl;
	for (int i=0;i<30;++i) {
		std::cout << arr[i] << " ";
	}
	std::cout << std::endl;
}

void doSort(int type, int size, int *arr) {
	initNewArr(size,arr);
	int start = clock();
	switch (type) {
		case 0: stdSort(size, arr); break;
		case 1: bubbleSort(size, arr); break;
		case 2: insertionSort(size, arr); break;
		case 3: selectionSort(size, arr); break;
		case 4: mergeSort(size, arr); break;
		case 5: quickSort(size, arr); break;
	}
	int end = clock();
	std::cout << " on array size " << size << "." << std::endl;
	float time = ((float)end-start)/CLOCKS_PER_SEC;
	std::printf("Time elapsed: %.8f seconds.",time);
	//outputFirst30(arr); // for testing
	std::cout << std::endl << std::endl;
}

void stdSort(int size, int *arr){
	std::cout << "STD::SORT";
	std::sort(arr,arr+size);
}
void bubbleSort(int size, int *arr){
	std::cout << "BUBBLE SORT";
	int i, j, flag = 1;    
	int temp;             
	for(i = 1; (i <= size) && flag; ++i)
	{
		flag = 0;
		for (j=0; j < (size-1); j++)
		{
			if (arr[j+1] > arr[j])     
			{
				temp = arr[j];             
				arr[j] = arr[j+1];
				arr[j+1] = temp;
				flag = 1;              
			}
		}
	}
}
void insertionSort(int size, int *arr){
	std::cout << "INSERTION SORT";
	int key, j;
	for (int i=1; i<size; ++i)
    {
        key= arr[i];
        j = i-1;
        while((j >= 0) && (arr[j] > key))
        {
            arr[j+1] = arr[j];
            j -= 1;
        }
        arr[j+1]=key;
    }
}
void selectionSort(int size, int *arr){
	std::cout << "SELECTION SORT";
	int i, j, first, temp;
	for (i= size-1; i > 0; --i)
	{
		first = 0;                 
		for (j=1; j<=i; j++)   
		{
			if (arr[j] < arr[first])
			first = j;
		}
		temp = arr[first];   
		arr[first] = arr[i];
		arr[i] = temp;
	}
}
void mergeSort(int size, int *arr){
	std::cout << "MERGE SORT";
	mergesort(arr,0,size-1);
}
void quickSort(int size, int *arr){
	std::cout << "QUICK SORT";
	QuickSort(arr,0,size-1);
}


void merge(int* arr, int low, int middle, int high)
{
    int* tmp = new int[high-low+1];
    int i = low;
    int j = middle+1;
    int k = 0;
    while ((i <= middle) && (j <= high))
    {
        if (arr[i] < arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }
    if (i <= middle)
    {
        while (i <= middle)
            tmp[k++] = arr[i++];
    }
    if (j <= high)
    {
        while (j <= high)
            tmp[k++] = arr[j++];
    }
    /*See how are we adjusting tmp array index below*/
    for (k = low; k <= high; ++k)
        arr[k] = tmp[k-low];
    delete[] tmp;
    return;
}
void mergesort(int* arr, int low, int high)
{
    if (low < high)
    {
        int middle = (high + low)/2;
        mergesort(arr, low, middle);
        mergesort(arr, middle+1, high);
        merge(arr, low, middle, high);
    }
    return;
}


void swap(int &a, int &b)
{
	int temp;
	temp = a;
	a = b;
	b = temp;
}
void QuickSort(int* array, int startIndex, int endIndex)
{
	int pivot = array[startIndex];					
	int splitPoint;
	
	if(endIndex > startIndex)						
	{
		splitPoint = SplitArray(array, pivot, startIndex, endIndex);
		array[splitPoint] = pivot;
		QuickSort(array, startIndex, splitPoint-1);   
		QuickSort(array, splitPoint+1, endIndex);	 
	}
}
int SplitArray(int* array, int pivot, int startIndex, int endIndex)
{
	int leftBoundary = startIndex;
	int rightBoundary = endIndex;
	
	while(leftBoundary < rightBoundary)			
	{
		 while( pivot < array[rightBoundary]		 
				&& rightBoundary > leftBoundary)	
		 {
			  rightBoundary--;					
		 }
		 swap(array[leftBoundary], array[rightBoundary]);
		 
		 while( pivot >= array[leftBoundary]		 
				&& leftBoundary < rightBoundary)	
		 {
			  leftBoundary++;						
		 }
		 swap(array[rightBoundary], array[leftBoundary]);
	}
	return leftBoundary;							  
}