Партиціювання — серце quicksort

Ти вже знаєш merge sort. Тут лише одна нова ідея — і коли вона клацне, увесь quicksort стане очевидним.

Зачіпка: де робиться робота?

І merge sort, і quicksort — це «розділяй і володарюй»: розбий масив, відсортуй частини, поєднай. Різниця в тому, коли робиться важка робота:

Отже єдине, що тобі справді треба зрозуміти нового — це partition. Решта quicksort — це знайома тобі рекурсія.

Що робить partition

Обираємо один елемент — pivot (тут: останній). Завдання: переставити масив так, щоб усі менші за pivot опинились ліворуч від нього, усі більші — праворуч. Після цього pivot стоїть на своєму фінальному місці й більше ніколи не рухається.

Схема Lomuto тримає один вказівник i — це межа «зони менших». Другий вказівник j просто йде по масиву. Щоразу, коли arr[j] < pivot, ми міняємо його в зону менших і розширюємо її (i++).

function partition(arr: number[], lo: number, hi: number): number {
  const pivot = arr[hi];          // pivot = останній елемент
  let i = lo;                     // межа зони "менших за pivot"
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {         // знайшли менший?
      [arr[i], arr[j]] = [arr[j], arr[i]];  // закидаємо в зону менших
      i++;                       // розширюємо зону
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];    // pivot на своє фінальне місце
  return i;                       // індекс, де тепер стоїть pivot
}

Проведи масив крізь partition сам

Натискай Крок і дивись, як j сканує, а зелена зона «менших» росте. Pivot — рожевий. У кінці pivot стрибає на межу.

Перевір розуміння

Збери повний quicksort

Тепер, коли partition зрозумілий, увесь алгоритм — три рядки рекурсії навколо нього:

function quicksort(arr: number[], lo = 0, hi = arr.length - 1): number[] {
  if (lo < hi) {
    const p = partition(arr, lo, hi);   // p стоїть на місці
    quicksort(arr, lo, p - 1);       // сортуємо менших
    quicksort(arr, p + 1, hi);       // сортуємо більших
  }
  return arr;
}

Зверни увагу: pivot p у рекурсію не входить — він уже на місці. Це і є та «безкоштовність» замість merge.