Algorytmy sortowania danych – przegląd i porównanie wydajności

Sortowanie jest jednym z podstawowych problemów w informatyce. Polega na uporządkowaniu elementów zbioru według określonego kryterium (np. rosnąco lub malejąco). Wybór odpowiedniego algorytmu sortowania ma duże znaczenie, zwłaszcza w przypadku pracy z dużymi zbiorami danych. W artykule przedstawiono najważniejsze algorytmy sortowania, ich działanie oraz porównanie złożoności obliczeniowej.

1. Algorytmy proste

1.1 Sortowanie bąbelkowe (Bubble Sort)

• Idea: porównywanie sąsiednich elementów i zamiana ich miejscami, aż do uzyskania uporządkowanej listy.
• Złożoność:
  • Czasowa:
    • najlepszy przypadek: O(n) (dla już posortowanej tablicy),
    • średni i najgorszy przypadek: O(n²).
  • Pamięciowa: O(1).
• Zalety: prostota implementacji.
• Wady: bardzo niska wydajność przy większych zbiorach danych.

function bubbleSort(arr) {
  const a = [...arr];
  for (let i = 0; i < a.length; i++) {
    for (let j = 0; j < a.length - i - 1; j++) {
      if (a[j] > a[j+1]) {
        [a[j], a[j+1]] = [a[j+1], a[j]];
      }
    }
  }
  return a;
}

1.2 Sortowanie przez wstawianie (Insertion Sort)

• Idea: elementy są wstawiane kolejno na odpowiednie miejsce w już częściowo posortowanej tablicy.
• Złożoność:
  • najlepszy przypadek: O(n),
  • średni i najgorszy przypadek: O(n²).
• Zalety: dobre działanie dla małych lub częściowo posortowanych zbiorów.
• Wady: nieefektywne dla dużych zbiorów.

function insertionSort(arr) {
  const a = [...arr];
  for (let i = 1; i < a.length; i++) {
    let key = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > key) {
      a[j+1] = a[j];
      j--;
    }
    a[j+1] = key;
  }
  return a;
}

1.3 Sortowanie przez wybieranie (Selection Sort)

• Idea: w każdej iteracji wybierany jest najmniejszy element i przenoszony na początek.
• Złożoność:
  • zawsze: O(n²).
• Zalety: prostota implementacji, niewielka liczba zamian elementów.
• Wady: duża liczba porównań, mała wydajność.

function selectionSort(arr) {
  const a = [...arr];
  for (let i = 0; i < a.length; i++) {
    let minIdx = i;
    for (let j = i + 1; j < a.length; j++) {
      if (a[j] < a[minIdx]) minIdx = j;
    }
    if (minIdx !== i) {
      [a[i], a[minIdx]] = [a[minIdx], a[i]];
    }
  }
  return a;
}

1.4 Comb Sort

• Idea: Rozwinięcie Bubble Sort. Zamiast porównywać sąsiednie elementy, porównuje elementy w pewnym odstępie („gap”), który maleje z każdą iteracją (najczęściej przez współczynnik ok. 1.3). Usuwa tzw. „żółwie” — małe wartości przesuwające się bardzo wolno na początek.
• Złożoność:
  • Średnia: około O(n² / 2ᵖ), gdzie p to liczba iteracji (zwykle lepsza niż Bubble),
  • Najgorszy przypadek: O(n²),
  • Najlepszy przypadek: O(n log n) (dla bardzo dobrze dobranego współczynnika).
• Wady: Nadal kwadratowa złożoność dla dużych danych. Nie jest stabilny. Wymaga dobrania optymalnego współczynnika „shrink”.

function combSort(arr) {  
  const a = [...arr];
  const shrink = 1.3;
  let gap = a.length;
  let swapped = true;

  while (gap > 1 || swapped) {
    gap = Math.floor(gap / shrink);
    if (gap < 1) gap = 1;

    swapped = false;
    for (let i = 0; i + gap < a.length; i++) {      
      if (a[i] > a[i + gap]) {
        [a[i], a[i + gap]] = [a[i + gap], a[i]];
        swapped = true;        
      }
    }
  }

  return a;
}

1.5 Shell Sort

• Idea: Ulepszony Insertion Sort — zaczyna od porównywania elementów oddzielonych dużym odstępem (tzw. gap), który w każdej iteracji maleje. Dzięki temu szybko przesuwa elementy blisko właściwego miejsca.
• Złożoność:
  • Średnia: od O(n log n) do O(n^1.5) w zależności od przyjętej sekwencji odstępów,
  • Najgorszy przypadek: O(n²), *Najlepszy przypadek (już prawie posortowana tablica): O(n log n).
