Insertion sort и selection sort в JavaScript

Проблем

Бавната страница с продуктите

Магазинът подрежда поръчките на деня по час за доставка, а админ страницата показва всички продукти по цена. И двете места ползват един и същ стар код:

function selectionSort(times) {
  for (let i = 0; i < times.length - 1; i++) {
    let best = i;
    for (let j = i + 1; j < times.length; j++) {
      if (times[j] < times[best]) {
        best = j;
      }
    }
    if (best !== i) {
      [times[i], times[best]] = [times[best], times[i]];
    }
  }
}

const today = ["14:30", "09:15", "11:00", "16:45", "10:30", "08:45"];
selectionSort(today);
console.log(today.join(" "));

08:45 09:15 10:30 11:00 14:30 16:45

За шест поръчки е мигновено. Но продуктите са 50 000, и страницата се отваря за секунди. Кодът намира най-малкия елемент в целия остатък, слага го отпред и повтаря. За 50 000 елемента това са 49 999 + 49 998 + … + 1 = 1 249 975 000 сравнения. Всеки път, даже когато продуктите вече са подредени и само два са разменени.

В урока са двата основни алгоритъма за сортиране: този, selection sort, и insertion sort. Ще ги броиш сравнение по сравнение и ще видиш кога всеки от тях е на място.

Идеята

Insertion sort: като карти в ръка

Така подреждаш карти в ръка. Вземаш следващата карта и я плъзгаш наляво, покрай по-големите, докато не стигне по-малка. Картите вляво от нея са винаги подредени.

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

key е поръчката, която се слага на място. j тръгва от поръчката вляво от нея. Докато поръчката на j е по-късна от key, тя се мести с едно надясно, а j слиза. Където цикълът спре, на j + 1 има дупка, и key влиза там.

В JavaScript times[j] > key сравнява низовете знак по знак. Часовете са с водеща нула (09:15), затова редът на текста е редът на часа.

const today = ["14:30", "09:15", "11:00", "16:45", "10:30", "08:45"];
insertionSort(today);
console.log(today.join(" "));

08:45 09:15 10:30 11:00 14:30 16:45

Виж го

Картите на място

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

Стъпка по стъпка, с думи

6 поръчки по час за доставка. Вляво расте подредената част: в началото е само първата поръчка, 14:30.
key = 09:15. 1 по-късна поръчка се мести с едно надясно, до самото начало, и 09:15 влиза на място 0. 1 сравнение.
key = 11:00. 1 по-късна поръчка се мести с едно надясно, до 09:15, и 11:00 влиза на място 1. 2 сравнения.
key = 16:45. 14:30 не е по-късно: нищо не се мести, и 16:45 влиза на място 3. 1 сравнение.
key = 10:30. 3 по-късни поръчки се местят с едно надясно, до 09:15, и 10:30 влиза на място 1. 4 сравнения.
key = 08:45. 5 по-късни поръчки се местят с едно надясно, до самото начало, и 08:45 влиза на място 0. 5 сравнения.
Подредено: 13 сравнения и 10 премествания. Почти подреденият списък на деня иска само 6 сравнения и 1 преместване.

Всяка карта прави толкова работа, колкото по-късни карти има пред нея в подредената част. 16:45 идва след всички и не мести нищо. 08:45 е по-рано от всички и мести всичките пет.

Пробвай

Преброй

Същият insertion sort, но всяко сравнение и всяко отместване се броят. Първо на поръчките от сцената, после на почти подреден списък: една поръчка е дошла малко след следващата.

function insertionSort(times) {
  let comparisons = 0;
  let shifts = 0;
  for (let i = 1; i < times.length; i++) {
    const key = times[i];
    let j = i - 1;
    while (j >= 0) {
      comparisons++;
      if (times[j] <= key) {
        break;
      }
      times[j + 1] = times[j];
      shifts++;
      j--;
    }
    times[j + 1] = key;
  }
  console.log(`Сравнения: ${comparisons}, премествания: ${shifts}`);
}

const today = ["14:30", "09:15", "11:00", "16:45", "10:30", "08:45"];
insertionSort(today);
console.log(today.join(" "));

const almost = ["08:45", "09:15", "11:00", "10:30", "14:30", "16:45"];
insertionSort(almost);

Сравнения: 13, премествания: 10
08:45 09:15 10:30 11:00 14:30 16:45
Сравнения: 6, премествания: 1

