Czym jest sortowanie danych? Podstawy dla początkujących

[Marcel_S]

Porządek w codziennym życiu jest czymś naturalnym. Układanie książek według gatunków lub nazwisk autorów to tylko pojedyncze przykłady sortowania, czyli problemu uporządkowania przedmiotów na podstawie ich cech.

Z sortowaniem spotykamy się każdego dnia, czym jest jednak sortowanie w informatyce? Źródło zdjęcia.

Otwierając szafkę ze sztućcami, najprawdopodobniej masz je posortowane w pojemniku. W lodówce zazwyczaj na poszczególne półki wkłada się konkretne typy pożywienia - nabiał, mięso, owoce… Sortowanie ułatwia nam życie, zapewniając nam organizację.

W IT to jeden z najważniejszych problemów algorytmiki, co potwierdza poświęcenie na ten temat jednego rozdziału w słynnej książce Sztuka Programowania autorstwa Donalda Knutha. Szybkie i efektywne sortowanie jest ważne. Dotyczy to szczególnie dużych baz danych, w których może być kilka tysięcy danych. 

Co sortuje się w informatyce?

Ogólnie sortuje się liczby. Oprócz tego można sortować znaki, łańcuchy znaków (napisy/stringi) i struktury danych (np. tablice i listy). Przykładem może być sortowanie bazy danych stacji pogodowej wykonanej przy użyciu Arduino. Jeżeli chcemy zobaczyć najcieplejsze dni w ciągu miesiąca to nie obędzie się bez sortowania.

Szybkość w algorytmach sortowania jest kluczowa. Niektóre algorytmy są szybsze od innych. Bogo sort może być przykładem nieefektywnego algorytmu. Polega on na losowym ustawianiu danych i liczeniu na to, że kiedyś się posortują. To tak, jakby mieć nieposortowaną talię kart, rozrzucić ją w powietrze, pozbierać i liczyć na to, że karty są ułożone od najmniejszej do największej wartości. Powtarza się to w kółko, aż karty spełnią nasze wymagania. Nie muszę chyba wyjaśniać, że to mało wydajny algorytm i nigdzie się go nie stosuje. Chociaż, jeżeli ktoś ma bardzo duże szczęście, to dane posortują się za pierwszym razem 🙂.

Im szybszy algorytm tym lepiej. Niestety zdarza się, że jest to związane z większym wykorzystaniem zasobów komputera, np. pamięci. Źródło zdjęcia.

 

Algorytmy, które powinieneś znać

Poniżej przedstawiam jedne z najpopularniejszych algorytmów. Nie wiesz czym jest algorytm? Zapraszam cię do przeczytania mojego artykułu Czym jest algorytm? Podstawy dla przyszłych programistów Arduino. Zakładam, że masz podstawową znajomość programowania, dlatego nie będę tu wyjaśniał, czym jest tablica, jak się odwołać do poszczególnego elementu, jak zapisuje się funkcje itp. Podkreślam, że w języku C tablice indeksuje się od 0!

Dobrze jest poznać kilka algorytmów sortowania, bo mogą się przydać w różnych projektach. Źródło zdjęcia.

Sortowanie bąbelkowe (ang. bubble sort)

Zaczynamy od najprostszego algorytmu, od którego zazwyczaj zaczyna się swoją przygodę z algorytmami sortowania.

Zasada działania

Nazwa nie jest myląca. Wzięła się ze specyficznego działania tego algorytmu. W szklance z napojem gazowanym większe bąbelki wypływają na powierzchnię, podczas gdy te mniejsze zostają na dole. Jest to analogia do danych w tablicy, które zachowują się w ten sam sposób. Te większe zostają wypchnięte na sam koniec, wyprzedzając mniejsze od siebie, oczywiście w przypadku sortowania rosnącego.

