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:

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

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!

Kategorie wpisów

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

W dniach od 13.06.2024 do 17.06.2024 trwa w Videopoint.pl promocja urodzinowa - oprócz wielu zniżek mamy też możliwość odebrania darmowego kursu! Można odebrać jeden videokurs z trzech: 1. "Mały szachista"; 2. "Wejście w świat IT"; 3. "Angielski dla inżynierów i techników". Warto korzystać - Zobacz promocję na 9 urodziny Videopoint.pl

Bądź na bieżąco
Pasja informatyki