Разликата идва от това кога спира вътрешният цикъл. Ако поръчката вече е след всички вляво, едно сравнение стига. Затова:

най-добрият случай е подреден списък: n - 1 сравнения, нула отмествания. O(n);
най-лошият случай е обратно подреден: всяка поръчка минава до място 0, n(n - 1)/2 сравнения и толкова отмествания. O(n²);
на случаен вход всяка поръчка минава средно през половината подредена част: около n²/4. Пак O(n²).

Почти подреденият списък е близо до най-добрия случай: всяка разместена поръчка добавя едно-две сравнения.

Пробвай

Предвиди изхода

Поръчките вече са подредени. Какво печата броещият insertion sort?

const today = ["08:45", "09:15", "10:30", "11:00", "14:30", "16:45"];
insertionSort(today);

Отговор

Сравнения: 0, премествания: 0

Сравнения: 5, премествания: 0

Сравнения: 15, премествания: 0

Идеята

Selection sort: избери най-ранната

Старият код от началото прави друго. За място i преглежда целия остатък, намира най-ранната поръчка (индексът ѝ е best: най-добрата досега) и я разменя с поръчката на i. После място i не се пипа повече.

function selectionSort(times) {
  for (let i = 0; i < times.length - 1; i++) {
    let best = i;
    for (let j = i + 1; j < times.length; j++) {
      if (times[j] < times[best]) {
        best = j;
      }
    }
    if (best !== i) {
      [times[i], times[best]] = [times[best], times[i]];
    }
  }
}

Стъпка по стъпка, с думи

Същите 6 поръчки. Selection sort преглежда всичко неподредено, намира най-ранната поръчка и я слага отпред.
i = 0: 5 сравнения в остатъка. Най-ранната е 08:45 и разменя се с 14:30.
i = 1: 4 сравнения в остатъка. Най-ранната е 09:15 и тя вече е на мястото си: без размяна.
i = 2: 3 сравнения в остатъка. Най-ранната е 10:30 и разменя се с 11:00.
i = 3: 2 сравнения в остатъка. Най-ранната е 11:00 и разменя се с 16:45.
i = 4: 1 сравнение в остатъка. Най-ранната е 14:30 и разменя се с 16:45.
15 сравнения и 4 размени. Сравненията винаги са n(n − 1)/2 = 15: и почти подреденият списък иска 15, с 1 размяна.

function selectionSort(times) {
  let comparisons = 0;
  let swaps = 0;
  for (let i = 0; i < times.length - 1; i++) {
    let best = i;
    for (let j = i + 1; j < times.length; j++) {
      comparisons++;
      if (times[j] < times[best]) {
        best = j;
      }
    }
    if (best !== i) {
      [times[i], times[best]] = [times[best], times[i]];
      swaps++;
    }
  }
  console.log(`Сравнения: ${comparisons}, размени: ${swaps}`);
}

const today = ["14:30", "09:15", "11:00", "16:45", "10:30", "08:45"];
selectionSort(today);
console.log(today.join(" "));

const almost = ["08:45", "09:15", "11:00", "10:30", "14:30", "16:45"];
selectionSort(almost);

Сравнения: 15, размени: 4
08:45 09:15 10:30 11:00 14:30 16:45
Сравнения: 15, размени: 1

И двата списъка искат по 15 сравнения: за да е сигурен, че е намерил най-ранната, selection sort гледа целия остатък всеки път. За n поръчки това са (n - 1) + (n - 2) + … + 1 = n(n - 1)/2 сравнения при всеки вход. Няма по-добър случай.

Силата му е другаде: размените са най-много n - 1, по една на място. Insertion sort отмества до n²/2 пъти. Когато сравнението е евтино, а преместването е скъпо (големи записи, които се копират, или запис върху флаш памет, която се износва), малкото размени имат значение.

Виж го

Измери

Операцията е едно сравнение на два елемента. Insertion sort е пуснат на три входа: случаен, почти подреден (подреден, а после n/20 съседни двойки са разменени) и обратно подреден. Selection sort е само на случаен вход, защото при всеки вход прави едно и също.

Insertion sort, случаен вход O(n²)
Insertion sort, почти подреден вход O(n)
Insertion sort, обратно подреден вход O(n²)
Selection sort, случаен вход O(n²)

