Стабилно сортиране и вграденият sort

Код на:JavaC#PythonJavaScript

Накратко: Стабилното сортиране пази реда на елементите с равни ключове; Array.prototype.sort в JavaScript е стабилен, затова подреждането по няколко ключа става на няколко минавания.

Проблем

Датите, които се разбъркват

В админ панела на магазина поръчките стоят по дата: най-старите отгоре. Служителят натиска заглавието „Клиент“, за да види поръчките на всеки клиент заедно. Очаква поръчките на Иван да са една под друга, и пак по дата.

Ето какво дава подреждане по клиент със selection sort:

function selectionSort(orders) {
  for (let i = 0; i < orders.length - 1; i++) {
    let smallest = i;
    for (let j = i + 1; j < orders.length; j++) {
      if (orders[j].customer < orders[smallest].customer) {
        smallest = j;
      }
    }
    const tmp = orders[i];
    orders[i] = orders[smallest];
    orders[smallest] = tmp;
  }
}

const orders = [
  { date: "2026-10-03", customer: "Иван", amount: 42.50 },
  { date: "2026-10-05", customer: "Мария", amount: 18.00 },
  { date: "2026-10-07", customer: "Иван", amount: 120.00 },
  { date: "2026-10-09", customer: "Петър", amount: 64.90 },
  { date: "2026-10-12", customer: "Мария", amount: 35.20 },
  { date: "2026-10-15", customer: "Иван", amount: 9.99 },
];
selectionSort(orders);
for (const o of orders) {
  console.log(o.customer, o.date);
}

Изход

Иван 2026-10-03
Иван 2026-10-07
Иван 2026-10-15
Мария 2026-10-12
Мария 2026-10-05
Петър 2026-10-09

Клиентите са подредени. Но при Мария поръчката от 12 октомври е преди тази от 5 октомври. Служителят вижда последната поръчка на Мария като първа и ѝ звъни за грешната.

Идеята

Стабилност: равните пазят реда си

Подреждане е стабилно, ако елементите с равен ключ остават в реда, в който са били. Двете поръчки на Мария са с равен ключ (клиентът). Стабилното подреждане ги оставя както са дошли: първо 5 октомври, после 12.

Кои алгоритми са стабилни:

• insertion sort: мести елемент само покрай строго по-големи, затова никога не прескача равен;
• merge sort: при равни взима от лявата половина (merge sort);
• counting sort: поставя отляво надясно (counting sort).

Кои не са:

• selection sort, quick sort и heap sort. И трите разменят елементи на разстояние. Размяната пренася елемент над всичко между двете места, и равните между тях остават зад него.

Стабилността има значение само когато елементът носи нещо повече от ключа. Две равни числа 5 не се различават. Две поръчки на Мария се различават.

Виж го

Selection sort срещу insertion sort

Същият списък с insertion sort:

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

const orders = [
  { date: "2026-10-03", customer: "Иван", amount: 42.50 },
  { date: "2026-10-05", customer: "Мария", amount: 18.00 },
  { date: "2026-10-07", customer: "Иван", amount: 120.00 },
  { date: "2026-10-09", customer: "Петър", amount: 64.90 },
  { date: "2026-10-12", customer: "Мария", amount: 35.20 },
  { date: "2026-10-15", customer: "Иван", amount: 9.99 },
];
insertionSort(orders);
for (const o of orders) {
  console.log(o.customer, o.date);
}

Изход

Иван 2026-10-03
Иван 2026-10-07
Иван 2026-10-15
Мария 2026-10-05
Мария 2026-10-12
Петър 2026-10-09

function selectionSort(orders) {
  for (let i = 0; i < orders.length - 1; i++) {
    let smallest = i;
    for (let j = i + 1; j < orders.length; j++) {
      if (orders[j].customer < orders[smallest].customer) {
        smallest = j;
      }
    }
    const tmp = orders[i];
    orders[i] = orders[smallest];
    orders[smallest] = tmp;
  }
}

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

