Lekcja 6 Sortowanie

Sortowanie to jedno z najważniejszych zagadnień w programowaniu. W JavaScript mamy wbudowaną metodę sort(), ale warto znać też klasyczne algorytmy sortowania, takie jak sortowanie bąbelkowe, quick sort czy merge sort.

1. Wbudowana metoda Array.sort()

Każda tablica w JavaScript ma metodę sort().

Podstawowe użycie

const liczby = [4, 2, 10, 1];
liczby.sort();
console.log(liczby); // [1, 10, 2, 4]  ❌ (alfabetycznie!)

Domyślnie sortowanie odbywa się jak tekst, dlatego wyniki mogą być zaskakujące.

Sortowanie liczbowe

const liczby = [4, 2, 10, 1];
liczby.sort((a, b) => a - b);
console.log(liczby); // [1, 2, 4, 10]

Funkcja porównująca zwraca:

• wartość ujemną → a przed b,

• 0 → bez zmian,

• wartość dodatnią → b przed a.

2. Sortowanie bąbelkowe (Bubble Sort)

Najprostszy do zrozumienia algorytm. Porównuje sąsiednie elementy i zamienia je miejscami, jeśli są w złej kolejności. Proces powtarza się aż do posortowania.

Kod:

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

console.log(bubbleSort([5, 2, 9, 1, 5, 6]));
// [1, 2, 5, 5, 6, 9]

Złożoność:

• Średnia i najgorsza: O(n²)

• Najlepsza (dla posortowanej tablicy z optymalizacją): O(n)

3. Sortowanie szybkie
(Quick Sort)

Jeden z najszybszych algorytmów sortowania.
Działa na zasadzie „dziel i zwyciężaj”:

1. Wybiera element pivot (np. środkowy).

2. Dzieli tablicę na mniejsze (mniejsze od pivot i większe od pivot).

3. Rekurencyjnie sortuje podtablice.

Kod:

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

console.log(quickSort([10, 7, 8, 9, 1, 5]));
// [1, 5, 7, 8, 9, 10]

Złożoność:

• Średnia: O(n log n)

• Najgorsza (źle dobrany pivot): O(n²)

4. Sortowanie przez scalanie
(Merge Sort)

Algorytm stabilny i przewidywalny.

1. Dzieli tablicę na pół, aż zostaną jednoelementowe tablice.

2. Scala je w jedną posortowaną.

Kod:

function merge(left, right) {
  let result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }

  return [...result, ...left.slice(i), ...right.slice(j)];
}

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

console.log(mergeSort([12, 11, 13, 5, 6, 7]));
// [5, 6, 7, 11, 12, 13]

Złożoność:

• Wszystkie przypadki: O(n log n)

• Minusem jest dodatkowa pamięć.

5. Inne popularne algorytmy sortowania

• Sortowanie przez wstawianie (Insertion Sort) – dobre dla małych tablic lub prawie posortowanych, O(n²).

• Sortowanie przez wybór (Selection Sort) – proste, ale powolne, O(n²).

• Heap Sort – używa kopca, O(n log n), mniej popularny w JS.

Podsumowanie

• Array.sort() – najszybszy w praktyce, bo implementowany w C++ w silniku JS (np. V8).

• Bubble Sort – edukacyjny, prosty, ale nieefektywny.

• Quick Sort – bardzo szybki dla dużych zbiorów.

• Merge Sort – stabilny i przewidywalny, kosztem dodatkowej pamięci.