Sortier-Algorithmen

Bubble Sort — einfach, langsam

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

O(n²) — nur für sehr kleine Arrays oder Lehrzwecke.

Quick Sort — schnell im Schnitt

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[Math.floor(arr.length/2)];
  const links = arr.filter(x => x < pivot);
  const mitte = arr.filter(x => x === pivot);
  const rechts = arr.filter(x => x > pivot);
  return [...quickSort(links), ...mitte, ...quickSort(rechts)];
}

Durchschnitt O(n log n), Worst Case O(n²). Speicher: O(log n).

Merge Sort — stabil, garantiert O(n log n)

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)));
}
function merge(l, r) {
  const out = [];
  while (l.length && r.length) {
    out.push(l[0] <= r[0] ? l.shift() : r.shift());
  }
  return [...out, ...l, ...r];
}