Простая сортировка: пузырёк, выбор, вставка

живой пример

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class StableDemo {
    record Order(String city, int day) {}

    public static void main(String[] args) {
        List<Order> orders = new ArrayList<>(List.of(
                new Order("Казань", 3), new Order("Москва", 1), new Order("Казань", 1), new Order("Москва", 2)));
        orders.sort(Comparator.comparingInt(Order::day));
        orders.sort(Comparator.comparing(Order::city));
        System.out.println(orders);
    }
}

живой пример

package main

import (
	"cmp"
	"fmt"
	"slices"
)

type Order struct {
	City string
	Day  int
}

func main() {
	orders := []Order{{"Казань", 3}, {"Москва", 1}, {"Казань", 1}, {"Москва", 2}}
	slices.SortStableFunc(orders, func(a, b Order) int { return cmp.Compare(a.Day, b.Day) })
	slices.SortStableFunc(orders, func(a, b Order) int { return cmp.Compare(a.City, b.City) })
	fmt.Println(orders)
}

живой пример

const orders = [
  { city: "Казань", day: 3 }, { city: "Москва", day: 1 },
  { city: "Казань", day: 1 }, { city: "Москва", day: 2 },
];
orders.sort((a, b) => a.day - b.day);
orders.sort((a, b) => a.city.localeCompare(b.city));
console.log(orders);

живой пример

from dataclasses import dataclass


@dataclass
class Order:
    city: str
    day: int


orders = [Order("Казань", 3), Order("Москва", 1), Order("Казань", 1), Order("Москва", 2)]
orders.sort(key=lambda o: o.day)
orders.sort(key=lambda o: o.city)
print(orders)

живой пример

import java.util.Arrays;

public class SortCost {
    static int comparisons, moves;

    static boolean greater(int x, int y) {
        comparisons++;
        return x > y;
    }

    static void swap(int[] a, int i, int j) {
        moves++;
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }

    static void bubble(int[] a) {
        for (int out = a.length - 1; out > 0; out--)
            for (int in = 0; in < out; in++)
                if (greater(a[in], a[in + 1])) swap(a, in, in + 1);
    }

    static void selection(int[] a) {
        for (int out = 0; out < a.length - 1; out++) {
            int min = out;
            for (int in = out + 1; in < a.length; in++)
                if (greater(a[min], a[in])) min = in;
            swap(a, out, min);
        }
    }

    static void insertion(int[] a) {
        for (int out = 1; out < a.length; out++) {
            int temp = a[out], in = out;
            while (in > 0 && greater(a[in - 1], temp)) {
                a[in] = a[in - 1];
                in--;
                moves++;
            }
            a[in] = temp;
        }
    }

    static void print(String name, int[] a) {
        System.out.println(name + ": сравнений " + comparisons + ", перемещений " + moves
            + " → " + Arrays.toString(a));
        comparisons = moves = 0;
    }

    public static void main(String[] args) {
        int[] data = {7, 3, 9, 1, 8, 2, 6, 4};
        int[] a = data.clone(); bubble(a); print("пузырёк", a);
        a = data.clone(); selection(a); print("выбор", a);
        a = data.clone(); insertion(a); print("вставки", a);
    }
}

живой пример

package main

import (
	"fmt"
	"slices"
)

var comparisons, moves int

func greater(x, y int) bool {
	comparisons++
	return x > y
}

func swap(a []int, i, j int) {
	moves++
	a[i], a[j] = a[j], a[i]
}

func bubble(a []int) {
	for out := len(a) - 1; out > 0; out-- {
		for in := 0; in < out; in++ {
			if greater(a[in], a[in+1]) {
				swap(a, in, in+1)
			}
		}
	}
}

func selection(a []int) {
	for out := 0; out < len(a)-1; out++ {
		least := out
		for in := out + 1; in < len(a); in++ {
			if greater(a[least], a[in]) {
				least = in
			}
		}
		swap(a, out, least)
	}
}

