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

int N, count = 1;
int pasi;
void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}
void citire(int a[], int n)
{
    int i;
    printf("Dati cele %d numere: ", n);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
}
void afisare(int a[], int n)
{
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");
}
void interschimbare(int a[], int n)
{
    int i, j;
    for (i = 0; i < n - 1; i++) {
        for (j = i + 1; j < n; j++) {
            if (a[i] > a[j]) {
                int aux = a[i];
                a[i] = a[j];
                a[j] = aux;
            }
        }
        printf("Etapa %d: ", count);
        count++;
        afisare(a, n);
    }
}

void insertie(int a[], int n)
{
    int i, j, aux;
    for (i = 1; i < n; i++)
    {
        aux = a[i];
        j = i - 1;
        while (j >= 0 && a[j] > aux)
        {
            a[j + 1] = a[j];
            j = j - 1;
        }

        a[j + 1] = aux;
        printf("Etapa %d: ", i);
        afisare(a, n);
    }
}

int cautareBinara(int a[], int cautat, int s, int d)
{
    if (d <= s)
    {
        if (cautat > a[s])
            return (s + 1);
        else
            return s;
    }
    int m = (s + d) / 2;
    if (cautat == a[m])
        return m + 1;
    if (cautat > a[m])
        return cautareBinara(a, cautat, m + 1, d);
    return cautareBinara(a, cautat, s, m - 1);
}

void insertieBinara(int a[], int n)
{
    int i, j, aux, loc;
    for (i = 1; i < n; i++)
    {
        j = i - 1;
        aux = a[i];
        loc = cautareBinara(a, aux, 0, j);
        while (j >= loc)
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = aux;
        printf("\nEtapa %d: ", i);
        afisare(a, n);
    }
}

void selectie(int a[], int n)
{
    int i, j, k_min, aux;
    for (i = 0; i < n - 1; i++)
    {
        k_min = i;
        aux = a[i];
        for (j = i + 1; j < n; j++)
            if (a[j] < a[k_min])
            {
                k_min = j;
                aux = a[k_min];
            }
        a[k_min] = a[i];
        a[i] = aux;
        printf("\nEtapa %d: ", i + 1);
        afisare(a, n);
    }
}
void selectiePerformanta(int a[], int n)
{
    int i, j, k_min, aux;
    for (i = 0; i < n - 1; i++)
    {
        k_min = i;
        for (j = i + 1; j < n; j++)
            if (a[j] < a[k_min])
                k_min = j;
        aux = a[k_min];
        a[k_min] = a[i];
        a[i] = aux;
        printf("\nEtapa %d: ", i + 1);
        afisare(a, n);
    }
}

void bubbleSort(int a[], int n)
{
    int i, j, aux;
    for (i = 1; i < n; i++)
    {
        for (j = n - 1; j >= i; j--)
            if (a[j - 1] > a[j])
            {
                aux = a[j - 1];
                a[j - 1] = a[j];
                a[j] = aux;
            }
        printf("\nEtapa %d: ", i);
        afisare(a, n);
    }

}

void shakeSort(int a[], int n)
{
    int  j, k, s, d, aux, count = 1;
    s = 1;
    d = n - 1;
    k = n - 1;
    do
    {
        for (j = d; j >= s; j--)
            if (a[j - 1] > a[j])
            {
                aux = a[j - 1];
                a[j - 1] = a[j];
                a[j] = aux;
                k = j;
            }
        s = k + 1;
        for (j = s; j <= d; j++)
            if (a[j - 1] > a[j])
            {
                aux = a[j - 1];
                a[j - 1] = a[j];
                a[j] = aux;
                k = j;
            }
        d = k - 1;
        printf("\nEtapa %d: ", count);
        afisare(a, n);
        count++;

    } while (s <= d&&count<=pasi);
}
void binsort(int a[], int n)
{
    int i, aux;
    for (i = 0; i < n; i++)
    {
        while (a[i] != i)
        {
            aux = a[a[i]];
            a[a[i]] = a[i];
            a[i] = aux;
        }
        printf("Etapa %d: ", i + 1);
        afisare(a, n);
    }
}

void shellsort(int a[], int n)
{
    int i, j, aux, l, k;
    int h[3] = { 5,3,1 };
    for (l = 0; l < 3; l++)
    {
        k = h[l];
        for (i = k; i < n; i++)
        {
            aux = a[i];
            j = i - k;
            while (j >= 0 && aux < a[j])
            {
                a[j + k] = a[j];
                j = j - k;
            }
            a[j + k] = aux;
        }
        printf("Trecerea %d: ", l + 1);
        afisare(a, n);
    }
}

