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

Код на:JavaC#PythonJavaScript

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

Проблем

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

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

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

record Order(String date, String customer, double amount) {}

static boolean before(Order x, Order y) {
    return x.customer().compareTo(y.customer()) < 0;
}

static void selectionSort(Order[] orders) {
    for (int i = 0; i < orders.length - 1; i++) {
        int smallest = i;
        for (int j = i + 1; j < orders.length; j++) {
            if (before(orders[j], orders[smallest])) {
                smallest = j;
            }
        }
        Order tmp = orders[i];
        orders[i] = orders[smallest];
        orders[smallest] = tmp;
    }
}

Order[] orders = {
    new Order("2026-10-03", "Иван", 42.50),
    new Order("2026-10-05", "Мария", 18.00),
    new Order("2026-10-07", "Иван", 120.00),
    new Order("2026-10-09", "Петър", 64.90),
    new Order("2026-10-12", "Мария", 35.20),
    new Order("2026-10-15", "Иван", 9.99)
};
selectionSort(orders);
for (Order o : orders) {
    System.out.println(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:

static void insertionSort(Order[] orders) {
    for (int i = 1; i < orders.length; i++) {
        Order current = orders[i];
        int j = i - 1;
        while (j >= 0 && before(current, orders[j])) {
            orders[j + 1] = orders[j];
            j--;
        }
        orders[j + 1] = current;
    }
}

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

Изход

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

static void selectionSort(Order[] orders) {
    for (int i = 0; i < orders.length - 1; i++) {
        int smallest = i;
        for (int j = i + 1; j < orders.length; j++) {
            if (before(orders[j], orders[smallest])) {
                smallest = j;
            }
        }
        Order 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. Подреждането пак е по клиент, но датите вътре в клиента излизат обърнати:

static void insertionSort(Order[] orders) {
    for (int i = 1; i < orders.length; i++) {
        Order current = orders[i];
        int j = i - 1;
        while (j >= 0 && !before(orders[j], current)) {
            orders[j + 1] = orders[j];
            j--;
        }
        orders[j + 1] = current;
    }
}

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

Изход

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

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

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

1static void insertionSort(Order[] orders) {2 for (int i = 1; i < orders.length; i++) {3 Order current = orders[i];4 int j = i - 1;5 while (j >= 0 && !before(orders[j], current)) {6 orders[j + 1] = orders[j];7 j--;8 }9 orders[j + 1] = current;10 }11}

Провери

Виж го

Вграденият sort

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

В Java List.sort (и Collections.sort, и Arrays.sort за масив от обекти) е стабилен. Документацията го обещава изрично.

orders.sort(Comparator.comparing(Order::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!.

Виж го

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

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

Comparator.comparing прави сравнение по едно поле, thenComparing добавя следващото, когато първото е равно, а Comparator.reverseOrder() го обръща.

orders.sort(Comparator.comparing(Order::customer)
        .thenComparing(Order::amount, Comparator.reverseOrder()));

Изход

Иван 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.

Пробвай

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

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

List<Order> orders = new ArrayList<>(List.of(
    new Order("2026-10-05", "Мария", 35.20),
    new Order("2026-10-06", "Иван", 9.99),
    new Order("2026-10-07", "Мария", 18.00),
    new Order("2026-10-08", "Иван", 42.50)
));
orders.sort(Comparator.comparing(Order::amount).reversed());
orders.sort(Comparator.comparing(Order::customer));
for (Order o : orders) {
    System.out.println(o.customer() + " " + o.amount());
}

Отговор

Иван 9.99 / Иван 42.5 / Мария 18.0 / Мария 35.2

Иван 42.5 / Иван 9.99 / Мария 35.2 / Мария 18.0

Иван 42.5 / Мария 35.2 / Мария 18.0 / Иван 9.99

Провери

Упражнение

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

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

По град, после по сума. Шест доставки имат град и сума. Подреди ги по град, а в един град най-голямата сума първа, с вградения 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 задача
• Задачи по темата: Сортиране