Implementing Counting sort C++

Counting sort is a technique which sorts input in o(n) time complexity if it falls in particular range. 
As the input falls in particular range, the counting method works well and can be rearranged easily.

Counting sort maintain count of each element appearing in the input then it places those in the order.

Code below sorts the input array A and returns B as a sorted array.  Even you can choose to return sorted data in same array by copying B data to input array.

typedef vector<int> IntVect; void CountingSort(IntVect & A, IntVect & B, int range) {     IntVect temp;     for (size_t i = 0; i < range; i++)     {         temp.push_back(0);     }     for (int i = 0; i < A.size(); i++)     {         temp[A[i]] += 1;     }     for (int i = 1; i < temp.size(); i++)     {         temp[i] += temp[i - 1];     }     for (int i = 0; i < A.size(); i++)     {         B[temp[A[i]] - 1] = A[i];         temp[A[i]] -= 1;     } }

Counting sort described here takes o(n) additional space.

Implementing bubble sort in C++

Bubble sort is the simplest sorting algorithm. It can be viewed as the lighter values coming up step by step.

Bubble sort works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order.

The code below implements the bubble sort.

typedef vector <int> IntVect; void SwapInts(int & A, int & B) {     int temp = A;     A = B;     B = temp; } void BubbleSort(IntVect & A) {     for (int i = A.size() - 1; i >= 0; i--)     {         for (int j = 0; j < i; j++)         {             if (A[j] > A[j + 1])             {                 SwapInts(A[j], A[j + 1]);             }         }     } }

The bubble sort has O(n^2) average and worst case complexity.

Implementing heap sort algorithm in C++

Heapsort is a comparison-based sorting algorithm to create a sorted array, and is part of the selection sort family.

Heap sort build the max heap first. The max heap is where the highest element is at the front of the array. Once max heap is built then swap the highest element to end.

Now minimize the size of heap by and fulfill the max heap property. So that highest from the remaining array will be at the front. Now again swap this with second last element from the array. Follow this process till first element.

typedef vector<int> IntVect; inline int Left(int i) {     return (2 *  i); } inline int Right(int i) {     return ((2 * i) + 1); } void MaxHeapify(IntVect & A, int i, int end) {     int left = Left(i);     int right = Right(i);     int max = i;     if (left < end && A[left] > A[max])         max = left;     if (right < end && A[right] > A[max])         max = right;     if (max != i)     {         SwapInts(A[max], A[i]);         MaxHeapify(A, max, end);     } } void BuildMaxHeap(IntVect & A, int end) {     for (int i = end / 2; i >= 0 ; i--)     {         MaxHeapify(A, i, end);     } } void HeapSort(IntVect & A) {     BuildMaxHeap(A, A.size());     for (int i = A.size() - 1; i > 0; i--)     {         SwapInts(A[0], A[i]);         MaxHeapify(A, 0, i);     } }

The BuildMaxHeap method can be used for creating the priority queue as well.

Implementing Quick Sort in C++

Quicksort is a sorting algorithm which picks one element at a time and places it at its correct position, during this it also places elements less than that element on its left and element greater than that element on right side.

The code below implements the Quick sort in recursive manner.

typedef vector<int> IntVect; int QuickPartition(IntVect & A, int start, int end) {     int  key = A[end];     int j = start - 1;     for (int i = start; i < end; i++)     {         if (A[i] < key)         {             int temp = A[++j];             A[j] = A[i];             A[i] = temp;         }     }     j++;     A[end] = A[j];     A[j] = key;     return j;     } void QuickSort(IntVect & A, int start, int end) {     if (start < end)     {         int pivot = QuickPartition(A, start, end);         QuickSort(A, start, pivot - 1);         QuickSort(A, pivot + 1, end);     } }

In the worst case, it makes O(n2) comparisons, though this behavior is rare. Quicksort is often faster in practice than other O(n log n) algorithms.

Implementing Selection Sort Algorithm in C++/C

SelectionSort method implements Selection Sort algorithm in the simplest way. This method you can use in C/C++ program. Method takes integer array and size the array to be sorted and sorts the array in place.

 