1. Шест поръчки, подредени по дата. Сега по клиент, със selection sort.
2. Място 0: най-малкият клиент оттук нататък е Иван 03.10, вече е на мястото си.
3. Място 1: Иван 07.10 се разменя с Мария 05.10.
4. Място 2: Иван 15.10 се разменя с Мария 05.10. Далечната размяна хвърля Мария 05.10 в края, зад Мария 12.10.
5. Още две размени: Мария идва преди Петър.
6. Подредено по клиент, но Мария 12.10 е преди Мария 05.10. Selection sort не е стабилен: равните ключове губят реда си.
7. Същият списък с insertion sort. Поръчката се мести само покрай строго по-големи, затова Мария 05.10 остава преди Мария 12.10. Стабилно.

Поръчката, която insertion sort мести наляво, спира пред първата, която не е по-голяма. Равна поръчка не се прескача, и датите на Мария остават 05, после 12.

Пробвай

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

Някой е сменил едно сравнение в insertion sort. Подреждането пак е по клиент, но датите вътре в клиента излизат обърнати:

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

const orders = [
  { date: "2026-10-03", customer: "Иван", amount: 42.50 },
  { date: "2026-10-05", customer: "Мария", amount: 18.00 },
  { date: "2026-10-07", customer: "Иван", amount: 120.00 },
  { date: "2026-10-09", customer: "Петър", amount: 64.90 },
  { date: "2026-10-12", customer: "Мария", amount: 35.20 },
  { date: "2026-10-15", customer: "Иван", amount: 9.99 },
];
insertionSort(orders);
for (const o of orders) {
  console.log(o.customer, o.date);
}

Изход

Иван 2026-10-15
Иван 2026-10-07
Иван 2026-10-03
Мария 2026-10-12
Мария 2026-10-05
Петър 2026-10-09

На кой ред е грешката?

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

1function insertionSort(orders) {2 for (let i = 1; i < orders.length; i++) {3 const current = orders[i];4 let j = i - 1;5 while (j >= 0 && current.customer <= orders[j].customer) {6 orders[j + 1] = orders[j];7 j--;8 }9 orders[j + 1] = current;10 }11}

Провери

Виж го

Вграденият sort

На практика не пишеш свое подреждане, а ползваш вграденото. Двайсет поръчки, по дата, подредени по клиент. Печатат се датите на всеки клиент:

В JavaScript Array.prototype.sort е стабилен от ES2019 нататък: стандартът го изисква. Сравнението връща отрицателно, нула или положително число.

orders.sort((a, b) => a.customer.localeCompare(b.customer));
show(orders);

Изход

Иван: 01 04 06 09 12 15 18
Мария: 02 05 08 11 13 16 19
Петър: 03 07 10 14 17 20

Датите на всеки клиент са подред: 01, 04, 06…

Идеята

Какво ползва вграденият sort на всеки език

• Java. Arrays.sort за масив от примитиви (int[], double[]) е dual-pivot quick sort: не е стабилен, но при числата това няма значение. За обекти (Arrays.sort(Object[]), List.sort, Collections.sort) е TimSort: стабилен.
• C#. Array.Sort и List<T>.Sort са introsort: quick sort, който минава на heap sort при твърде дълбоко разделяне и на insertion sort при малки части. Не е стабилен. LINQ OrderBy и ThenBy са стабилни.
• Python. list.sort и sorted са TimSort: стабилни.
• JavaScript. Array.prototype.sort трябва да е стабилен от ES2019. V8 (Chrome, Node.js) ползва TimSort от версия 7.0.

TimSort е merge sort, който търси вече подредени парчета във входа и ги слива. Реалните данни често са почти подредени, и тогава той е близо до O(n).

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

• Python: от версия 3.11 правилото, по което TimSort избира кои парчета да слее, е powersort (на Munro и Wild). Подреждането пак е стабилно, сливанията са по-добре подредени.
• Java: стабилността за примитиви наистина няма значение, защото две равни int не се различават. Затова там е избран по-бързият quick sort.
• C#: introsort пази O(n log n) в най-лошия случай благодарение на heap sort (heap sort). Цената е стабилността.
• JavaScript: преди ES2019 V8 ползваше quick sort за дълги масиви и подреждането не беше стабилно. Код, писан тогава, понякога има „поправки“ за това, които днес не трябват.
• И в четирите: сравнението трябва да е последователно. Ако казва, че А е преди Б, а Б е преди А, резултатът е непредвидим, а в Java List.sort може да хвърли IllegalArgumentException: Comparison method violates its general contract!.