• Wady: Złożoność trudna do dokładnego określenia (zależna od sekwencji odstępów). Nie jest algorytmem stabilnym (elementy równe mogą zmienić kolejność).

function shellSort(arr) {  
  const a = [...arr];
  let gap = Math.floor(a.length / 2);

  while (gap > 0) {
    for (let i = gap; i < a.length; i++) {
      const temp = a[i];
      let j = i;

      while (j >= gap && a[j - gap] > temp) {
        a[j] = a[j - gap];        
        j -= gap;
      }

      a[j] = temp;      
    }
    gap = Math.floor(gap / 2);
  }

  return a;
}

1.6 Bogo Sort

• Idea: Najbardziej nieefektywny (i żartobliwy) algorytm sortowania. Polega na losowym tasowaniu elementów tablicy aż do momentu, gdy tablica przypadkowo stanie się posortowana.
• Złożoność: Średnio i w najgorszym przypadku ma złożoność O(n!), ponieważ w najgorszym razie trzeba sprawdzić wszystkie możliwe permutacje.
• Wady: Ekstremalnie wolny i nieprzewidywalny.

W praktyce bezużyteczny (stosowany tylko edukacyjnie lub humorystycznie). Może nie zakończyć się w rozsądnym czasie dla nawet małych tablic (np. n > 6).

function bogoSort(arr) {  
  const a = [...arr];

  function isSorted(a) {
    for (let i = 1; i < a.length; i++) {
      if (a[i - 1] > a[i]) return false;
    }
    return true;
  }

  function shuffle(a) {
    for (let i = a.length - 1; i > 0; i--) {
      const j = Math.floor(Math.random() * (i + 1));
      [a[i], a[j]] = [a[j], a[i]];
    }
  }

  let safety = 10000; // zabezpieczenie przed nieskończoną pętlą

  while (!isSorted(a) && safety-- > 0) {
    shuffle(a);
  }

  return a;
}

2. Algorytmy zaawansowane

2.1 Sortowanie szybkie (Quick Sort)

• Idea: wybór elementu (pivot), podział tablicy na dwie części i rekurencyjne sortowanie podtablic.
• Złożoność:
  • najlepszy i średni przypadek: O(n log n),
  • najgorszy przypadek: O(n²) (dla źle dobranego pivota).
• Pamięciowa: O(log n) (rekurencja).
• Zalety: bardzo szybki w praktyce.
• Wady: wrażliwy na wybór pivota.

function quickSort(arr) {
  const a = [...arr];
  quickRec(a, 0, a.length - 1);
  return a;

  function quickRec(a, lo, hi) {
    if (lo < hi) {
      const p = partition(a, lo, hi);
      quickRec(a, lo, p - 1);
      quickRec(a, p + 1, hi);
    }
  }

  function partition(a, lo, hi) {
    const pivot = a[hi];
    let i = lo;
    for (let j = lo; j < hi; j++) {
      if (a[j] < pivot) {
        [a[i], a[j]] = [a[j], a[i]];
        i++;
      }
    }
    [a[i], a[hi]] = [a[hi], a[i]];
    return i;
  }
}

2.2 Sortowanie przez scalanie (Merge Sort)

• Idea: dziel i zwyciężaj – dzielenie tablicy na mniejsze części i scalanie posortowanych fragmentów.
• Złożoność:
  • zawsze: O(n log n).
• Pamięciowa: O(n) (potrzebne dodatkowe tablice).
• Zalety: stabilność, przewidywalny czas działania.
• Wady: wymaga dodatkowej pamięci.

function mergeSort(arr) {
  const a = [...arr];
  mergeRec(a, 0, a.length - 1);
  return a;

  function mergeRec(a, l, r) {
    if (l >= r) return;
    const m = Math.floor((l + r) / 2);
    mergeRec(a, l, m);
    mergeRec(a, m+1, r);
    merge(a, l, m, r);
  }

  function merge(a, l, m, r) {
    const left = a.slice(l, m+1);
    const right = a.slice(m+1, r+1);
    let i = 0, j = 0, k = l;
    while (i < left.length && j < right.length) {
      if (left[i] <= right[j]) {
        a[k++] = left[i++];
      } else {
        a[k++] = right[j++];
      }
    }
    while (i < left.length) { a[k++] = left[i++]; }
    while (j < right.length) { a[k++] = right[j++]; }
  }
}

2.3 Sortowanie przez kopcowanie (Heap Sort)

• Idea: budowa kopca i wyciąganie największego elementu, aż do uzyskania posortowanej listy.
• Złożoność:
  • zawsze: O(n log n).
• Pamięciowa: O(1).
• Zalety: przewidywalność, brak dodatkowej pamięci.
• Wady: wolniejszy od Quick Sorta w praktyce.

