SORTING ALGORITHMS

Program in C++ for merge sort

#include<iostream>

using namespace std;

void display(double *arr, int size){

    for (int i = 0; i < size; i++)

        cout<<arr[i]<<" ";

    cout<<endl;

}

void merge(double *arr, int size, int low, int mid, int high){

    double *temp = new double[size];

    for (int i = low; i <= high; i++)

        temp[i] = arr[i];

    int i = low, j = mid + 1, k = low;

    while(i <= mid && j <= high){

        if(temp[i] <= temp[j])

            arr[k] = temp[i++];

        else arr[k] = temp[j++];

        k++;

    }

    while(i <= mid)

        arr[k++] = temp[i++];

}

void mergeSort(double *arr, int size, int low, int high){

    if ( low >= high) return;

    int mid = static_cast<int>(low/2 + high/2);

    mergeSort(arr, size, low, mid);

    mergeSort(arr, size, mid+1, high);

    display(arr, size);

    merge(arr, size, low, mid, high);

}

int main(){

    double arr[] = {99, 5, 94, 59, 0, -1, 2, -5};

    int size = sizeof(arr)/sizeof(arr[0]);

    mergeSort(arr, size, 0, size -1);

    display(arr, size);

    return 0;

}

Program code for Radix sort implemented in C++

#include <iostream>

#include <queue>

#include <deque>

#include <algorithm>

#include <iterator>

using namespace std;

void getinddigs(int digits[],int number)

{

    int i= 0;

    while(number)

    {

        digits[i++] = number % 10;

        number /= 10;

    }

}

int main()

{

    int n;

    cout << "Enter the number of data to enter : " ;

    cin >> n;

    int data[n];

    for (int j=0;j<n;j++)

    cin >> data[j];

    int indv_digits[3];

    deque<int> num[10];

    for (int i=0;i<3;i++){

        for (int j=0;j<n;j++){

             getinddigs(indv_digits,data[j]);

             reverse(indv_digits,indv_digits+3);

             num[indv_digits[i]].push_back(data[j]);

        }

        int cnt = 0;

        for(int k=0;k<10;k++)

        {

            sort(num[k].begin(), num[k].end());

            while (num[k].size()){

                data[cnt++] = num[k].front();

                num[k].pop_front();

            }

        }

        for (int j=0;j<n;j++){

            cout << data[j] << " " ;

        }

        cout << endl;

    }

    cout << endl;

    for (int j=0;j<n;j++){

        cout << data[j] << " " ;

    }

}

Program codes for heap sort

#include <iostream>

using namespace std;

void heapsort(int array[], int size);

void buildheap(int array[], int size);

void percolateDown(int heap[], int size, int id);

void printArray(int array[], int size) {

        for(int i=0; i<size; i++) {

                cout << array[i] << " ";

        }

        cout << endl;

}

int main() {

        int size = 5;

        cout<<"Enter the size of the array ::" ; cin>>size ;

        int arrayToSort[size];

        for(int i=0; i<size; i++)

                cin>>arrayToSort[i]; // between 1 and 99

        printArray(arrayToSort, size);

        heapsort(arrayToSort, size);

        printArray(arrayToSort, size);

}

void heapsort(int array[], int size) {

        buildheap(array, size);

        int heapsize = size;

        for(int i=size-1; i>0; i--) {

                int temp = array[i];

                array[i] = array[0];

                array[0] = temp;

                heapsize--;

                percolateDown(array, heapsize, 0);

        }

}

void buildheap(int array[], int size) {

        for(int i=size/2; i>=0; i--) {

                percolateDown(array, size, i);

        }

}

void percolateDown(int array[], int size, int id) {

        int current = id;

        int max;

        while(true) {

                int left = current*2+1;

                int right = current*2+2;

                if(left >= size)

                        return;

                else if(right >= size)

                        max = left;

                else if(array[left] > array[right])

                        max = left;

                else if(array[left] < array[right])

                        max = right;

                if(array[max] > array[current]) {

                        int temp = array[max];

                        array[max] = array[current];

                        array[current] = temp;

                        current = max;

                } else

                        return;

        }

}