// Program to sort an integer array using bubble, linear, and shell sort.
// Assignment-07
// varsort.cpp, Author - Krishna Kumar Khatri.

// Uncomment ONLY the following line if you are using Turbo/Borland compiler.
// #define TC
#ifdef TC
	#include <iostream.h>
#else
	#include <iostream>
	using namespace std;
#endif
#include <conio.h>  // For getch.

int comp_grtr(int a, int b) 
    { return a > b; }

void swap(int& a, int& b)
    { a = a - b; b = a + b; a = b - a; }

void bubble_sort(int arr[], int arrsize)
{
    int i, j;
    
    for (i = 0; i < arrsize; i++)
        for (j = 0; j < arrsize - i - 1; j++)
            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
                
    for (i = 0; i < arrsize; i++)
        (i + 1) != arrsize ? cout << arr[i] << ", " :
                             cout << arr[i];
    cout << endl;
}

void linear_sort(int arr[], int arrsize)
{
    int i, j;

    for (i = 0; i < arrsize; i++)
        for (j = 0; j <= i; j++)
            if (arr[i] < arr[j])
                swap(arr[i], arr[j]);
    
    for (i = 0; i < arrsize; i++)
        (i + 1) != arrsize ? cout << arr[i] << ", " :
                             cout << arr[i];
    cout << endl;
}

void shell_sort(int arr[], int lb, int ub)
{
    int n, h, i, j;
    int t;

    /* compute largest increment */
    n = ub - lb + 1;
    
    h = 1;
    if (n < 14)
        h = 1;
    else if (sizeof(int) == 2 && n > 29524)
        h = 3280;
    else {
        while (h < n) 
            h = 3 * h + 1;
        h /= 3;
        h /= 3;
    }

    while (h > 0) {
        /* sort-by-insertion in increments of h */
        for (i = lb + h; i <= ub; i++) {
            t = arr[i];
            for (j = i - h; 
                 j >= lb && comp_grtr(arr[j], t);
                 j -= h)
                arr[j+h] = arr[j];
            arr[j+h] = t;
        }
        /* compute next increment */
        h /= 3;
    }
    
    for (i = 0; i <= ub; i++)
        (i + 1) <= ub ? cout << arr[i] << ", " :
                             cout << arr[i];
    cout << endl;
}

int main()
{
    #ifdef TC
        clrscr();
    #endif
    const int MAXSIZE = 20;
    int* arr;
    int arrsize, cnt;
    char choice;
    
    do {
        cout << "Enter the size of array (1-" << MAXSIZE << "): ";
        cin >> arrsize;
    } while (arrsize < 1 || arrsize > MAXSIZE);
    arr = new int[arrsize];
    
    cout << "Now enter " << arrsize << " elements for array: ";
    for (cnt = 0; cnt < arrsize; cnt++)
        cin >> arr[cnt];
    
    cout << endl << "b-Bubble, l-Linear, and s-Shell sort." << endl;
    cout << "Your choice: ";
    cin >> choice;

    switch (choice) {
        case 'b':
            cout << endl << "Bubble sorted list is - ";
            bubble_sort(arr, arrsize);
            break;
        case 'l':
            cout << endl << "Linear sorted list is - ";
            linear_sort(arr, arrsize);
            break;
        case 's':
            cout << endl << "Shell sorted list is - ";
            shell_sort(arr, 0, arrsize - 1);
            break;
        default:
            cout << "Invlid choice.";
    }

    end:
    cout << endl << endl << "Program over. Press any key to exit...";
    getch();
    return 0; // Successful termination.
}