Виж го

Подреждане по няколко ключа

Често ключът е повече от едно поле: по клиент, а вътре в клиента най-голямата сума първа.

Сравнението връща число. || минава към втория ключ само когато първият даде 0, тоест когато клиентите са равни. b.amount - a.amount е най-голямата сума първа.

orders.sort((a, b) => a.customer.localeCompare(b.customer) || b.amount - a.amount);

Изход

Иван 2026-10-07 120.00 €
Иван 2026-10-03 42.50 €
Иван 2026-10-15 9.99 €
Мария 2026-10-12 35.20 €
Мария 2026-10-05 18.00 €
Петър 2026-10-09 64.90 €

Има и втори начин, който работи само със стабилно подреждане: подреди първо по втория ключ, после по първия. Второто подреждане пази реда на равните, а той вече е по втория ключ. Последното подреждане е главното.

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

Кога е полезен вторият начин: когато ключовете не се събират в едно сравнение. Например в Python -o.amount не става за текст: за „по клиент, а вътре по име на продукта в обратен ред“ се подрежда два пъти, първо key=lambda o: o.product, reverse=True, после key=lambda o: o.customer.

Пробвай

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

Две стабилни подреждания едно след друго: първо по сума, най-голямата първа, после по клиент. Какво печата програмата?

const orders = [
  { date: "2026-10-05", customer: "Мария", amount: 35.20 },
  { date: "2026-10-06", customer: "Иван", amount: 9.99 },
  { date: "2026-10-07", customer: "Мария", amount: 18.00 },
  { date: "2026-10-08", customer: "Иван", amount: 42.50 },
];
orders.sort((a, b) => b.amount - a.amount);
orders.sort((a, b) => a.customer.localeCompare(b.customer));
for (const o of orders) {
  console.log(o.customer, o.amount.toFixed(2));
}

Отговор

Иван 42.50 / Мария 35.20 / Мария 18.00 / Иван 9.99

Иван 9.99 / Иван 42.50 / Мария 18.00 / Мария 35.20

Иван 42.50 / Иван 9.99 / Мария 35.20 / Мария 18.00

Провери

Упражнение

Доставките по град

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

По град, после по сума. Шест доставки имат град и сума. Подреди ги по град, а в един град най-голямата сума първа, с вградения sort на езика си.

Изход

Варна 40.00 €
Варна 9.90 €
Пловдив 24.00 €
Пловдив 15.30 €
София 80.00 €
София 12.50 €

Още задачи

• Два пъти. Направи същото с две стабилни подреждания, без да слагаш два ключа в едно сравнение. Кое подреждане е първо?
• Нестабилно на ръка. Подреди доставките по град с heap sort от урока за heap. Остават ли сумите в един град в реда, в който бяха?
• Стабилен selection sort. Може ли selection sort да стане стабилен, ако вместо да разменя, премести най-малкия на мястото му и избута останалите надясно? Колко струва това?

Тест

Провери се

1. Какво значи, че едно подреждане е стабилно?

Не иска допълнителна паметЕлементите с равен ключ остават в реда, в който са били предиВинаги е O(n log n)

2. Кои от тези са стабилни, както са написани обикновено?

Selection sort и heap sortQuick sort и selection sortInsertion sort и merge sort

3. Списъкът е подреден по дата. Искаш го по клиент, а вътре в клиента по дата. Какво стига?

Нищо не стига, трябва подреждане по два ключаЕдно подреждане по клиент с какъвто и да е алгоритъмЕдно стабилно подреждане по клиент

4. В C# ти трябва стабилно подреждане на поръчки по клиент. Какво ползваш?

List.SortArray.Sort с ComparisonOrderBy от LINQ

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Merge sort и „разделяй и владей“ · Quick sort и лошият пивот · Heap и heap sort · Counting sort и radix sort
• Продължава в: Приоритетна опашка · Trie · Минимално покриващо дърво · Как да разпознаеш DP задача
• Задачи по темата: Сортиране