Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2020
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.63 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. #define ROZMIAR_TABLICY 10000000
  6. #define ZAKRES_LICZB_OD -10
  7. #define ZAKRES_LICZB_DO 10
  8.  
  9. void quickSort( int* tablica, int lewy, int prawy);
  10. int podzialTablicy( int* tablica, int lewy, int prawy);
  11. void zamien( int* a, int* b);
  12.  
  13. int main( int argc, char* argv[]){
  14. // sprawdz czy zakres danych liczb jest poprawny
  15. if( ZAKRES_LICZB_OD > ZAKRES_LICZB_DO){
  16. printf("Podano bledny zakres liczb\n");
  17. return 0;
  18. }
  19. // wybieź ziarno liczb pseudolosowych
  20. srand( time(0));
  21.  
  22. // zaalokuj tablice dynamiczna
  23. int* tablica =(int*) malloc( ROZMIAR_TABLICY*sizeof(int));
  24. if( tablica == NULL){ // blad alokacji
  25. printf( "nie udalo sie zaalokowac tak duzego liniowego obszaru pamieci na stercie\n");
  26. return 0;
  27. }
  28. // wypelnij tablice losowymi liczbami
  29. for( int i=0; i<ROZMIAR_TABLICY; i++){
  30. tablica[i] = rand() % ( ZAKRES_LICZB_DO - ZAKRES_LICZB_OD) + ZAKRES_LICZB_OD;
  31. }
  32.  
  33. // // wyswietl zawartosc tablicy przed posortowaniem
  34. // for( int i=0; i<ROZMIAR_TABLICY; i++){
  35. // printf("%d, ", tablica[i]);
  36. // }
  37. // printf("\n");
  38.  
  39. clock_t stoper; // zmienna do mierzenia czasu wykoniania
  40. stoper = clock(); // rozpocznij mierzenie czasu wykoniania
  41. // posortuj tablice
  42. quickSort( tablica, 0, ROZMIAR_TABLICY-1);
  43. stoper = clock() - stoper; // zakoncz mierzenie czasu wykoniania
  44. double stoperSekundy = ((double)stoper)/CLOCKS_PER_SEC;; // przekonwertuj na sekundy
  45. printf( "Czas wykonania to: %f sekund \n", stoperSekundy);
  46.  
  47. // // wyswietl zawartosc tablicy po posortowaniu
  48. // for( int i=0; i<ROZMIAR_TABLICY; i++){
  49. // printf("%d, ", tablica[i]);
  50. // }
  51. // printf("\n");
  52.  
  53. return 0;
  54. }
  55.  
  56. void quickSort( int* tablica, int lewy, int prawy){
  57. // warunki brzegowe
  58. if( lewy >= prawy) return;
  59. if( lewy < 0) return;
  60. if( prawy >= ROZMIAR_TABLICY) return;
  61.  
  62. // podziel tablice na elementy przed i za pivotem
  63. int nowyIdxPivota = podzialTablicy( tablica, lewy, prawy);
  64.  
  65. // posortuj rekurencyjnie elementy przed i za pivotem
  66. quickSort( tablica, lewy, nowyIdxPivota-1);
  67. quickSort( tablica, nowyIdxPivota, prawy);
  68. }
  69.  
  70. // podziel tablice tak, zeby elementy mniejsze od pivota znajdowaly sie na lewo od niego, a wieksze na prawo
  71. // podzial powinien wykonywac sie w czasie liniowym
  72. int podzialTablicy( int* tablica, int lewy, int prawy){
  73. int pivot = tablica[ (prawy+lewy)/2 ]; // strategia wybierania pivota (srodkowy element)
  74. int przedPivotem = lewy; // sledzi indeks od lewej najwiekszego elementu przed pivotem; wszystkie elementy o indeksie mnieszym niz przedPivotem sa mniejsze od pivota
  75. int zaPivotem = prawy; // sledzi indeks od prawej najmniejszego elementu za pivotem; wszystkie elementy o indeksie wiekszym niz zaPivotem sa wieksze od pivota
  76. while( przedPivotem <= zaPivotem){
  77. while( tablica[przedPivotem] < pivot) przedPivotem++; // znajdz nastepny przedPivotem
  78. while( pivot < tablica[zaPivotem]) zaPivotem--; // znajdz nastepny zaPivotem
  79. if( przedPivotem <= zaPivotem){
  80. zamien( &tablica[przedPivotem], &tablica[zaPivotem]);
  81. przedPivotem++;
  82. zaPivotem--;
  83. }
  84. }
  85. // po zakonczeniu podzialu, przedzial indeksow [przedPivotem, zaPivotem] to kandydaci na nowe miejsca na pivot wg wybranej strategii
  86. return przedPivotem; // dowolny indeks z przedzialu [przedPivotem, zaPivotem]
  87. }
  88.  
  89. // funkcja do zamiany dwóch wartości
  90. void zamien( int* a, int* b){
  91. int tmp;
  92. tmp = *b;
  93. *b = *a;
  94. *a = tmp;
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement