#include <stdio.h>
#include <stdlib.h>
void sortowaniebabelkowe(int tab[], int n)
{
    int i, j;
    for(i=1; i<n; i++)
    {
        for(j=n-1; j>=1; j--)
        {
            if(tab[j]<tab[j-1])
            {
                int zmien;
                zmien=tab[j-1];
                tab[j-1]=tab[j];
                tab[j]=zmien;
            }
        }
    }
}

int partition(int tab[], int p, int r) // dzielimy tablice na dwie czesci, w pierwszej wszystkie liczby sa mniejsze badz rowne x, w drugiej wieksze lub rowne od x
{
int x = tab[p]; // obieramy x
int i = p, j = r, w; // i, j - indeksy w tabeli
while (1) // petla nieskonczona - wychodzimy z niej tylko przez return j
{
while (tab[j] > x) // dopoki elementy sa wieksze od x
j--;
while (tab[i] < x) // dopoki elementy sa mniejsze od x
i++;
if (i < j) // zamieniamy miejscami gdy i < j
{
w = tab[i];
tab[i] = tab[j];
tab[j] = w;
i++;
j--;
}
else // gdy i >= j zwracamy j jako punkt podzialu tablicy
return j;
}
}

void quicksort(int tab[], int p, int r) // sortowanie szybkie
{
int q;
if (p < r)
{
q = partition(tab,p,r); // dzielimy tablice na dwie czesci; q oznacza punkt podzialu
quicksort(tab, p, q); // wywolujemy rekurencyjnie quicksort dla pierwszej czesci tablicy
quicksort(tab, q+1, r); // wywolujemy rekurencyjnie quicksort dla drugiej czesci tablicy
}
}

void sortowanie_przez_wstawianie(int n, int tab[])
{
    int i, pom, j;
    for(i=1; i<n; i++)
    {
        //wstawienie elementu w odpowiednie miejsce
        pom = tab[i]; //ten element bêdzie wstawiony w odpowiednie miejsce
        j = i-1;

        //przesuwanie elementów wiêkszych od pom
        while(j>=0 && tab[j]>pom)
        {
            tab[j+1] = tab[j]; //przesuwanie elementów
            --j;
        }
        tab[j+1] = pom; //wstawienie pom w odpowiednie miejsce
    }
}

void selectionsort(int tab[], int n)
{
    int min,i,j,temp;
    for (i=0; i<n-1; i++)
    {
        min=i;
        for (j=i+1; j<n; j++)
            if (tab[j]<tab[min]) min=j;
        temp=tab[min];
        tab[min]=tab[i];
        tab[i]=temp;
    }
}

int main()
{
    int n, c, d, i, tab[200], x;
    printf("Ile liczb ma zawierac ciag n?: ");
    scanf("%d", &n);
    printf("\nWybierz 1 jesli chcesz wpisac ciag sam\nWybierz 2 jesli chcesz aby ciag zostal wygenerowany losowo\n");
    printf("Twoj wybor:  ");
    scanf("%d", &c);
    switch(c)
    {
    case 1:
    {
        printf("Wybierz metode sortowania\n");
        printf("1-Sortowanie Karciane, 2-Bubble Sort, 3-Selection Sort, 4-Quicksort");
        printf("\nTwoj wybor: ");
        scanf("%d", &d);
        switch(d)
        {
        case 1:
        {
            for(i=0; i<n; i++)
            {
                printf("Podaj %d element: ", i+1);
                scanf("%d", &tab[i]);
            }

            printf("elementy przed sortowaniem: \n");
            for(i=0; i<n; i++)
            {
                printf("%d\n", tab[i]);
            }


            sortowanie_przez_wstawianie(n, tab);

            printf("elementy posortowane: \n");
            for(i=0; i<n; i++)
            {
                printf("%d\n", tab[i]);
            }
        }
        break;
        case 2:
        {
            for(i=0; i<n; i++)
            {
                printf("Podaj %d element: ", i+1);
                scanf("%d", &tab[i]);
            }

            printf("elementy przed sortowaniem: \n");
            for(i=0; i<n; i++)
            {
                printf("%d\n", tab[i]);
            }


            sortowaniebabelkowe(tab, n);

            printf("elementy posortowane: \n");
            for(i=0; i<n; i++)
            {
                printf("%d\n", tab[i]);
            }

            break;

        }
        case 3:
        {
            for(i=0; i<n; i++)
            {
                printf("Podaj %d element: ", i+1);
                scanf("%d", &tab[i]);
            }

            printf("elementy przed sortowaniem: \n");
            for(i=0; i<n; i++)
            {
                printf("%d\n", tab[i]);
            }


            selectionsort(tab, n);

            printf("elementy posortowane: \n");
            for(i=0; i<n; i++)
            {
                printf("%d\n", tab[i]);
            }
        }
        break;

        case 4:
            {
                for(i=0; i<n; i++)
            {
                printf("Podaj %d element: ", i+1);
                scanf("%d", &tab[i]);
            }

            printf("elementy przed sortowaniem: \n");
            for(i=0; i<n; i++)
            {
                printf("%d\n", tab[i]);
            }


            quicksort(tab, 0, n-1);

            printf("elementy posortowane: \n");
            for(i=0; i<n; i++)
            {
                printf("%d\n", tab[i]);
            }
            }
        }break;
    }
    case 2:
    {
        printf("Wybierz metode sortowania\n");
        printf("1-Sortowanie Karciane, 2-Bubble Sort, 3-Selection Sort, 4-Quicksort");
        printf("\nTwoj wybor: ");
        scanf("%d", &d);
        switch(d)
        {
        case 1:
        {
            x=1234;
            srand(x);
            printf("Wartosci liczbowe przed posortowaniem: ");
            for(i=0; i<n; i++)
            {
                tab[i]=rand()%1001;
                printf("\n%d  ", tab[i]);
            }
            sortowanie_przez_wstawianie(n, tab);
            printf("\n\nPo posortowaniu: \n");
            for(i=0; i<n; i++)
            {
                printf("\n%d  ", tab[i]);
            }
            break;
        }
        case 2:
        {
            x=1634;
            srand(x);
            printf("Wartosci liczbowe przed posortowaniem: ");
            for(i=0; i<n; i++)
            {
                tab[i]=rand()%1001;
                printf("\n%d  ", tab[i]);
            }
            sortowaniebabelkowe(tab, n);

            printf("\n\nPo posortowaniu: \n");
            for(i=0; i<n; i++)
            {
                printf("\n%d  ", tab[i]);
            }
            break;
        }
        case 3:
        {
            x=9999;
            srand(x);
            printf("Wartosci liczbowe przed posortowaniem: ");
            for(i=0; i<n; i++)
            {
                tab[i]=rand()%1001;
                printf("\n%d  ", tab[i]);
            }
            selectionsort(tab, n);

            printf("\n\nPo posortowaniu: \n");
            for(i=0; i<n; i++)
            {
                printf("\n%d  ", tab[i]);
            }
            break;
        }
        case 4:
            {
                x=9119;
            srand(x);
            printf("Wartosci liczbowe przed posortowaniem: ");
            for(i=0; i<n; i++)
            {
                tab[i]=rand()%1001;
                printf("\n%d  ", tab[i]);
            }
            quicksort(tab, 0, n-1);

            printf("\n\nPo posortowaniu: \n");
            for(i=0; i<n; i++)
            {
                printf("\n%d  ", tab[i]);
            }
            }break;
        }
    }
    break;
    }
    return 0;
}