func insertion(a []int) {
	for out := 1; out < len(a); out++ {
		temp, in := a[out], out
		for in > 0 && greater(a[in-1], temp) {
			a[in] = a[in-1]
			in--
			moves++
		}
		a[in] = temp
	}
}

func report(name string, a []int) {
	fmt.Printf("%s: сравнений %d, перемещений %d → %v\n", name, comparisons, moves, a)
	comparisons, moves = 0, 0
}

func main() {
	data := []int{7, 3, 9, 1, 8, 2, 6, 4}
	a := slices.Clone(data)
	bubble(a)
	report("пузырёк", a)
	a = slices.Clone(data)
	selection(a)
	report("выбор", a)
	a = slices.Clone(data)
	insertion(a)
	report("вставки", a)
}

живой пример

let comparisons = 0;
let moves = 0;

function greater(x, y) {
  comparisons++;
  return x > y;
}

function swap(a, i, j) {
  moves++;
  [a[i], a[j]] = [a[j], a[i]];
}

function bubble(a) {
  for (let out = a.length - 1; out > 0; out--)
    for (let inn = 0; inn < out; inn++)
      if (greater(a[inn], a[inn + 1])) swap(a, inn, inn + 1);
}

function selection(a) {
  for (let out = 0; out < a.length - 1; out++) {
    let least = out;
    for (let inn = out + 1; inn < a.length; inn++)
      if (greater(a[least], a[inn])) least = inn;
    swap(a, out, least);
  }
}

function insertion(a) {
  for (let out = 1; out < a.length; out++) {
    const temp = a[out];
    let inn = out;
    while (inn > 0 && greater(a[inn - 1], temp)) {
      a[inn] = a[inn - 1];
      inn--;
      moves++;
    }
    a[inn] = temp;
  }
}

function report(name, a) {
  console.log(`${name}: сравнений ${comparisons}, перемещений ${moves} → [${a.join(", ")}]`);
  comparisons = moves = 0;
}

const data = [7, 3, 9, 1, 8, 2, 6, 4];
let a = [...data]; bubble(a); report("пузырёк", a);
a = [...data]; selection(a); report("выбор", a);
a = [...data]; insertion(a); report("вставки", a);

живой пример

comparisons = moves = 0


def greater(x: int, y: int) -> bool:
    global comparisons
    comparisons += 1
    return x > y


def swap(a: list, i: int, j: int) -> None:
    global moves
    moves += 1
    a[i], a[j] = a[j], a[i]


def bubble(a: list) -> None:
    for out in range(len(a) - 1, 0, -1):
        for i in range(out):
            if greater(a[i], a[i + 1]):
                swap(a, i, i + 1)


def selection(a: list) -> None:
    for out in range(len(a) - 1):
        least = out
        for i in range(out + 1, len(a)):
            if greater(a[least], a[i]):
                least = i
        swap(a, out, least)


def insertion(a: list) -> None:
    global moves
    for out in range(1, len(a)):
        temp, i = a[out], out
        while i > 0 and greater(a[i - 1], temp):
            a[i] = a[i - 1]
            i -= 1
            moves += 1
        a[i] = temp


def report(name: str, a: list) -> None:
    global comparisons, moves
    print(f"{name}: сравнений {comparisons}, перемещений {moves} → {a}")
    comparisons = moves = 0


data = [7, 3, 9, 1, 8, 2, 6, 4]
a = data.copy(); bubble(a); report("пузырёк", a)
a = data.copy(); selection(a); report("выбор", a)
a = data.copy(); insertion(a); report("вставки", a)

От того, что внутри у библиотечной сортировки, зависит, сохранится ли порядок равных элементов и как быстро всё отработает на почти упорядоченных данных.

Точек входа две: Arrays.sort для массивов и Collections.sort (то же самое, что list.sort(...)) для списков.

Откуда сортировка знает, что «меньше», а что «больше». У чисел, строк и дат есть естественный порядок: они реализуют интерфейс Comparable, и метод compareTo возвращает отрицательное число, ноль или положительное; Arrays.sort(int[]) и Collections.sort(list) без аргументов пользуются им. Свой класс либо тоже реализует Comparable, если у него один очевидный порядок, либо порядок задают снаружи объектом Comparator, как в примере выше через Comparator.comparing; порядков может быть сколько угодно, по фамилии, по дате, по сумме. Как их собирают из нескольких ключей и что делать с null, разобрано в статье про коллекции, в разделе про сортировку.

Оговорка про «дорогие перемещения», ради которых выбирают сортировку выбором. В Java перемещение объекта это копирование ссылки, четыре байта, и оно дешевле сравнения: сравнение объектов вызывает compareTo через интерфейс и лезет в поля, а строк ещё и идёт по символам. Дорогим перемещение бывает у примитивов больших структур в других языках и у записей на диске, где переставить значит переписать блок. Поэтому в Java на выбор смотрят как на учебный алгоритм, а библиотечная сортировка экономит именно сравнения.

List<Employee> staff = new ArrayList<>(hired);
staff.sort(Comparator.comparing(Employee::lastName));

Когда сортируют объекты, внутри работает TimSort — гибрид сортировки слиянием и вставок. Сначала он проходит по данным и ищет куски, которые уже упорядочены (их называют сериями); короткую серию он достраивает до приличной длины именно вставками, только двоичными — место для очередного элемента ищется двоичным поиском, а не перебором слева. Потом готовые серии сливаются между собой. Отсюда два свойства: TimSort устойчив и на почти упорядоченных данных работает близко к O(N). В худшем случае — O(N·log N).

Вставки остались в библиотеке и на вторых ролях: короткие участки в несколько десятков элементов досортировываются именно ими — на такой длине они обгоняют всё остальное за счёт крошечных накладных расходов.

Одно важное различие: устойчивость есть только у объектной версии. Arrays.sort(int[]) про неё ничего не знает и знать не может — два одинаковых числа неразличимы, «сохранять их порядок» бессмысленно.

Грабля. TimSort верит, что сравнение последовательно: если a меньше b, а b меньше c, то и a меньше c. Классический способ это сломать — сравнивать вычитанием:

Comparator<Item> byPrice = (a, b) -> (int) (a.priceInCents() - b.priceInCents());

Разность двух больших чисел не влезает в int, знак получается случайным, порядок становится противоречивым. На маленьких списках «всё работает», а на большом TimSort замечает нестыковку и роняет сортировку с IllegalArgumentException: Comparison method violates its general contract!. Надёжный вариант — Comparator.comparingLong(Item::priceInCents): он сравнивает, а не вычитает.

От того, что внутри у библиотечной сортировки, зависит, сохранится ли порядок равных элементов и как быстро всё отработает на почти упорядоченных данных.

Точек входа в Go две семьи: старый пакет sort (sort.Ints, sort.Slice, sort.SliceStable, sort.Sort по интерфейсу) и обобщённый пакет slices с Go 1.21 (slices.Sort, slices.SortFunc, slices.SortStableFunc). В новом коде берут slices: он быстрее и не требует писать три метода интерфейса sort.Interface.

Откуда сортировка знает, что «меньше», а что «больше». slices.Sort работает для типов с естественным порядком, чисел и строк, это ограничение cmp.Ordered. Для своего типа порядок задают функцией func(a, b T) int, которая возвращает отрицательное число, ноль или положительное; собирать её из нескольких ключей помогает cmp.Compare: сначала сравнить город, и только при равенстве день. Порядков может быть сколько угодно, по фамилии, по дате, по сумме.

Оговорка про «дорогие перемещения», ради которых выбирают сортировку выбором. В Go срез структур хранит сами значения, и обмен двух элементов копирует их целиком: у структуры в сотню байт перемещение уже сравнимо со сравнением. Поэтому большие структуры часто сортируют через срез указателей или индексов. Но библиотечная сортировка всё равно экономит именно сравнения: функция сравнения вызывается косвенно, а строки сравниваются побайтно.

staff := slices.Clone(hired)
slices.SortFunc(staff, func(a, b Employee) int {
	return cmp.Compare(a.LastName, b.LastName)
})

Внутри slices.Sort и slices.SortFunc с Go 1.19 работает pdqsort (pattern-defeating quicksort): быстрая сортировка, которая замечает уже упорядоченные и почти упорядоченные участки и на них работает близко к O(N), а на плохих данных переключается на пирамидальную сортировку, так что худший случай O(N·log N). Короткие участки до двенадцати элементов досортировываются вставками — на такой длине они обгоняют всё остальное за счёт крошечных накладных расходов.

Одно важное различие: pdqsort неустойчив. Два заказа из одного города после slices.SortFunc по городу могут поменяться местами, и пример с двумя проходами по дню и городу на нём сломается. Для устойчивости есть slices.SortStableFunc и sort.Stable: внутри сортировка вставками блоками по двадцать элементов и слияние блоков на месте, устойчиво, но дороже: O(N·log N) сравнений и O(N·log² N) обменов.

Грабля. Сортировка верит, что сравнение последовательно: если a меньше b, а b меньше c, то и a меньше c. Классический способ это сломать в Go — вычитание беззнаковых чисел:

slices.SortFunc(items, func(a, b Item) int { return int(a.Qty - b.Qty) })

Если Qty объявлен как uint32, разность никогда не бывает отрицательной: 3 - 5 даёт огромное положительное число, и функция всегда отвечает «a больше». Паники не будет: Go молча вернёт неверно упорядоченный срез, а на маленьких данных «всё работает». Надёжный вариант — cmp.Compare(a.Qty, b.Qty): он сравнивает, а не вычитает. Вторая ловушка того же рода — float64 с NaN: обычные < и > с ним непоследовательны, а cmp.Compare нарочно ставит NaN раньше всех чисел.

От того, что внутри у библиотечной сортировки, зависит, сохранится ли порядок равных элементов и как быстро всё отработает на почти упорядоченных данных.

Точка входа одна: array.sort(compareFn), и она сортирует на месте, меняя исходный массив. С Node 20 есть toSorted, которая возвращает отсортированную копию и исходный массив не трогает.

Откуда сортировка знает, что «меньше», а что «больше». Здесь главная грабля JavaScript: без функции сравнения sort приводит элементы к строкам и сравнивает их как текст, поэтому [10, 9, 1].sort() даёт [1, 10, 9]. Для чисел функцию сравнения пишут всегда: (a, b) => a - b; для строк с учётом языка a.localeCompare(b); для своих объектов сравнивают поля. Функция возвращает отрицательное число, ноль или положительное, порядков может быть сколько угодно, по фамилии, по дате, по сумме.

Оговорка про «дорогие перемещения», ради которых выбирают сортировку выбором. В JavaScript перемещение объекта это копирование ссылки, и оно дешевле сравнения: сравнение вызывает вашу функцию, а та лезет в поля. Поэтому библиотечная сортировка экономит именно сравнения.

const staff = hired.toSorted((a, b) => a.lastName.localeCompare(b.lastName));

Внутри у V8 с 2018 года работает TimSort — гибрид сортировки слиянием и вставок, тот же алгоритм, что в Java и Python. Сначала он проходит по данным и ищет куски, которые уже упорядочены (их называют сериями); короткую серию достраивает двоичными вставками, потом сливает серии между собой. Отсюда два свойства: сортировка устойчива, и с ES2019 это требование стандарта, а не деталь движка, а на почти упорядоченных данных она работает близко к O(N). В худшем случае — O(N·log N). Вставки остались на вторых ролях: короткие участки досортировываются именно ими.

Устойчивость есть для любых элементов: два равных числа неразличимы, а объекты с равным ключом сохраняют порядок, и два прохода по дню и городу из примера выше работают.

Грабля. TimSort верит, что сравнение последовательно: если a меньше b, а b меньше c, то и a меньше c. В JavaScript её ломают не вычитанием, числа здесь дробные и до 2⁵³ не переполняются, а функцией, которая возвращает true или false:

items.sort((a, b) => a.priceInCents > b.priceInCents);

true превращается в 1, false в 0, и сортировка никогда не слышит ответа «меньше». Результат стандартом не определён: массив может остаться как был или перемешаться, исключения не будет нигде. Надёжный вариант — (a, b) => a.priceInCents - b.priceInCents: он возвращает знак, а не истину.

От того, что внутри у библиотечной сортировки, зависит, сохранится ли порядок равных элементов и как быстро всё отработает на почти упорядоченных данных.

Точек входа две: list.sort() сортирует список на месте и возвращает None, sorted(iterable) строит новый список из чего угодно, хоть из словаря или генератора. Классическая ошибка новичка — a = a.sort(), после которой в a лежит None.

Откуда сортировка знает, что «меньше», а что «больше». У чисел, строк и дат есть естественный порядок через метод __lt__, им пользуются sort и sorted без аргументов. Для своего порядка функцию сравнения не пишут, а передают ключ key=, который из элемента делает то, что уже умеет сравниваться: key=lambda o: o.day, key=attrgetter("city"), кортеж key=lambda o: (o.city, o.day) для нескольких полей. Ключ считается один раз на элемент, а не при каждом сравнении, поэтому это быстрее двухаргументных сравнений; старую функцию сравнения при необходимости заворачивают в functools.cmp_to_key.

Оговорка про «дорогие перемещения», ради которых выбирают сортировку выбором. В Python перемещение объекта это копирование указателя, и оно дешевле сравнения: сравнение вызывает __lt__, а для своих классов ещё и проходит через интерпретатор. Поэтому библиотечная сортировка экономит именно сравнения.

staff = sorted(hired, key=attrgetter("last_name"))

Внутри работает TimSort, и придуман он был именно для Python: гибрид сортировки слиянием и вставок. Сначала он проходит по данным и ищет куски, которые уже упорядочены (их называют сериями); короткую серию достраивает до длины в несколько десятков элементов двоичными вставками, потом сливает серии между собой. Отсюда два свойства: сортировка устойчива, и это гарантия языка, а на почти упорядоченных данных она работает близко к O(N). В худшем случае — O(N·log N). С версии 3.11 порядок слияния серий сменился на схему powersort, но название и свойства прежние.

Устойчивость есть для любых элементов: два прохода по дню и городу из примера выше дают порядок по обоим полям, а ключ-кортеж делает то же за один проход.

Грабля. TimSort верит, что сравнение последовательно, и переполнения чисел в Python нет, зато есть другая ловушка: элементы разных типов. Список из чисел и строк сортироваться откажется:

sorted([3, "10", 7])

Python 3 честно бросает TypeError: '<' not supported between instances of 'str' and 'int', и это лучше молчаливого мусора. Хуже, когда ключ возвращает None для части элементов: сравнение None < 5 падает тем же TypeError посреди сортировки, уже на боевых данных. Надёжный вариант — ключ, который всегда одного типа: key=lambda o: (o.price is None, o.price or 0) ставит пустые цены в конец и не падает.

• Порядок задаёт Comparable (естественный, через compareTo) или внешний Comparator; в Java перемещение объекта это копия ссылки и дешевле сравнения. Внутри Arrays.sort для объектов TimSort, устойчивый.

• Порядок задаёт cmp.Ordered у чисел и строк или функция func(a, b T) int у своих типов; slices.Sort это pdqsort и он неустойчив, устойчивость даёт slices.SortStableFunc; в срезе структур обмен копирует значение целиком.

• Порядок задаёт функция сравнения, без неё sort сравнивает как строки; sort меняет массив на месте, toSorted даёт копию; TimSort устойчив по стандарту, функция сравнения должна возвращать знак, а не true/false.

• Порядок задаёт key=, а не функция сравнения; list.sort() меняет на месте и возвращает None, sorted() даёт новый список; TimSort устойчив по гарантии языка, разнотипные элементы дают TypeError.