• Algorytm rozpoczyna od pobrania tablicy i jej wielkości
• Działanie odbywa się w dwóch pętlach. Jedna odpowiada za przejście przez tablicę tyle razy, ile jest elementów w tablicy, co umożliwia sortowanie każdego elementu osobno
• Druga pętla (zagnieżdżona) przechodzi przez tablicę i porównuje ze sobą kolejne dwa sąsiadujące ze sobą elementy
• Jeżeli aktualnie rozpatrywany element jest większy niż następny, to liczby są zamieniane ze sobą miejscami
• Po przejściu przez tablicę ostatni element jest posortowany, więc przy kolejnej iteracji porównuje się o tyle mniej elementów, ile razy już przeszliśmy przez tę tablicę

Implementacja w C

void bubbleSort (int tab[], int n) { // funkcja pobiera 'tablicę' i jej rozmiar

  int temp = 0; // zmienna pomocnicza służąca do zamiany liczb miejscami

  for (int i = 0; i < n; i++) {
    
    for (int j = 0; j < n-i-1; j++) { // przejście przez zagnieżdżoną pętlę jest pomniejszane o tyle razy ile przeszliśmy razy przez tablicę
      
      if (tab[j] > tab[j+1]) {        // jeżeli liczba jest wieksza od kolejnej...
      // ...to zamień je miejscami
        temp = tab[j];     // jedna zmienna jest kopiowana do zmiennej pomocniczej, zeby się "nie zgubiła"
        tab[j] = tab[j+1]; // zmienna o indeksie 'j' teraz ma wynosić tyle ile zmienna na pozycji 'j+1'...
        tab[j+1] = temp;   // ...a zmienna o indeksie 'j+1' tyle ile j
      }
    }
  }
}

Wizualizacja algorytmu bąbelkowego. 

Zielony kolor oznacza posortowane elementy. Z wizualizacji wynika, że im więcej jest posortowanych elementów, tym algorytm szybciej działa, dlatego dobrze się sprawdzi w niewielkich zbiorach danych.

Sortowanie przez wstawianie (ang. insertion sort)

Jest to względnie szybszy algorytm od sortowania bąbelkowego, ale nadal prosty do implementacji i zrozumienia.

Zasada działania

Algorytm opiera się na przejściu przez tablicę i wsadzeniu rozpatrywanego elementu w odpowiednie miejsce.

• Pobieramy tablicę i jej rozmiar
• Działanie odbywa się w dwóch pętlach
• Zmienna sterująca pierwszej pętli ‘i’ to granica, która dzieli tablicę na część posortowaną (elementy o indeksie mniejszym od ‘i’) i nieposortowaną (elementy większe lub równe od ‘i’)
• W drugiej pętli odbywa się cofanie przez tablicę z pierwszym elementem części nieposortowanej (klucz). Porównuje go i kolejne elementy posortowanej części. Klucz jest porównywany z ostatnim elementem, przedostatnim etc.
• Jednocześnie kolejne elementy z tej części są duplikowane o jeden indeks w prawo, tzn. na indeksie o jeden większym niż porównywany element pojawi się liczba o takiej samej wartości jak ten element. To pozwoli na wsadzenie sortowanej liczby w odpowiednie miejsce, nie gubiąc danych. Innymi słowy: przesuwa się elementy i robi miejsce na sortowaną liczbę
• Proces działa do momentu, aż klucz znajdzie indeks, na którym po jego lewej stronie znajdzie się mniejszy element lub równy, lub dojdzie do początku tablicy, co spowoduje wstawieniem go na indeks 0
• Zmienna ‘i’ się zwiększa i proces wstawiania rozpoczyna się od nowa

Implementacja w C

void insertionSort(int tab[], int n) {
  
  int klucz, j;

  for (int i = 1; i < n; i++) {
    klucz = tab[i]; // klucz to pierwszy element czesci nieposortowanej
    j = i - 1;

    while (j >= 0 && tab[j] > klucz) { // petla do cofania sie z kluczem
      tab[j+1] = tab[j]; // robimy miejsce dla klucza
      j = j - 1;
    }
    
    tab[j+1] = klucz; // petla sie zakonczyla czyli znaleziono miejsce dla klucza
  }
}