void SelectionSort(int * array, int nSize) {     if( NULL == array )         return;        if( nSize < 1 )         return;     for( int nIterator = 0; nIterator < nSize - 1; nIterator++)     {         int nCurrentLow = array[nIterator];         int nPos = nIterator;         for( int nTemp = nIterator +1; nTemp < nSize; nTemp++ )         {             if( nCurrentLow > array[ nTemp ] )             {                 nCurrentLow = array[ nTemp ];                 nPos = nTemp;             }         }         array[nPos] = array[ nIterator ];         array[nIterator] = nCurrentLow;     } }

Implementing Merge Sort Algorithm in C/C++

Below function implements the Merge Sort algorithm. The function takes input as a array of integers start and end position of the array. Merge Sort  uses the Divide and Conquer method for sorting the array. 

MergeSort method divides the array and Merge method merges sorted array in sorted fashion.

void MergeSort( int * intArray, int start, int end) { if( start < end ) { int mid = (end + start)/2; Sort( intArray, start, mid ); Sort( intArray, mid+1, end ); Merge( intArray, start, mid, end); } } void Merge( int * intArray, int start, int mid, int end) {     int mid2 = mid +1;     int nFirst = (mid - start)  + 1;     int nSec= (end - mid);     int * pLeft = new int [nFirst + 1];         int * pRight = new int [nSec + 1];          for ( int cntr1= 0; cntr1 < nFirst ; ++ cntr1)     {         pLeft[cntr1] = intArray[start + cntr1];     }         pLeft[nFirst] = intArray[mid] + intArray[end];          for ( int cntr1 = 0; cntr1 < nSec ; ++ cntr1)     {         pRight[cntr1] = intArray[mid2 + cntr1];     }     pRight[nSec] = intArray[mid] + intArray[end];          for( int cntr = start, j = 0, k = 0; cntr <= end ; )     {         if( pLeft[j] < pRight[k] )         {             intArray[cntr++] = pLeft[j++];             continue;         }                 intArray[cntr++] = pRight[k++];     }     delete [] pLeft;     delete [] pRight; }

Merge method can write such as stop once either array left or right has had all its elements copied back to intArray then copy the reminder other array back to intArray as given below.

void Merge( int * intArray, int start, int mid, int end) {     int mid2 = mid +1;     int nFirst = (mid - start)  + 1;     int nSec= (end - mid);     int *pLeft = new int [nFirst];       int *pRight = new int [nSec];        for ( int cntr1= 0; cntr1 < nFirst ; ++ cntr1)     {         pLeft[cntr1] = intArray[start + cntr1];     }            for ( int cntr1 = 0; cntr1 < nSec ; ++ cntr1)     {         pRight[cntr1] = intArray[mid2 + cntr1];     }     int cntr = start, j = 0, k = 0;     for( ; j < nFirst && k < nSec ; )     {         if( pLeft[j] < pRight[k] )         {             intArray[cntr++] = pLeft[j++];         }                else         {             intArray[cntr++] = pRight[k++];         }     }     for( ; j < nFirst ; j++)     {         intArray[cntr++] = pLeft[j];     }     for( ; k < nSec ; k++)     {         intArray[cntr++] = pRight[k];     }     delete [] pLeft;     delete [] pRight; }

You can even use insertion sort to sort and merge the array as shown below. 

void Merge( int * intArray, int start, int mid, int end) {     for( int nCtr = mid+1; nCtr <= end; nCtr++)     {         int n = nCtr - 1;         int key = intArray[nCtr];         while( n >= start && intArray[n] > key  )         {             intArray[n+1] = intArray[n];             n--;         }         intArray[n+1] = key;     } }

Implementing Insertion sort in C/C++

Below function implements the insertion sort algorithm. The function takes input as a array of integers and size of the array.
The sorting is performed in place. 


void InsertionSort(int * array, int size)
{
    //we are starting from second element of the array
    for(int counter = 1; counter < size; counter++)
    {
        int nKey = array[counter];
        int tempCounter = counter-1;
        while(tempCounter >= 0 && array[tempCounter] > nKey )
        {           
            array[tempCounter+1] = array[tempCounter];
            tempCounter--;
        }
        array[tempCounter+1] = nKey;       
    }
}