14. Sortowanie. Złożoność algorytmów
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.
Znajdź w filmie
Tutoriale posiadają tzw. timestamps (chwile czasowe) - dzięki nim łatwo odnajdziesz interesujące fragmenty wiedzy. Wystarczy kliknąć na podane w nawiasach kwadratowych momenty filmu, by przewinąć tutorial dokładnie do interesującego Cię miejsca w odcinku.
[ 00:00:00 ] Wstęp
[ 00:02:20 ] Sortowanie danych
[ 00:04:08 ] Sortowanie bąbelkowe
[ 00:09:38 ] Zastosowanie bufora
[ 00:11:17 ] Pisanie sortującego algorytmu bąbelkowego
[ 00:20:30 ] Szybkość sortowania bąbelkowego
[ 00:21:40 ] Sortowanie quicksort
[ 00:24:50 ] Algorytm partycjonujący
[ 00:28:50 ] Pisanie sortującego algorytmu quicksort
[ 00:32:07 ] Porównanie szybkości obu algorytmów
[ 00:34:26 ] Efektywność algorytmu
[ 00:36:57 ] Mierzenie zdolności algorytmów
[ 00:44:09 ] Zadanie domowe
Komentarze
Czy macie jakieś pytania, sugestie, uwagi? A może zauważyliście literówkę albo błąd? Dajcie koniecznie znać: kontakt@pasja-informatyki.pl. Dziękujemy za poświęcony czas - to dzięki Wam serwis staje się coraz lepszy!