Wizualizacja

Na gifie widać jak sortowany element przemieszcza się po części posortowanej.

Sortowanie szybkie (ang. quick sort)

Funkcja rekurencyjna w pewnym momencie wywołuje samą siebie. Tworzy swoją kopię z innymi parametrami, podczas gdy stworzone wcześniej wywołania nadal pozostają w pamięci. Funkcja rekurencyjna musi mieć warunek stopu, który zatrzyma wykonywanie się kolejnych kopii. Zaletą pisania rekurencji jest czytelność i elegancja kodu, ale trzeba pamiętać o pamięciożerności takiego procesu.

Zasada działania

• W tym algorytmie korzysta się z pivota. Jest to element, według którego będzie sortowana tablica. Wybiera się go na samym początku algorytmu. Najczęściej jest to wartość środkowego elementu
• Iteruje się od początku i od końca tablicy. Lewy indeks nazwiemy ‘p’ a prawy ‘q’. 
• Iteruje się z dwóch stron dopóki nie znajdzie się elementu większego od pivota po lewej stronie i mniejszego po prawej
• Po znalezieniu takich liczb zamienia się je miejscami i powraca się do przechodzenia po tablicy
• Robi się to do momentu, aż lewy indeks będzie większy od prawego (p>q)
• Po tych operacjach pivot wyląduje na swoim miejscu
• Dzieli się tę tablicę na dwie tablice zawierające elementy na lewo od pivota i na prawo (metoda dziel i zwyciężaj)
• Z tymi tablicami postępuje się tak samo, włącznie z wybieraniem nowego pivota
• Wywołując funkcję podaje się jego lewy i prawy indeks. Są to granice według których sortuje się liczby tablicy

Implementacja w C

void quickSort(int tab[], int lewy, int prawy) {

  if (lewy < prawy) {
      int temp;
      int p = lewy;
      int q = prawy;
      int pivot = tab[(lewy + prawy) / 2]; // wybranie pivota jako srodkowego elementu tablicy

      while (p <= q) { // iterowanie z lewej strony...
          while (tab[p] < pivot) { // ...az znajdziemy element wiekszy od pivota
              p += 1;
          }

          while (tab[q] > pivot) { // iterowanie z prawej strony az znajdziemy element mniejszy od pivota
              q -= 1;
          }

          if (p <= q) {
              // zamiana elementow miejscami  
              temp = tab[p];
              tab[p] = tab[q];
              tab[q] = temp;
              
              p += 1;
              q -= 1;
          }
      }
      // rekurencja
      quickSort(tab, lewy, q);
      quickSort(tab, p, prawy);
  }
}

Wizualizacja

Jest to najszybszy algorytm, który do tej pory został omówiony. Wizualizację trzeba było bardzo mocno spowolnić, aby, cokolwiek zobaczyć. Gołym okiem widać rekurencję!

Szybkość algorytmów

Zużycie zasobów, takich jak czas i pamięć definiuje jak dobry jest algorytm. Zacznijmy zatem mierzyć!

1. Pomiar czasu wykonania algorytmów

Poniżej znajduje się przykład obliczenia czasu wykonywania algorytmu. Nie musisz tego kodu analizować, dla nas najważniejsze są wyniki.

// bubble sort
gettimeofday(&start, NULL);
bubbleSort(tabBubble, N); // N wielkosc tablicy
gettimeofday(&stop, NULL);
double czasBubble = (stop.tv_sec - start.tv_sec) * 1000000 + (stop.tv_usec - start.tv_usec);

Obliczana jest różnica czasu, która daje nam czas wykonania funkcji dla rozmiaru tablicy z losowymi elementami N = 100000. Oto wyjście pojedynczego wykonania kodu:

• Czas wykonania BUBBLE SORT: 25.754122
• Czas wykonania INSERTION SORT: 5.232003
• Czas wykonania QUICK SORT: 0.010057

