Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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 =(int*) 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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement