14. Sortowanie. Złożoność algorytmów

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.

Pliki do odcinka

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

Poprzedni wpis

Następny wpis

Zobacz także

Daj się zaskoczyć! Poniżej wylosowałem dla Ciebie pięć wpisów z innych kategorii blogowych aniżeli ta, którą właśnie przeglądasz:

Zamów książki o IT sec z kodem: pasja

Można już zamawiać dwa tomy książek "Wprowadzenie do bezpieczeństwa IT". Mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy aż 15% zniżki! Dziękujemy ekipie Sekuraka za fajny rabat dla naszej Społeczności! Zamówień można dokonywać tutaj:

Tom 1 Tom 2

Pomóż dzieciom

Polska Akcja Humanitarna od wielu lat dożywia dzieci. Proszę, poświęć teraz dosłownie chwilę i pomóż klikając w oznaczony strzałką zielony brzuszek Pajacyka. Dziękuję!

Kategorie wpisów