Średnia z 5 pomiarów:

• Bubble sort: ~26 s.
• Insertion sort: ~5 s.
• Quick sort: ~0,01 s.

2. Notacja dużego O (ang. Big O notation)

Wszystko sprowadza się do jednego - złożoności algorytmu. Informuje ona, ile zasobów zostaje zużytych w trakcie wykonywania algorytmu. Zasobem może być czas lub pamięć.

Aby przedstawić złożoność, zapisuje się najpierw duże O, a następnie w nawiasach okrągłych liczbę zużytych zasobów w postaci wyrażenia matematycznego. Przykładowo:

• O(n) - algorytm zużywa n zasobów
• O(n^2) - zużycie n^2 zasobów

Im mniejsza złożoność obliczeniowa, tym algorytm jest lepszy.

Wykres przedstawiający złożoności obliczeniowe i ich ocena. Źródło zdjęcia.

Złożoności omawianych algorytmów:

• sortowanie bąbelkowe:
  • czasowa: O(n^2)
  • pamięciowa: O(1)
• sortowanie przez wstawianie
  • czasowa: O(n^2)
  • pamięciowa: O(1) 
• sortowanie szybkie:
  • czasowa:
    • zazwyczaj: O(n log n)
    • w przypadku pesymistycznym: O(n^2)
  • pamięciowa: O(log n)

3. Wnioski

Pomimo tej samej złożoności czasowej, algorytmy nie muszą wykonywać się w tym samym czasie.

W zależności od skomplikowania problemu, różne algorytmy przydadzą się do różnych sytuacji: Sortowanie bąbelkowe świetnie sprawdzi się do bardzo małych zbiorów danych, a do średnich i dużych zbiorów dobrze pomyśleć o wykorzystaniu sortowania szybkiego. Trzeba mieć na uwadze jego rekurencyjny charakter i złożoność pamięciową.

Podsumowanie

Wymienione zostały tylko 3 algorytmy. Tak naprawdę jest ich cała masa i każdy z nich posiada różne właściwości. Pisząc swój program i stając przed problemem nieposortowanego zbioru danych musisz pogodzić kilka kwestii: czas pisania i wykonywania algorytmu, zużycie pamięci i praktyczne zastosowanie. Istnieje także możliwość skorzystania z biblioteki, która oferuje jakąś funkcję sortowania. Wtedy warto sprawdzić, czy taka funkcja spełnia twoje wymagania.

Jeżeli jesteś ciekawy jak działają inne algorytmy sortowania, to zapraszam na mojego GitHuba, na którym znajdziesz program do wizualizacji takich właśnie algorytmów. Odsyłam cię również do mojego artykułu Algorytmy sortowania i ich realizacje w Python 3.

[Treker (Damian Szymański)]

@Marcel_S dziękuję za publikację kolejnego artykułu - mam nadzieję, że będzie pomocny dla początkujących. Plus za wizualizację algorytmów 🙂 

PS Informacyjnie dla innych użytkowników: zgodziłem się na umieszczenie w artykule linków do GitHuba i innych treści.

[Santiago]

Świetny artykuł. Mam tylko pewne zastrzeżenia do 

 ,Porządek w codziennym życiu jest czymś naturalnym' 😀

[H1M4W4R1]

46 minut temu, Santiago napisał:

 ,Porządek w codziennym życiu jest czymś naturalnym' 😀

Zgodnie z prawami termodynamiki wszystko dąży do chaosu 😉 

[Polecacz 101]

Produkcja i montaż PCB - wybierz sprawdzone PCBWay!
   • Darmowe płytki dla studentów i projektów non-profit
   • Tylko 5$ za 10 prototypów PCB w 24 godziny
   • Usługa projektowania PCB na zlecenie
   • Montaż PCB od 30$ + bezpłatna dostawa i szablony
   • Darmowe narzędzie do podglądu plików Gerber
Zobacz również » Film z fabryki PCBWay