Kurs C++ (#14) Sortowanie. Złożoność algorytmów

2014-04-19 | Mirosław Zelent

Sortowanie danych - jakże często potrzebujemy dokonać tej operacji w różnych aplikacjach; przykłady można by mnożyć w nieskończoność. My póki co znamy algorytm wyznaczania największej liczby, no ale to nie jest to samo co sortowanie. W sortowaniu trzeba ułożyć np. liczby w tablicy rosnąco, co oznacza, że nie wystarczy wyciągnąć najmniejszej liczby z podanych - nie, my musimy ułożyć każdą z nich na odpowiednim miejscu. Oczywiście ludzie zajmują się sortowaniem danych nie od dzisiaj - i dlatego posłużymy się znanymi algorytmami, choć oczywiście wyjaśnimy je bardzo szczegółowo.

Wybrałem dwa algorytmy - jeden nazywa się sortowaniem bąbelkowym (bubble sort), a drugi nazywa się sortowaniem szybkim (quicksort). Metoda bąbelkowa jest bardzo intuicyjna, ale niestety także bardzo wolna. Z kolei sortowanie szybkie to już ekstraklasa wśród algorytmów sortowania - jest piekielnie szybki i sprytnie pomyślany. A jedyna różnica pomiędzy nimi to pomysł na jaki wpadli programiści. Dlatego będzie to ciekawe porównanie, m.in. zmierzymy tym algorytmom czas i pozwolimy się im ze sobą pościgać w sortowaniu dokładnie tych samych tablic. A na koniec powiemy o złożoności czasowej algorytmów i tzw. notacji dużego O.

Pobierz pliki źródłowe z odcinka: