Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek,  wersja1.0

©2010 mgr Jerzy Wałaszek I LO w Tarnowie

Sortowanie Szybkie - QuickSort

Profesor Tony Hoare jest autorem bardzo szybkiego algorytmu sortującego, który obecnie stosuje się powszechnie. Algorytm ten nosi nazwę Sortowania Szybkiego (ang. QuickSort) i opiera się na zasadzie dziel i zwyciężaj (ang. divide and conquer). Działanie algorytmu jest następujące:

Pierwszy element zbioru traktujemy jako element zwrotny, pivot. Zbiór T dzielimy na dwie partycję T_L i T_{P, tak aby} w lewej partycji T_L znalazły się elementy mniejsze od pivotu, a w prawej T_P elementy większe. Podziału dokonujemy za pomocą funkcji podziel(), którą opisaliśmy dokładnie w poprzednim rozdziale.

Zwróć uwagę, iż po takim podziale pivot p trafia na właściwe miejsce. W zbiorze uporządkowanym znajdzie się on na tej właśnie pozycji. Pozostałe elementy nie są jeszcze uporządkowane. Dlatego rekurencyjnie dzielimy każdą z partycji T_L i T_P na dalsze partycje tą samą funkcją podziel(). Po każdym takim podziale elementy pivotów trafiają na właściwe miejsca. Rekurencję przerywamy, gdy danej partycji nie można już dalej dzielić, ponieważ jest albo jednoelementowa, albo pusta.

Partycję będziemy określać za pomocą dwóch indeksów, i_p - pierwszy element, i_k - ostatni element. Dopóki jest spełniony warunek:

i_p < i_k

partycja może być dzielona na dwie partycje lewą i prawą. Warunek ten będziemy sprawdzać na początku funkcji sortuj_szybko(). Pozwoli nam on zakończyć rekurencję. Ponieważ pivoty układają się na właściwych miejscach, to po osiągnięciu końca rekurencji, wszystkie elementy zbioru będą pivotami i zbiór zostanie posortowany.

Algorytm sortowania szybkiego posiada liniowo logarytmiczną klasę złożoności obliczeniowej O(n log n). Jest to bardzo korzystne i pozwala efektywnie sortować duże zbiory danych.

Algorytm funkcji sortuj_szybko(T,i_p,i_k)

Wejście

Wyjście:

Posortowana tablica T[ ]

Zmienne pomocnicze:

Lista kroków quicksort(T, i_p, i_k)

Przykładowe dane dla programu

Pierwsza liczba określa liczbę elementów n. Następne n  liczb całkowitych jest zawartością zbioru.

510
463 926 603 901 826 879 376 264 189 472 582 447 664 547 702
453 401 398 930 907 177 256 105 429 63 995 437 638 190 16
16 320 40 141 523 284 138 405 17 318 257 543 651 378 278
9 27 805 962 204 390 387 382 210 32 64 128 100 150 200
4 12 32 530 35 125 450 41 316 301 15 246 849 844 165
27 959 14 21 8 876 539 948 662 5 13 32 254 577 888
452 715 691 81 725 359 361 381 263 793 144 412 137 119 476
496 189 467 149 377 714 273 443 490 81 976 255 180 71 703
620 161 978 849 678 964 935 188 602 63 659 111 182 245 712
31 9 8 603 178 832 743 916 341 87 65 646 707 830 612
63 877 495 149 290 2 698 166 227 400 476 941 786 129 71
919 820 502 828 481 943 815 70 415 413 484 1 329 250 78
915 466 401 641 802 543 331 766 934 487 786 868 951 768 886
231 762 74 269 508 985 134 328 371 937 531 756 470 464 488
926 25 502 261 339 115 67 962 399 68 882 863 996 791 924
742 13 370 448 183 531 147 41 546 768 318 120 522 466 628
756 968 58 358 592 421 638 978 980 988 444 85 118 831 48
858 754 281 344 210 703 84 885 844 685 148 389 927 84 956
103 310 782 175 614 523 496 897 562 399 924 896 539 328 995
685 336 548 961 15 175 982 120 300 100 583 228 588 672 950
68 232 659 587 909 967 218 608 838 779 343 873 980 478 572
950 944 395 754 598 994 26 689 399 342 3 4 5 982 730
985 780 160 816 933 628 433 414 845 646 322 450 716 849 619
669 855 278 173 687 471 304 460 377 424 10 7 20 130 721
883 654 47 145 224 771 927 320 579 38 361 773 661 662 155
335 9 159 283 49 971 963 318 913 431 811 266 374 861 284
232 672 564 888 932 484 973 226 143 344 962 110 444 532 646
16 3 29 14 83 874 871 401 381 473 538 908 58 760 20
969 120 160 40 584 176 598 110 358 443 822 403 198 46 199
643 614 574 5 8 13 4 8 3 143 703 7 242 50 61
34 487 526 290 818 219 968 710 894 510 180 447 708 226 296
782 314 932 211 169 67 824 127 90 508 138 350 824 799 882
713 212 335 223 990 735 502 743 363 434 484 509 782 166 512
565 654 934 364 397 168 4 5 6 603 524 183 303 789 399

// Sortowanie szybkie
// (C)2010 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

// Funkcja dokonuje podziału na partycje
// względem pierwszego elementu. Zwraca jako wynik
// pozycję elementu pierwszego po podziale
//------------------------------------------------

int podziel(int * T, int ip, int ik)
{
    int v,x,i,j;

    v = T[ip]; i = ip; j = ik + 1;

    while(i < j)
    {
        while(T[++i] < v);
        while(v < T[--j]);
        if(i < j)
        {
            x = T[i]; T[i] = T[j]; T[j] = x;
        }
    }

    T[ip] = T[j]; T[j] = v;

    return j; 
}

// Funkcja sortuje szybko zbiór

void sortuj_szybko(int * T, int ip, int ik)
{
    if(ip < ik)
    {
        int p = podziel(T, ip, ik);
        sortuj_szybko(T, ip, p - 1);
        sortuj_szybko(T, p + 1, ik);
    }
}

int main()
{
    int * T,n,i;

    // odczytujemy liczbę elementów

    cin >> n;

    // tworzymy tablicę dynamiczną o n elementach

    T = new int[n + 1];

    // wczytujemy elementy do tablicy

    for(i = 0; i < n; i++) cin >> T[i];

    // umieszczamy strażnika

    T[n] = 2147483647;

    // sortujemy

    sortuj_szybko(T, 0, n - 1);

    // wyświetlamy wyniki

    cout << endl << endl;

    for(i = 0; i < n; i++) cout << T[i] << " ";

    cout << endl << endl;

    // usuwamy tablicę dynamiczną

    delete [] T;

    return 0;
}

Zaprojektuj algorytm, który sortuje szybko malejąco. Napisz na podstawie tego algorytmu odpowiedni program.

---

I Liceum Ogólnokształcące    im. Kazimierza Brodzińskiego w Tarnowie ©2024 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe