[C++] Sorting – Algorithms in C++ and their complexities « HPC, AI, C++, Silverlight … Among Others

2

May

0

[C++] Sorting – Algorithms in C++ and their complexities

by Berenger

Here is the implementation of 10 sorting algorithms : There are written in C++ and has been taken from two greats books : Algorithms in a nutshell C++ Footprint and Performance Optimization Licence is (as all the blog) LGPL. Here is the code :

/*
bubble(array,Size);     O(n²)
insertion(array,Size);  O(n²)
selection(array,Size);  O(n²)
quick(array,Size);      O(n log n)
heap(array,Size);       O(n log n)
counting(array,Size);   O(n)
radix(array,Size);      O(M*n)
shell(array,Size);      O(n^1.25)
bucket(array,Size);     O(n)
merge(array,Size);      O(n log n)

Here is the implementation of 10 sorting algorithms :

<!--more-->

There are written in C++ and has been taken from two greats books :
<a href="http://www.amazon.com/Algorithms-Nutshell-OReilly-George-Heineman/dp/059651624X/ref=sr_1_1?ie=UTF8&amp;s=books&amp;qid=1304320903&amp;sr=8-1" target="_blank">Algorithms in a nutshell</a>

<a href="http://www.amazon.com/Footprint-Performance-Optimization-Sams-Professional/dp/0672319047/ref=sr_1_1?ie=UTF8&amp;s=books&amp;qid=1304320966&amp;sr=1-1" target="_blank">C++ Footprint and Performance Optimization </a>

Licence is (as all the blog) LGPL.

Here is the code :
 */

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

void swap(int& v1, int& v2){
    const int tmp = v1;
    v1 = v2;
    v2 = tmp;
}

bool isSorted(int *array, const int size){
    for(int idx = 1; idx < size ; ++idx){
        if(array[idx-1] > array[idx]) return false;
    }
    return true;
}

void print(const int* const array, const int size){
    for(int idx = 0 ;idx < size; ++idx){
        printf("%d\t",array[idx]);
    }
    printf("\n");
}

/////////////////////////////////////////////////
/////////////////////////////////////////////////

// Average Complexity : O(n²)
// Max : O(n²)
// Min : O(n)

void bubble(int* const array, const int size){
    bool hasChanged = true;
    for(int done = size ; done > 0 && hasChanged; --done){
        hasChanged = false;
        for(int iter = 1 ; iter < done ; ++iter){
            if(array[iter-1] > array[iter]){
                swap(array[iter-1],array[iter]);
                hasChanged = true;
            }
        }
    }
}

/////////////////////////////////////////////////
/////////////////////////////////////////////////

// Average Complexity : O(n²)
// Max : O(n²)
// Min : O(n)

void oddEven(int* const array, const int size){
    const int lastIndex = size - 1;
    bool hasChanged = true;
    while( hasChanged ){
        hasChanged = false;
        for(int iter = 1 ; iter < lastIndex ; iter += 2){
            if(array[iter] > array[iter+1]){
                swap(array[iter],array[iter+1]);
                hasChanged = true;
            }
        }

        for(int iter = 0 ; iter < lastIndex ; iter += 2){
            if(array[iter] > array[iter+1]){
                swap(array[iter],array[iter+1]);
                hasChanged = true;
            }
        }
    }
}

/////////////////////////////////////////////////
/////////////////////////////////////////////////

// Average Complexity : O(n²)
// Max : O(n²)
// Min : O(n)

void powerBubble(int* const array, const int size){
    int firstChangedIndex = 0;
    int lastChangedIndex = size;
    while( firstChangedIndex != lastChangedIndex){
        {
            const int lastIndexThisLoop = lastChangedIndex;
            lastChangedIndex = firstChangedIndex;

            for(int iter = firstChangedIndex + 1 ; iter < lastIndexThisLoop ; ++iter){
                if(array[iter-1] > array[iter]){
                    swap(array[iter-1],array[iter]);
                    lastChangedIndex = iter;
                }
            }
        }
        {
            const int firstIndexThisLoop = firstChangedIndex;
            firstChangedIndex = lastChangedIndex;

            for(int iter = lastChangedIndex - 1 ; iter > firstIndexThisLoop ; --iter){
                if(array[iter-1] > array[iter]){
                    swap(array[iter-1],array[iter]);
                    firstChangedIndex = iter;
                }
            }
        }
    }
}

/////////////////////////////////////////////////
/////////////////////////////////////////////////

// Average Complexity : O(n²)
// Max : O(n²)
// Min : O(n)