Алгоритъм	n = 10	n = 100	n = 1000	n = 10 000	n = 100 000
Insertion sort, случаен вход	37	2481	254 808	25 057 917	≈ 2 505 791 700
Insertion sort, почти подреден вход	9	104	1049	10 474	104 755
Insertion sort, обратно подреден вход	45	4950	499 500	49 995 000	≈ 4 999 500 000
Selection sort, случаен вход	45	4950	499 500	49 995 000	≈ 4 999 500 000

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

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

При 1000 елемента: случаен вход 254 808, почти подреден 1 049, обратно подреден 499 500, а selection sort 499 500 при всеки вход. При 100 000 се пуска само почти подреденият: другите биха направили милиарди сравнения. Страницата с 50 000 продукта е между двете: над милиард сравнения при selection sort.

Пробвай

Намери грешката

Тази версия оставя една поръчка не на място:

const today = ["14:30", "09:15", "11:00", "16:45", "10:30", "08:45"];
insertionSort(today);
console.log(today.join(" "));

14:30 08:45 09:15 10:30 11:00 16:45

Избери реда с грешката.

Пробвай

Подреди редовете

Това е тялото на външния цикъл на insertion sort. Подреди го.

while (j >= 0 && times[j] > key) {
let j = i - 1;
times[j + 1] = key;
j--;
const key = times[i];
times[j + 1] = times[j];
}

Идеята

Къде се ползват

Бавни са за много елементи, но не са само за учене. Insertion sort е най-бързият за малки масиви и за почти подредени: няма рекурсия и допълнителна памет, а вътрешният му цикъл е къс.

Затова вградените сортирания го ползват отвътре:

По-точно, за любопитните

Java. Arrays.sort за обекти и Collections.sort са TimSort: той търси вече подредени парчета в данните, а късите ги удължава с binary insertion sort, до около 32 елемента. Arrays.sort за числа е dual-pivot quicksort, който подрежда малките части с insertion sort.
C#. Array.Sort и List<T>.Sort са introsort: quick sort, който за части до 16 елемента минава на insertion sort.
Python. list.sort() и sorted() са TimSort (от 3.11 с powersort правилото за сливане), и пак удължават късите парчета с binary insertion sort.
JavaScript. В V8 (Chrome, Node.js) Array.prototype.sort е TimSort от 2018 г., със същия binary insertion sort за късите парчета.

Binary insertion sort търси мястото на key с двоично търсене, а не едно по едно. Сравненията стават около n log n, но отместванията остават същите.

За големи масиви трябват O(n log n) алгоритми. Първият е merge sort.

Упражнение

Най-големите поръчки отгоре

Реши задачата в редактора си.

По сума, от най-голямата. Отчетът за деня показва поръчките по сума, от най-голямата към най-малката. Напиши sortByTotalDescending(totals) с insertion sort и подреди поръчки за 46, 13, 89, 23 и 67 €. Изходът е:

89 €
67 €
46 €
23 €
13 €

Още задачи

Selection sort отзад. Напиши selection sort, който всеки път намира най-късната поръчка и я слага на края на неподредената част. Преброй сравненията: пак ли са n(n - 1)/2?
Отмествания срещу размени. Пусни броещите версии на обратно подреден списък от 10 поръчки. Колко отмествания прави insertion sort и колко размени selection sort?
Binary insertion sort. Намери мястото на key с двоично търсене в подредената част и после отмести. Колко сравнения прави за 1000 случайни поръчки?

Тест

Провери се

1. Списъкът с поръчки вече е подреден по час, само две съседни са разменени. Кой алгоритъм свършва по-бързо?Selection sort: прави най-малко размениЕднакво бързо: и двата са O(n²)Insertion sort: почти всяка поръчка се сравнява веднъж и остава

2. Колко сравнения прави selection sort за 1000 поръчки?Около 10 000Около 1000, ако са подредени499 500, при всякакъв вход

3. Кога selection sort е по-добрият избор?Когато списъкът е почти подреденКогато всяко записване на място е скъпо: той прави най-много n - 1 размениКогато елементите са милион

4. Какво прави insertion sort с поръчка, която е по-рано от всички в подредената част?Оставя я накраяРазменя я с първатаОтмества всички с по едно надясно и я слага на място 0

Insertion sort и selection sort

Бисквитки