Vikram Menon

/*
Sort an array of integers in descending order by different methods.
*/

#include <iostream>

using namespace std;

const int MAX = 20;

class heap                      // to facilitate heap sorting
{
    int *ar;
    int l;

public:
    void heapify(int x = 0)
    {
        if(x >= l/2)
            return;
        heapify(2*x+1);
        heapify(2*x+2);
        if(ar[2*x+1] > ar[2*x+2])       // right subnode is larger
        {
            if(ar[x] < ar[2*x+1])
            {
                int temp = ar[x];
                ar[x] = ar[2*x+1];
                ar[2*x+1] = temp;
            }
        }
        else                            // left subnode is larger
        {
            if(ar[x] < ar[2*x+2])
            {
                int temp = ar[x];
                ar[x] = ar[2*x+2];
                ar[2*x+2] = temp;
            }
        }
    }

    void push(int v)
    {
        int i = l-1;
        while(ar[i] > -MAX && i > l/2)
            i--;
        ar[i] = v;                      // empty node at lowest tier
        heapify();
    }

    heap(int *a, int n)
    {
        for(l=1; l <= n; l*=2);         // nodes in tree
        l--;                        // l = {1,3,7,15...}
        ar = new int[l];
        for(int i=0; i < l; i++)
            ar[i] = -MAX;
        for(int i=0; i < n; i++)
            push(a[i]);
    }

    ~heap()
    {
        delete[] ar;
    }

    int pop()
    {
        int temp = ar[0];
        ar[0] = -MAX;
        heapify();
        return temp;
    }
};

void swap(int *a, int p1, int p2)       // swap two integers within an array
{
    int temp = a[p1];
    a[p1] = a[p2];
    a[p2] = temp;
}

