[AiSD] 2. Sortowanie

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <math.h>
using namespace std;

const int N = 10;
int tab[N]={};
int mergeTab[N];
int pozTab[N];

void wypelnij()
{
    srand( time( NULL ) );
    for(int i = 0; i< N; i++)
        tab[i] = rand()%N;
}

void wypelnijPoz()
{
    srand( time( NULL ) );
    for(int i = 0; i< N; i++)
        pozTab[i] = rand()%899+100;
}

void wypisz(int tab[])
{
    for(int i = 0; i< N; i++)
        cout<<tab[i]<<" ";
    cout<<endl;
}

void proste_wybieranie()
{
    cout<<"[PROSTE WYBIERANIE] \t";
    int minimum;
    for(int i = 0; i < N-1; i++)
    {
        minimum = i;
        for(int j = i+1; j < N; j++)
            if(tab[j] < tab[minimum])
                minimum = j;
        swap(tab[i],tab[minimum]);
    }
}

void proste_wstawianie()
{
    cout<<"[PROSTE WSTAWIANIE] \t";
    int x, j;
    for(int i = 1; i < N; i++)
    {
        x = tab[i];
        j = i - 1;
        while(j >= 0 && x < tab[j])
        {
            tab[j+1] = tab[j];
            j -= 1;
        }
        tab[j+1] = x;
    }
}

void prosta_zamiana()
{
    cout<<"[PROSTA ZAMIANA] \t";
    for(int i = 1; i < N; i++)
        for(int j = N-1; j >= i; j--)
            if(tab[j] < tab[j-1])
                swap(tab[j],tab[j-1]);
}

void przez_zliczanie()
{
    cout<<"[PRZEZ ZLICZANIE] \t";
    int C[N]={};
    int tab2[N]={};
    for(int i = 0; i < N; i++)
        C[tab[i]] += 1;
    for(int i = 1; i < N; i++)
        C[i] += C[i-1];
    for(int i = N-1; i>=0; i--)
    {
        tab2[C[tab[i]]-1] = tab[i];
        C[tab[i]] -= 1;
    }
    wypisz(tab2);
}

int podzial(int lewy, int prawy)
{
    int x = tab[lewy];
    int i = lewy;
    int j = prawy;
    while(true)
    {
        while(tab[j] > x)
            j--;
        while(tab[i] < x)
            i++;
        if(i < j)
        {
            swap(tab[i],tab[j]);
            i++;
            j--;
        }
        else
            return j;   //pkt podzialu tablicy
    }
}

void QuickSort(int lewy, int prawy)
{
    if(lewy < prawy)
    {
        int p = podzial(lewy, prawy);
        QuickSort(lewy, p);
        QuickSort(p+1, prawy);
    }
}

void merge(int lewy, int prawy, int srodek)
{
    int i, j, q;
    for(i = lewy; i<= prawy; i++)
        mergeTab[i] = tab[i];
    i = lewy;
    j = srodek+1;
    q = lewy;
    while(i <= srodek && j <= prawy)
    {
        if(mergeTab[i] < mergeTab[j])
            tab[q++] = mergeTab[i++];
        else
            tab[q++] = mergeTab[j++];
    }
    while(i <= srodek)
        tab[q++] = mergeTab[i++];
}

void mergeSort(int lewy, int prawy)
{
    if(lewy < prawy)
    {
        int srodek = (lewy + prawy)/2;
        mergeSort(lewy, srodek);
        mergeSort(srodek+1, prawy);
        merge(lewy, prawy, srodek);
    }
}

void pozycyjne()
{
    int x, j;
    for(int l = 0; l < 3; l++)
    {
        int x, j;
        for(int i = 1; i < N; i++)
        {
            x = (int)(pozTab[i]/pow(10,l))%10;
            j = i - 1;
            while(j >= 0 && x < (int)(pozTab[j]/pow(10,l))%10)
            {
                pozTab[j+1] = pozTab[j];
                j -= 1;
            }
            pozTab[j+1] = pozTab[i];
        }
        //
        wypisz(pozTab);
    }
}

int main(){
    clock_t poczatek;
    clock_t koniec;
    double wynik;

    wypelnij();
    wypisz(tab);
    poczatek = clock();
    proste_wybieranie();
    koniec = clock();
    wynik = (double) (koniec - poczatek) /CLOCKS_PER_SEC;
    cout<<"\t"<<wynik<<"\t";
    wypisz(tab);

    wypelnij();
    proste_wstawianie();
    wypisz(tab);

    wypelnij();
    prosta_zamiana();
    wypisz(tab);

    wypelnij();
    przez_zliczanie();

    cout<<"[SORTOWANIE SZYBKIE] \t";
    wypelnij();
    QuickSort(0, N-1);
    wypisz(tab);

    cout<<"[PRZEZ SCALANIE] \t";
    wypelnij();
    mergeSort(0, N-1);
    wypisz(tab);

    wypelnijPoz();
    wypisz(pozTab);
    pozycyjne();



    return 0;
}