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

#define ROZMIAR_TABLICY 10000000
#define ZAKRES_LICZB_OD -10
#define ZAKRES_LICZB_DO 10

void quickSort( int* tablica, int lewy, int prawy);
int  podzialTablicy( int* tablica, int lewy, int prawy);
void zamien( int* a, int* b);

int main( int argc, char* argv[]){
    // sprawdz czy zakres danych liczb jest poprawny
    if( ZAKRES_LICZB_OD > ZAKRES_LICZB_DO){
        printf("Podano bledny zakres liczb\n");
        return 0;
    }
    // wybieź ziarno liczb pseudolosowych
    srand( time(0));

    // zaalokuj tablice dynamiczna
    int* tablica = malloc( ROZMIAR_TABLICY*sizeof(int));
    if( tablica == NULL){ // blad alokacji
        printf( "nie udalo sie zaalokowac tak duzego liniowego obszaru pamieci na stercie\n");
        return 0;
    }
    // wypelnij tablice losowymi liczbami
    for( int i=0; i<ROZMIAR_TABLICY; i++){
        tablica[i] = rand() % ( ZAKRES_LICZB_DO - ZAKRES_LICZB_OD) + ZAKRES_LICZB_OD;
    }

    // // wyswietl zawartosc tablicy przed posortowaniem
    // for( int i=0; i<ROZMIAR_TABLICY; i++){
    //     printf("%d, ", tablica[i]);
    // }
    // printf("\n");

    clock_t stoper; // zmienna do mierzenia czasu wykoniania
    stoper = clock(); // rozpocznij mierzenie czasu wykoniania
    // posortuj tablice
    quickSort( tablica, 0, ROZMIAR_TABLICY-1);
    stoper = clock() - stoper; // zakoncz mierzenie czasu wykoniania
    double stoperSekundy = ((double)stoper)/CLOCKS_PER_SEC;; // przekonwertuj na sekundy
    printf( "Czas wykonania to: %f sekund \n", stoperSekundy);

    // // wyswietl zawartosc tablicy po posortowaniu
    // for( int i=0; i<ROZMIAR_TABLICY; i++){
    //     printf("%d, ", tablica[i]);
    // }
    // printf("\n");

    return 0;
}

void quickSort( int* tablica, int lewy, int prawy){
    // warunki brzegowe
    if( lewy >= prawy) return;
    if( lewy < 0) return;
    if( prawy >= ROZMIAR_TABLICY) return;

    // podziel tablice na elementy przed i za pivotem
    int nowyIdxPivota = podzialTablicy( tablica, lewy, prawy);

    // posortuj rekurencyjnie elementy przed i za pivotem
    quickSort( tablica, lewy, nowyIdxPivota-1);
    quickSort( tablica, nowyIdxPivota, prawy);
}

// podziel tablice tak, zeby elementy mniejsze od pivota znajdowaly sie na lewo od niego, a wieksze na prawo
// podzial powinien wykonywac sie w czasie liniowym
int podzialTablicy( int* tablica, int lewy, int prawy){
    int pivot = tablica[ (prawy+lewy)/2 ]; // strategia wybierania pivota (srodkowy element)
    int przedPivotem = lewy; // sledzi indeks od lewej najwiekszego elementu przed pivotem; wszystkie elementy o indeksie mnieszym niz przedPivotem sa mniejsze od pivota
    int zaPivotem = prawy; // sledzi indeks od prawej najmniejszego elementu za pivotem; wszystkie elementy o indeksie wiekszym niz zaPivotem sa wieksze od pivota
    while( przedPivotem <= zaPivotem){
        while( tablica[przedPivotem] < pivot) przedPivotem++; // znajdz nastepny przedPivotem
        while( pivot < tablica[zaPivotem]) zaPivotem--; // znajdz nastepny zaPivotem
        if( przedPivotem <= zaPivotem){
            zamien( &tablica[przedPivotem], &tablica[zaPivotem]);
            przedPivotem++;
            zaPivotem--;
        }
    }
    // po zakonczeniu podzialu, przedzial indeksow [przedPivotem, zaPivotem] to kandydaci na nowe miejsca na pivot wg wybranej strategii
    return przedPivotem; // dowolny indeks z przedzialu [przedPivotem, zaPivotem]
}

// funkcja do zamiany dwóch wartości
void zamien( int* a, int* b){
    int tmp;
    tmp = *b;
    *b = *a;
    *a = tmp;
}