void simplesort(int *a, int n)          // position-by-position comparison
{
    int temp;
    for(int i=0; i < n; i++)
        for(int j=i; j < n; j++)
            if(a[j] > a[i])
            {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
}

void bubblesort(int *a, int n)          // compare consecutive elements repeatedly
{
    int temp;
    for(int i=0; i < n; i++)
        for(int j=0; j < n-1-i; j++)
            if(a[j+1] > a[j])
            {
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
}

void mergesort(int *a, int n)           // sort on merging sublists
{
    if(n == 1)
        return;
    int c[n];
    int *b = a+(n/2);
    mergesort(a, n/2);
    mergesort(b, n-(n/2));
    int t1=0, t2=0;
    for(int i=0; i < n; i++)
    {
        c[i] = 0;
        if(t1 >= n/2)
            c[i] = b[t2++];
        else if(t2 >= n-(n/2))
            c[i] = a[t1++];
        else if(a[t1] > b[t2])
            c[i] = a[t1++];
        else
            c[i] = b[t2++];
    }
    for(int i=0; i < n; i++)
        a[i] = c[i];
}

void heapsort(int *a,int n)             // sort using the heap class
{
    heap h(a, n);                   // parameterised constructor call
    for(int i=0; i < n; i++)
        a[i] = h.pop();
}

void quicksort(int *a, int n)       // choose a pivot P and sort as ( >= P | < P )
{
    if(n <= 1)
        return;
    int i, pivot = n/2;
    swap(a, pivot, 0);
    pivot = 0;
    for(i=1; i < n; i++)
    {
        if(a[i] >= a[pivot])
        {
            swap(a, i, pivot);
            pivot++;
            if(i != pivot)
            swap(a, i, pivot);
        }
    }
    quicksort(a, pivot);
    quicksort(a + pivot, n - pivot);
}

void selectsort(int *a, int n)          // select ith largest, place at (i-1)th location
{
    int max, temp;
    for(int i=0; i < n-1; i++)
    {
        max = i;
        for(int j=i; j < n; j++)
            if(a[j] > a[max])
                max = j;
        temp = a[max];              // store a[max] at a[i]
        a[max] = a[i];
        a[i] = temp;
    }
}

void insertsort(int *a, int n)          // insert a[i] into sorted sublist
{
    int temp;
    for(int i=1; i < n; i++)
        for(int j=i; j > 0 && a[j] > a[j-1]; j--)   // move this element into place
        {
            temp = a[j];
            a[j] = a[j-1];
            a[j-1] = temp;
        }
}

void countsort(int *a, int n)           // use sparse array to hold count of values
{
    int b[MAX];
    int top = 0;
    for(int i=0; i < MAX; i++)
        b[i] = 0;
    for(int i=0; i < n; i++)
        b[a[i]%MAX]++;
    for(int i=MAX-1; i >= 0; i--)
        while(b[i]--)
            a[top++] = i;
}

void bucketsort(int *a, int n)          // split data into buckets to sort separately
{
    int bkt[2][n], t1 = 0, t2 = 0;      // two buckets: +ve and -ve
    for(int i=0; i < n; i++)
        if(a[i] > 0)
            bkt[0][t1++] = a[i];
        else
            bkt[1][t2++] = a[i];
    selectsort(bkt[0], t1);
    selectsort(bkt[1], t2);
    for(int i=0; i < t1; i++)
        a[i] = bkt[0][i];
    for(int i=0; i < t2; i++)
        a[t1+i] = bkt[1][i];
}

void radixsort(int *a, int n)       // sort by radix, least to most significant
{
    int max = -MAX;
    for(int i=0; i < n; i++)
        if(a[i] > max)
            max = a[i];
    for(int ctr=10; max > 0; ctr*=10, max/=10)
    {
        int div = ctr/10;
        for(int i=0; i < n; i++)
            for(int j=0; j < n-1-i; j++)
                if(((a[j+1]%ctr)/div) > ((a[j]%ctr)/div))
                {
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
    }
}

void dualpivot(int *a, int n)       // choose pivots P1 > P2 and sort as ( >= P1 | > P2 | <= P2 )
{
    if(n <= 1)
        return;
    int i, pivot1 = n/3, pivot2 = 2*n/3;
    swap(a, pivot1, 0);
    swap(a, pivot2, n-1);
    pivot1 = 0;
    pivot2 = n-1;
    if(a[pivot1] < a[pivot2])
        swap(a, pivot1, pivot2);
    for(i=pivot1+1; i < pivot2; i++)
    {
        if(a[i] >= a[pivot1])
        {
            swap(a, i, pivot1);
            pivot1++;
            if(i != pivot1)
                swap(a, i, pivot1);
        }
        else if(a[i] <= a[pivot2])
        {
            swap(a, i, pivot2);
            pivot2--;
            if(i != pivot2)
                swap(a, i, pivot2);
            i--;
        }
    }
    dualpivot(a, pivot1);
    dualpivot(a + pivot1, pivot2 - pivot1);
    dualpivot(a + pivot2, n - pivot2);
}

int main()
{
    int i, n, choice;
    int *a;
    cout<<"\nNumber of elements? ";
    cin>>n;
    a = new int[n];
    cout<<"\nEnter "<<n<<" numbers:\n";
    for(i=0; i < n; i++)
        cin>>a[i];
    cout<<"\nChoose a sorting method:\n0. Simple sort\n1. Bubblesort\n2. Mergesort";
    cout<<"\n3. Quicksort\n4. Selection sort\n5. Insertion sort\n6. Heapsort";
    cout<<"\n7. Count sort\n8. Bucket sort\n9. Radix sort\n10. Dual pivot quicksort\n\n";
    cin>>choice;
    switch(choice)
    {
        case 0: simplesort(a,n); break;
        case 1: bubblesort(a,n); break;
        case 2: mergesort(a,n); break;
        case 3: quicksort(a,n); break;
        case 4: selectsort(a,n); break;
        case 5: insertsort(a,n); break;
        case 6: heapsort(a,n); break;
        case 7: countsort(a,n); break;
        case 8: bucketsort(a,n); break;
        case 9: radixsort(a,n); break;
        case 10: dualpivot(a,n); break;
        default: ;
    }
    cout<<"\nThe sorted array is:\n";
    for(i=0; i < n; i++)
        cout<<a[i]<<" ";
    cout<<"\n";
    return 0;
}