void heapify(int arr[], int n, int i)
{
    int aux;
    int largest = i; // Initialize largest as root
    int l = 2 * i + 1; // left = 2*i + 1
    int r = 2 * i + 2; // right = 2*i + 2

    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l;

    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
        largest = r;
    // If largest is not root
    if (largest != i)
    {
        aux = arr[i];
        arr[i] = arr[largest];
        arr[largest] = aux;

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

// main function to do heap sort
void heapSort(int arr[], int n)
{
    int aux;
    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
    {
        heapify(arr, n, i);
        printf("Etapa %da: ", n / 2 - i);
        afisare(arr, n);
    }

    // One by one extract an element from heap
    for (int i = n - 1; i > 0; i--)
    {
        // Move current root to end
        aux = arr[0];
        arr[0] = arr[i];
        arr[i] = aux;
        printf("Etapa %db: ", n - i);
        afisare(arr, n);
        // call max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}
int partition(int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int i = (low - 1);  // Index of smaller element

    for (int j = low; j <= high - 1; j++)
    {
        // If current element is smaller than the pivot
        if (arr[j] < pivot)
        {
            i++;    // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int a[], int s, int d)
{
    if (s < d)
    {
        int pi = partition(a, s, d);
        printf("Etapa %d: ", count);
        count++;
        afisare(a, N);
        quickSort(a, s, pi - 1);
        quickSort(a, pi, d);
    }
}
int biti(int x, int k, int j)
{
    return (x >> k) & ~(~0 << j);
}
void radix_interschimbare(int a[], int s, int d, int b)
{
    int i, j, aux;
    if (d > s && b >= 0)
    {
        i = s;
        j = d;
        do
        {
            while (i < j && biti(a[i], b, 1) == 0)
                i++;
            while (i < j && biti(a[j], b, 1) == 1)
                j--;
            aux = a[i];
            a[i] = a[j];
            a[j] = aux;

        } while (i != j);
        printf("Etapa %d: ", count);
        count++;
        afisare(a, N);
        if (biti(a[d], b, 1) == 0)
            j++;
        radix_interschimbare(a, s, j - 1, b - 1);
        radix_interschimbare(a, j, d, b - 1);
    }
}
void radix_direct(int a[], int n)
{
    int b, T[100], Numar[100], m, k, i, t;
    b = sizeof(int) * 8;
    m = 4;
    for (t = 0; t < b / m; t++)
    {
        for (i = 0; i < pow(2, m); i++)
            Numar[i] = 0;
        for (i = 0; i < n; i++)
        {
            k = biti(a[i], t * m, m);
            Numar[k]++;
        }
        for (i = 1; i < pow(2, m); i++)
            Numar[i] = Numar[i] + Numar[i - 1];
        for (i = n - 1; i >= 0; i--)
        {
            k = biti(a[i], t * m, m);
            T[Numar[k] - 1] = a[i];
            Numar[k]--;

        }
        printf("Etapa %d: ", t + 1);
        afisare(T, n);
        for (i = 0; i < n; i++)
            a[i] = T[i];
    }
}

int cautare_liniara(int* a, int N)
{
    int x;
    printf("El: ");
    scanf("%d", &x);
    int i;
    for (i = 0; i < N; i++)
    {
        if (a[i] == x)
            return i;
    }
    return -1;
}

int cautare_fanion(int* a, int N)
{
    int x;
    printf("El: ");
    scanf("%d", &x);
    int i = 0;
    a[N] = x;
    while (a[i] != x)
    {
        i++;
    }
    return i;
}

int cautare_binara(int s, int d, int* a)
{
    int x;
    printf("El: ");
    scanf("%d", &x);
    int m;
    if (s > d)
        return -1;
    else
    {
        m = (s + d) / 2;
        if (x == a[m])
            return m;
        if (x < a[m])
            return cautare_binara(s, m - 1, x, a);
        else
            return cautare_binara(m + 1, d, x, a);
    }
}

int cautare_interpolare(int* a, int ic, int sf)
{
    int x;
    printf("El: ");
    scanf("%d", &x);
    if (ic <= sf)
    {
        int m;
        m = ic + (x - a[ic]) * (sf - ic) / (a[sf] - a[ic]);
        if (x == a[m])
            return m + 1;
        else
            if (x < a[m])
                return cautare_interpolare(a, x, ic, m - 1);
            else
                return cautare_interpolare(a, x, m + 1, sf);
    }
    else return 0;
}


int main()
{
    int a[20], n, opt, b,x;
    do
    {
        printf("1.Sortare prin insertie\n");
        printf("2.Sortare prin selectie\n");
        printf("3.Sortare Bubblesort\n");
        printf("4.Shakesort\n");
        printf("5.Binsort\n");
        printf("6.Shellsort\n");
        printf("7.Heap sort(ansamblu invers)\n");
        printf("8.Quicksort\n");
        printf("9.Radix interschimbare\n");
        printf("10.Radix direct\n");
        printf("11.Interschimbare\n");
        printf("12.Cautare liniara\n");
        printf("13.Cautare fanion\n");
        printf("14.Cautare binara\n");
        printf("15.Cautare interpolare\n");
        printf("0.Iesire\n");
        printf("Dati optiunea: ");
        scanf("%d", &opt);
        switch (opt)
        {
        case 1:
            printf("SORTAREA PRIN INSERTIE\n");
            printf("n=");
            scanf("%d", &n);
            citire(a, n);
            insertie(a, n);
            printf("\nTabloul dupa sortare:\n");
            afisare(a, n);
            break;
        case 2:
            printf("\nSORTAREA PRIN SELECTIE\n");
            printf("n=");
            scanf("%d", &n);
            citire(a, n);
            selectie(a, n);
            printf("\nTabloul dupa sortare:\n");
            afisare(a, n);
            break;
        case 3:
            printf("\nBUBLE SORT\n");
            printf("n=");
            scanf("%d", &n);
            citire(a, n);
            bubbleSort(a, n);
            printf("\nTabloul dupa sortare:\n");
            afisare(a, n);
            break;
        case 4:
            printf("\nSHAKE SORT\n");
            printf("n=");
            scanf("%d", &n);
            citire(a, n);
            shakeSort(a, n);
            printf("\nTabloul dupa sortare:\n");
            afisare(a, n);
            break;
        case 5:
            printf("\nBinsort\n");
            printf("n=");
            scanf("%d", &n);
            citire(a, n);
            binsort(a, n);
            printf("\nTabloul dupa sortare:\n");
            afisare(a, n);
            break;
        case 6:
            printf("Shellsort");
            printf("n=");
            scanf("%d", &n);
            citire(a, n);
            shellsort(a, n);
            printf("\nTabloul dupa sortare:\n");
            afisare(a, n);
            break;
        case 7:
            printf("\nHEAPSORT\n");
            printf("n=");
            scanf("%d", &n);
            citire(a, n);
            heapSort(a, n);
            printf("\nTabloul dupa sortare:\n");
            afisare(a, n);
            break;
        case 8:
            printf("\nQUICKSORT\n");
            printf("n=");
            scanf("%d", &n);
            N = n;
            count = 1;
            citire(a, n);
            quickSort(a, 0, n - 1);
            printf("\nTabloul dupa sortare:\n");
            afisare(a, n);
            break;
        case 9:
            printf("\nRADIX INTERSCHIMBARE\n");
            printf("n=");
            scanf("%d", &n);
            citire(a, n);
            b = sizeof(int) * 8;
            N = n;
            count = 1;
            radix_interschimbare(a, 0, n - 1, b - 1);
            printf("\nTabloul dupa sortare:\n");
            afisare(a, n);
            break;
        case 10:
            printf("\nRADIX DIRECT\n");
            printf("n=");
            scanf("%d", &n);
            citire(a, n);
            radix_direct(a, n);
            printf("\nTabloul dupa sortare:\n");
            afisare(a, n);
            break;
        case 11:
            printf("\nInterschimbare\n");
            printf("n=");
            scanf("%d", &n);
            citire(a, n);
            interschimbare(a, n);
            printf("\nTabloul dupa sortare:\n");
            afisare(a, n);
            break;
        case 12:
            printf("El: ");
            scanf("%d", &x);
            printf("%d", cautare_liniara(a,n));
            break;
        case 13:
            printf("El: ");
            scanf("%d", &x);
            printf("%d", cautare_fanion(a, n));
            break;
        case 14:
            printf("El: ");
            scanf("%d", &x);
            printf("%d", cautare_binara(0, n - 1, a));
            break;
        case 15:
            printf("El: ");
            scanf("%d", &x);
            printf("%d", cautare_interpolare(a, 0, n - 1));
            break;
        case 0:
            printf("\nAti oprit consola interactiva\n");
            break;
        default:
            printf("\nOPTIUNE INVALIDA\n");
            break;
        }
    } while (opt != 0);
    getch();
    return 0;
}