Quick Sort

Worst case performance	O(n2)
Best case performance	O(n log n)
Average case performance	O(n log n)

(Source: http://en.wikipedia.org/wiki/Quicksort )

Tip: Randomly shuffle the array before sort to reduce the probability of the Worst case.

class Program
    {
        private void Swap(int[] input, int x, int y)
        {
            var temp = input[x];
            input[x] = input[y];
            input[y] = temp;
        }

        public int[] QuickSort(int[] input)
        {
            this.QuickSort(input, 0, input.Length - 1);
            return input;
        }

        private void QuickSort(int[] input, int low, int high)
        {
            if (low < high)
            {
                int j = Partition(input, low, high);
                QuickSort(input, low, j - 1);
                QuickSort(input, j + 1, high);
            }
        }

        private int Partition(int[] input, int low, int high)
        {
            int i=low+1;
            int j = high;
            // out of the loop if low value is come to the partition point

            while (true)
            {
                while (input[i] < input[low])
                {
                    i++;
                    if (i >= high)
                    {
                        break;
                    }
                }

                while (input[j] > input[low])
                {
                    j--;
                    if (j <= low)
                    {
                        break;
                    }
                }

                if (i >= j)
                {
                    Swap(input, j, low);

                    break;
                }
                else
                {
                    Swap(input, i, j);
                }
            }

            return j;
        }



        static void Main(string[] args)
        {
            Random r = new Random(DateTime.Now.Millisecond);
            int arraySize = 10000000;
            int[] Quick = new int[arraySize];
         

            for (int x = 0; x < Quick.Length; x++)
            {
                Quick[x] = x;
            }

            for (int x = 0; x < Quick.Length; x++)
            {
                int random = r.Next(0, x);
                var temp = Quick[random];
                Quick[random] = Quick[x];
                Quick[x] = temp;
           
            }

            var p = new Program();
            var StopWtch = new System.Diagnostics.Stopwatch();

            StopWtch.Reset();
            StopWtch.Start();
            p.QuickSort(Quick);
            StopWtch.Stop();
            Console.WriteLine("QUICKSORT:   " + StopWtch.Elapsed.TotalSeconds + "sec");

            Console.ReadLine();
        }
    }

Heap Sort

Heapsort is a comparison-based sorting algorithm to create a sorted array (or list), and is part of the selection sort family. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(nlog n) runtime. Heapsort is an in-place algorithm, but it is not a stable sort.

(Source: http://en.wikipedia.org/wiki/Heapsort)

    class Program
    {
        private void Swap(int[] input, int x, int y)
        {
            var temp = input[x];
            input[x] = input[y];
            input[y] = temp;
        }

        private int[] HeapSort(int[] input)
        {
            temp = input;

            // make the irregular array into heap format
            for (int i = input.Length / 2; i >= 1; i--)
            {
                sweep(i, input.Length);
            }

            // sort the heap
            for (int N = input.Length; N >= 1; )
            {
                Swap(temp, 0, N - 1);
                N--;
                sweep(1, N);

            }
     
            return input;
        }

        private int[] temp;

        private int getElementOneBasedIndex(int oneBasedIndex)
        {
            return temp[oneBasedIndex - 1];
        }

        private int sweep(int i, int N)
        {
            for ( ; i <= N/2;)
            {
                int leftChild = getElementOneBasedIndex(2 * i);
                int rightChild = int.MinValue;
                if (2 * i + 1 <= N)
                {
                    rightChild = getElementOneBasedIndex(2 * i + 1);
                }
                int maxChild = leftChild > rightChild ? 2 * i : 2 * i + 1;
                if (getElementOneBasedIndex(maxChild) > getElementOneBasedIndex(i))
                {
                    Swap(temp, maxChild-1, i-1);
                }
                i = maxChild;
            }
            return i;
           
        }

       

   
        static void Main(string[] args)
        {
            Random r = new Random(DateTime.Now.Millisecond);
            int arraySize = 10000000;
            int[] Heap = new int[arraySize];
           

            for (int x = 0; x < IteMerge.Length; x++)
            {
                Heap[x] = x;
            }

            for (int x = 0; x < IteMerge.Length; x++)
            {
                int random = r.Next(0, x);
                var temp = Heap[random];
                Heap[random] = IteMerge[x];
                Heap[x] = temp;
            }


            var p = new Program();
            var StopWtch = new System.Diagnostics.Stopwatch();

            StopWtch.Reset();
            StopWtch.Start();
            p.HeapSort(Heap);
            StopWtch.Stop();
            Console.WriteLine("HEAPSORT:    " + StopWtch.Elapsed.TotalSeconds + "sec");

            Console.ReadLine();
        }
    }

Recursive Merge Sort

class Program
    {
        private void Swap(int[] input, int x, int y)
        {
            var temp = input[x];
            input[x] = input[y];
            input[y] = temp;
        }

        public int[] MergeSort(int[] input)
        {
            int[] temp = new int[input.Length];
            this.RecursiveMergeSort(input, temp, 0, (input.Length - 1) / 2, input.Length - 1);

            return input;
        }

        private void RecursiveMergeSort(int[] input, int[]temp, int low,int mid, int high)
        {
            if (low < high)
            {
                RecursiveMergeSort(input,temp,low, (low + mid) / 2, mid);
                RecursiveMergeSort(input, temp,mid + 1, (mid + 1 + high) / 2, high);
                Merge(input, temp, low, mid, high);

            }
        }

        private void Merge(int[] input, int[] temp, int low, int mid, int high)
        {
            for (int i = low; i <= high; i++)
            {
                temp[i] = input[i];
            }

            int l = low;
            int h = mid + 1 ;
            for (int i = low; i <= high; i++)
            {
                if (h > high)
                {
                    input[i] = temp[l++];
                }
                else if (l > mid)
                {
                    input[i] = temp[h++];
                }
                else
                {
                    if (temp[l] <= temp[h])
                    {
                        input[i] = temp[l++];

                    }
                    else
                    {
                        input[i] = temp[h++];
                    }
                }
            }

        }

       
   
        static void Main(string[] args)
        {
            Random r = new Random(DateTime.Now.Millisecond);
            int arraySize = 10000000;
            int[] Merge= new int[arraySize];
           

            for (int x = 0; x < Quick.Length; x++)
            {
                Merge[x] = x;
            }

            for (int x = 0; x < Quick.Length; x++)
            {
                int random = r.Next(0, x);
                var temp = Merge[random];
                Merge[random] = Merge[x];
                Merge[x] = temp;
            }


            var p = new Program();
            var StopWtch = new System.Diagnostics.Stopwatch();

            StopWtch.Reset();
            StopWtch.Start();
            p.MergeSort(Merge);
            StopWtch.Stop();
            Console.WriteLine("MERGESORT:   " + StopWtch.Elapsed.TotalSeconds + "sec");
            Console.ReadLine();
        }
    }

Iterative Merge Sort

class Program
    {
        private void Swap(int[] input, int x, int y)
        {
            var temp = input[x];
            input[x] = input[y];
            input[y] = temp;
        }

        private void Merge(int[] input, int[] temp, int low, int mid, int high)
        {
            for (int i = low; i <= high; i++)
            {
                temp[i] = input[i];
            }

            int l = low;
            int h = mid + 1 ;
            for (int i = low; i <= high; i++)
            {
                if (h > high)
                {
                    input[i] = temp[l++];
                }
                else if (l > mid)
                {
                    input[i] = temp[h++];
                }
                else
                {
                    if (temp[l] <= temp[h])
                    {
                        input[i] = temp[l++];

                    }
                    else
                    {
                        input[i] = temp[h++];

                    }
                }
            }
        }

        public int[] InlineMerge(int[] input)
        {
            temp = new int[input.Length];
            // i length of the merging arrays
            for (int i = 1; i < input.Length; i *= 2)
            {
                // j is the starting position of the current merging arrays
                for (int j = 0; j < input.Length; j += 2 * i)
                {
                    if (j + i < input.Length)
                    {
                        int high = j + 2 * i - 1<input.Length?j + 2 * i - 1:input.Length-1;
                        Merge(input, temp, j, j + i - 1,high);
                    }
                }
            }
            return input;
        }

   
        static void Main(string[] args)
        {
            Random r = new Random(DateTime.Now.Millisecond);
            int arraySize = 10000000;
            int[] IteMerge = new int[arraySize];
           
            for (int x = 0; x < IteMerge.Length; x++)
            {
                IteMerge[x] = x;
            }

            for (int x = 0; x < IteMerge.Length; x++)
            {
                int random = r.Next(0, x);
                var temp = IteMerge[random];
                IteMerge[random] = IteMerge[x];
                IteMerge[x] = temp;
            }


            var p = new Program();
            var StopWtch = new System.Diagnostics.Stopwatch();

            StopWtch.Reset();
            StopWtch.Start();
            p.InlineMerge(InlineMerge);
            StopWtch.Stop();
            Console.WriteLine("ITERATIVEMERGE: " + StopWtch.Elapsed.TotalSeconds + "sec");

            Console.ReadLine();
        }
    }

Bucket Sort

A bucket sort begins with single subscripted array of positive integers to be sorted and a double subscripted array of integers with rows subscripted from 0 to 9 and columns subscripted from 0 to n-1 where n is the number of values in the array to be sorted.
Algorithm
1. Loop through the single subscripted array and place each of its values in a row of the bucket array based on its ones dight.
2.loop through bucket array. copy each element and past it in data array.
3.Repeat the process for each subsequent positions (tens, hundreds,thousands)
Note:
double subscripted array (bucket ) is 10 times larger than data array. which consume a considerable amount of memory. but its performance is high compared to bubble sort.
##############################################################
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define SIZE 20
#define MAXLENGTH  3        //MAXLENGTH means the number of numbers in a value
//eg. max value in data 9999 then  MAXLENGTH 4
void printArray(int data[]){
int i;
int j;
printf("\n\n");
for(i=0;i<SIZE;i++){
printf("%d \n",data[i]);
}
}
int main(int argc, char** argv) {
int data[SIZE];
int tmpArray[SIZE][10];
int tmpData[10]={0};
//Array initialization
srand(time(NULL));
int i;
for(i=0;i<SIZE;i++){
data[i]=rand()%((int)pow(10,MAXLENGTH));
printf("%d \n",data[i]);
}
//sorting
int power;
for(power=10;power<=(int)pow(10,MAXLENGTH);power*=10){
int j;
for(j=0;j<SIZE;j++){
int bal=data[j]%power;
bal=(int)(((10*bal)/power));
tmpArray[tmpData[bal]][bal]=data[j];
tmpData[bal]++;
}
int l;
for(j=0,l=0;j<10;j++){
int k;
for(k=0;k<tmpData[j];k++,l++){
data[l]=tmpArray[k][j];
}
tmpData[j]=0;
}
}
printArray(data);
return (EXIT_SUCCESS);
}

Bubble Sort

It is the simplest sorting technique with low memory consumption and low performance compared to other sorting techniques.


here we just compare adjacent elements and swap if there not in order.
after first iteration the last element is correctly placed. iterate the same until everything sorted.

####################################################

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

#define SIZE 10


void bubbleSort(int * const data);

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

    int data[SIZE];

    int i;
    srand(time(NULL));

    for(i=0;i<SIZE;i++){
        data[i]=rand()%100+1;
        printf("%d\n",data[i]);
    }

    bubbleSort(data);

    printf("\n\n\n");
    for(i=0;i<SIZE;i++){
        printf("%d\n",data[i]);
    }
    return (EXIT_SUCCESS);
}


void bubbleSort(int * const data){

    void swap(int * const swap1,int * const swap2);

    int i;
    for(i=0;i<SIZE;i++){
        int j;
        for(j=0;j<SIZE-i-1;j++){
            if(data[j]>data[j+1]){
                swap(&data[j],&data[j+1]);
            }
        }
    }
}


void swap(int * const swap1,  int * const swap2){
    int  tmp=*swap1;
    *swap1=*swap2;
    *swap2=tmp;
}

Selection Sort

SELECTION SORT.  (Recursive)
1.Selection Sort search array and looking for the smallest element in the array and swap it with the first element.
2.Again Search balance array without using the first element. (recursive part)


######################################################################
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 20
void printArray(int data[]){
int i;
printf("\n\n");
for(i=0;i<SIZE;i++){
printf("%d \n",data[i]);
}
}
void selectionSort(int data[],int start);
int main(int argc, char** argv) {
int data[SIZE];
//fill the array with random data
srand(time(NULL));
int i;
for(i=0;i<SIZE;i++){
data[i]=rand()%(1000);
}
printf("before Sort");
printArray(data);
//sort Array
selectionSort(data,0);
printf("after Sort");
printArray(data);
return (EXIT_SUCCESS);
}
void selectionSort(int data[],int start){
int i;
int temp=start;
for(i=start;i<SIZE;i++){
if(data[temp]>data[i]){
temp=i;
}
}
int value=data[temp];
data[temp]=data[start];
data[start]=value;
//recursive
if(start<=SIZE){
selectionSort(data,(start+1));
}
}