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

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:

Polecamy: Sekurak Academy 2024

Sekurak Academy 2024

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp do materiałów z edycji Sekurak Academy z roku 2023! Przy zakupie możecie skorzystać z kodu: pasja-akademia w koszyku, uzyskując rabat -30% na bilety w wersji "Standard" - warto korzystać! Więcej szczegółów znajdziecie tutaj.

Książka: Wprowadzenie do bezpieczeństwa IT

Wprowadzenie do bezpieczeństwa IT

Niedawno wystartował dodruk świetnej, rozchwytywanej książki pt. "Wprowadzenie do bezpieczeństwa IT, Tom I" (około 940 stron). Mamy dla Was kod: pasja (wpisz go w koszyku), dzięki któremu otrzymacie 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla naszych Widzów! Jest to pierwszy tom serii o ITsec, który wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

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ę!

Komentarze

Disqus

Kategorie wpisów

Oto polecana książka warta Waszej uwagi.
Pełna lista polecanych książek jest tutaj.

Uwaga - w dniach od 18.03.2024 do 25.03.2024 trwa w Helion.pl wiosenna akcja promocyjna. Otrzymujemy zniżkę -35% na książki drukowane oraz -50% na ebooki. Zobacz promocję tutaj.

Bądź na bieżąco