function heapSort(arr) {
  const a = [...arr];
  const n = a.length;

  function heapify(n, i) {
    let largest = i;
    const l = 2*i + 1;
    const r = 2*i + 2;
    if (l < n) { if (a[l] > a[largest]) largest = l; }
    if (r < n) { if (a[r] > a[largest]) largest = r; }
    if (largest !== i) {
      [a[i], a[largest]] = [a[largest], a[i]];
      heapify(n, largest);
    }
  }

  // build heap
  for (let i = Math.floor(n/2) - 1; i >= 0; i--) heapify(n, i);
  // extract elements
  for (let i = n - 1; i > 0; i--) {
    [a[0], a[i]] = [a[i], a[0]];
    heapify(i, 0);
  }
  return a;
}

3. Algorytmy specjalne

3.1 Sortowanie przez zliczanie (Counting Sort)

• Idea: Zlicza, ile razy występuje każda wartość w tablicy, a następnie na tej podstawie odtwarza posortowany wynik. Działa tylko dla liczb całkowitych z ograniczonego zakresu.
• Złożoność:
  • Czasowa: O(n + k), gdzie k to zakres wartości (max - min + 1),
  • Przestrzenna: O(k) (dodatkowa tablica zliczeń).
• Wady: Nie działa na liczbach zmiennoprzecinkowych ani ciągach znaków bez modyfikacji. Nieskuteczny, gdy zakres wartości (k) jest dużo większy od liczby elementów (n).

function countingSort(arr) {  
  const a = [...arr];

  const min = Math.min(...a);
  const max = Math.max(...a);
  const count = Array(max - min + 1).fill(0);

  for (let i = 0; i < a.length; i++) {
    count[a[i] - min]++;    
  }

  let index = 0;
  for (let i = 0; i < count.length; i++) {
    while (count[i]-- > 0) {
      a[index++] = i + min;      
    }
  }

  return a;
}

3.2 Sortowanie kubełkowe (Bucket Sort)

• Idea: rozdzielanie elementów do kubełków (przedziałów), a następnie sortowanie w każdym kubełku i scalanie wyników.
• Złożoność: O(n + k), gdzie k to liczba kubełków.
• Wady: zależne od rozkładu danych.

function bucketSort(arr) {
  if (arr.length === 0) return [];

  // Tworzymy puste kubełki
  const numBuckets = Math.floor(Math.sqrt(arr.length)) || 1;
  const buckets = Array.from({ length: numBuckets }, () => []);

  // Znajdujemy minimalną i maksymalną wartość, by rozłożyć elementy proporcjonalnie
  const minValue = Math.min(...arr);
  const maxValue = Math.max(...arr);
  const range = maxValue - minValue || 1;

  // Rozdzielamy elementy do kubełków
  for (let num of arr) {
    const index = Math.floor(((num - minValue) / range) * (numBuckets - 1));
    buckets[index].push(num);
  }

  // Sortujemy każdy kubełek i łączymy w jedną tablicę
  return buckets.flatMap(bucket => bucket.sort((a, b) => a - b));
}

3.3 Sortowanie pozycyjne (Radix Sort)

• Idea: sortowanie według kolejnych cyfr/liczb znaczących.
• Złożoność: O(nk), gdzie k to liczba cyfr.
• Zalety: bardzo szybkie dla liczb całkowitych.
• Wady: ograniczone zastosowanie (nie działa bezpośrednio na wszystkich typach danych).

function radixSort(arr) {
  if (arr.length === 0) return [];

  const maxNum = Math.max(...arr);
  let divisor = 1;
  let result = [...arr];

  // Pętla przez kolejne miejsca dziesiętne
  while (Math.floor(maxNum / divisor) > 0) {
    const buckets = Array.from({ length: 10 }, () => []);

    for (let num of result) {
      const digit = Math.floor((num / divisor) % 10);
      buckets[digit].push(num);
    }

    result = buckets.flat();
    divisor *= 10;
  }

  return result;
}

4. Porównanie algorytmów sortowania

5. Playground - wypróbuj kod!

Wpisz JavaScript i sprawdź wynik bezpiecznie w odizolowanym środowisku.

6. Dla jakich danych najlepszy jest dany algorytm sortowania

7. Szybkie podsumowanie typu zastosowań

8. Szybkie wnioski

• Najbardziej uniwersalne: Quick Sort, Merge Sort, Heap Sort
• Najlepsze dla małych danych: Insertion Sort
• Najlepsze dla danych numerycznych z ograniczonym zakresem: Counting / Radix / Bucket
• Najgorszy w praktyce: Bogo Sort (czysto pokazowy)