void insertion(int* const array, const int size){
    for(int idx = 1;idx < size ; ++idx){
        int iter = idx - 1;
        const int val = array[idx];
        while(iter >= 0 && array[iter] > val){
            swap(array[iter],array[iter+1]);
            --iter;
        }
        array[iter+1] = val;
    }
}
;
/////////////////////////////////////////////////
/////////////////////////////////////////////////

// Average Complexity : O(n²)
// Max : O(n²)
// Min : O(n²)

void selection(int* const array, const int size){
    for(int idx = size - 1; idx > 0 ; --idx){
        int maxIter = 0;
        for(int iter = 1 ; iter <= idx ; ++iter ){
            if(array[maxIter] < array[iter]){
                maxIter = iter;
            }
        }
        if(maxIter != idx){
            swap(array[maxIter],array[idx]);
        }
    }
}

/////////////////////////////////////////////////
/////////////////////////////////////////////////

// Average Complexity : O(nlogn)
// Max : O(n²)
// Min : O(nlogn)

int partition(int* const array, int left, int right){
    int part = right;
    swap(array[part],array[(right+left) / 2]);
    --right;

    while(true){
        while(array[left] < array[part]){
            ++left;
        }
        while(right >= left && array[part] <= array[right]){
            --right;
        }
        if(right < left) break;

        swap(array[left],array[right]);
        ++left;
        --right;
    }

    swap(array[part],array[left]);

    return left;
}

void qs(int* const array, const int left, const int right){
    if(left < right){
        const int part = partition(array, left, right);
        qs(array,part + 1,right);
        qs(array,left,part - 1);
    }
}

void quick(int* const array, const int size){
    qs(array,0,size-1);
}

/////////////////////////////////////////////////
/////////////////////////////////////////////////

// m size of elements
// Average Complexity : O(M*n)
// Max : O(M*n)
// Min : O(nlogn)

void radixSort(const int idxBytes, const int size, int* const original, int* const result){
    const int NbBytes = sizeof(int);
    int counter[256];
    memset(counter, 0, 256 * sizeof(int));
    {
        const unsigned char* iter = ((const unsigned char*)original) + idxBytes;
        for(int idx = 0 ; idx < size ; ++idx){
            ++counter[(*iter)];
            iter += NbBytes;
        }
    }
    {
        int startAt = 0;
        for(int idxBt = 0 ; idxBt < 256 ; ++idxBt){
            const int nb = counter[idxBt];
            counter[idxBt] = startAt;
            startAt += nb;
        }
    }
    {
        const unsigned char* iter = ((const unsigned char*)original);
        for(int idx = 0 ; idx < size ; ++idx){
            result[counter[iter[idxBytes]]++] = *(int*)iter;
            iter += NbBytes;
        }
    }
}

void radix(int* const array, const int size){
    const int NbBytes = sizeof(int);

    int* const arrayTmp = new int[size];

    int* sources = array;
    int* result = arrayTmp;

    for(int idxByte = 0 ; idxByte < NbBytes ; ++idxByte){
        radixSort(idxByte,size,sources,result);

        int* const tmp = sources;
        sources = result;
        result = tmp;
    }
    if(NbBytes & 1 /*=> result == arrayTmp */){
        memcpy(array,arrayTmp,size*NbBytes);
    }

    delete [] arrayTmp;
}

/////////////////////////////////////////////////
/////////////////////////////////////////////////

// Average Complexity : O(n^1.25)
// Max : O(n^1.50)
// Min : O(?)

void shell(int* const array, const int size){
    int stepSize = 1;
    if(size > 14){
        while(stepSize < size){
            stepSize = 3*stepSize + 1;
        }
        stepSize = (stepSize/3) /3;
    }

    while(stepSize > 0){

        for(int idx = stepSize ; idx < size ; idx += stepSize){
            int iter = idx - stepSize;
            const int val = array[idx];
            while(iter >= 0 && array[iter] > val){
                swap(array[iter],array[iter+stepSize]);
                iter -= stepSize;
            }
            array[iter+stepSize] = val;
        }

        stepSize /= 3;
    }
}

/////////////////////////////////////////////////
/////////////////////////////////////////////////

// Average Complexity : O()
// Max : O()
// Min : O()

void internal(int* array, const int n){

}

/////////////////////////////////////////////////
/////////////////////////////////////////////////

// Average Complexity : O(nlogn)
// Max : O(nlogn)
// Min : O(nlogn)

void mergearray(int* const array, const int left, const int middle, const int right){
    int*const buff = new int [right - left + 1];

    int idxLeft = left;
    int idxRight = middle + 1;
    int idxBuff = 0;

    while(idxLeft <= middle && idxRight <= right){
        if(array[idxLeft] < array[idxRight]){
            buff[idxBuff++] = array[idxLeft++];
        }
        else{
            buff[idxBuff++] = array[idxRight++];
        }
    }

    while(idxLeft <= middle){
        buff[idxBuff++] = array[idxLeft++];
    }

    while(idxRight <= right){
        buff[idxBuff++] = array[idxRight++];
    }

    memcpy(&array[left],buff,sizeof(int)*(right - left + 1));

    delete [] buff;
}

void mergesort(int* const array, const int left, const int right){
    if(left < right){
        const int middle = (right + left) / 2;
        mergesort(array,left,middle);
        mergesort(array,middle + 1 ,right);
       mergearray(array,left,middle,right);
    }
}

void merge(int* const array, const int size){
    mergesort(array,0,size-1);
}

/////////////////////////////////////////////////
/////////////////////////////////////////////////

// Average Complexity : O(n)
// Max : O(n)
// Min : O(n)

void counting(int* const array, const int size){
    int* const counter = new int[size + 1];
    for(int idx = 0; idx <= size ; ++idx){
        counter[idx] = 0;
    }

    for(int idx = 0 ; idx < size ; ++idx){
        ++counter[array[idx]];
    }

    int idxCounter = 0;
    for(int idx = 0 ; idx < size ; ++idx){
        while(!counter[idxCounter]){
            ++idxCounter;
        }
        array[idx] = idxCounter;
        --counter[idxCounter];
    }

    delete [] counter;
}

/////////////////////////////////////////////////
/////////////////////////////////////////////////

// Average Complexity : O(n)
// Max : O(n)
// Min : O(n)

//the hash function has to respect :
// if v1 < v2 < v3 then hash(v1) <= hash(v2) <= hash(v3)
int hashme(const int num){
    return num/3;
}

struct bucket_data{
    int values[10]; // dummy array
    int count;
    bucket_data() : count(0){}

    void add(const int inVal){
        values[count++] = inVal;
    }
};

void bucket(int* const array, const int size){
    bucket_data buckets[size];
    for(int idx = 0 ; idx < size ; ++idx){
        const int key = hashme(array[idx]);
        buckets[key].add(array[idx]);
    }

    int idx = 0;
    for(int iter = 0; iter < size && idx < size ; ++iter){
        if(buckets[iter].count){
            insertion(buckets[iter].values,buckets[iter].count);
            for(int buck = 0 ; buck < buckets[iter].count ; ++buck){
                array[idx++] = buckets[iter].values[buck];
            }
        }
    }
}

/////////////////////////////////////////////////
/////////////////////////////////////////////////

// Average Complexity : O(nlogn)
// Max : O(nlogn)
// Min : O(nlogn)

void heapify(int* const array, const int pos, const int size){
    const int leftChild = pos*2 + 1;
    if(leftChild < size){
        int maxIter = pos;
        if(array[maxIter] < array[leftChild]){
            maxIter = leftChild;
        }
        const int rightChild = leftChild + 1;
        if(rightChild < size && array[maxIter] < array[rightChild]){
            maxIter = rightChild;
        }

        if(maxIter != pos){
            swap(array[maxIter],array[pos]);
            heapify(array,maxIter,size);
        }
    }
}

void heap(int* const array, const int size){
    for(int idx = (size/2) - 1 ; idx >= 0 ; --idx){
        heapify(array,idx,size);
    }
    for(int idx = size - 1 ; idx > 0 ; --idx){
        swap(array[0],array[idx]);
        heapify(array,0,idx);
    }
}

/////////////////////////////////////////////////
/////////////////////////////////////////////////

int main(void){
    const int Size = 10;
    int array[Size];

    srand(time(0));

    for(int idx = 0 ; idx < Size ; ++idx){
        array[idx] = Size * (float(rand())/RAND_MAX);
    }

    //bubble(array,Size);
    //oddEven(array,Size);
    powerBubble(array,Size);
    //insertion(array,Size);
    //selection(array,Size);
    //quick(array,Size);
    //heap(array,Size);
    //counting(array,Size);
    //radix(array,Size);
    //shell(array,Size);
    //bucket(array,Size);
    //merge(array,Size);
    if(!isSorted(array,Size)){
        printf("Array is not sorted!\n");
        print(array,Size);
    }
    else {
        printf("Okay, done.\n");
    }

    return 0;
}

Enjoyed reading this post?
Subscribe to the RSS feed and have all new posts delivered straight to you.

Comments are closed.

Celadon theme by the Themes Boutique