2.2.1.3 — самый простой алгоритм сортировки, почти никогда не используемый на практике2.2.1.3 — the simplest sorting algorithm, almost never used in practice
Многократно проходит по массиву, меняя местами соседние элементы не в порядке — крупные значения постепенно "всплывают" к концу массива, как пузырьки. Исторически и педагогически важен, но insertion sort строго лучше при той же асимптотике O(n²).Repeatedly scans the array, swapping adjacent out-of-order elements — large values gradually "bubble up" to the end of the array. Historically and pedagogically important, but insertion sort is strictly better at the same O(n²) asymptotics.
За один проход по массиву сравниваются все соседние пары; если пара стоит не в порядке, элементы меняются местами. После первого прохода самый большой элемент гарантированно оказывается на последнем месте (он "всплывает" через все обмены на своём пути). После k проходов последние k элементов уже отсортированы, поэтому каждый следующий проход можно укорачивать. Алгоритм останавливается, когда за проход не произошло ни одного обмена — это признак того, что массив уже отсортирован (простая, но полезная оптимизация).In one pass over the array, every adjacent pair is compared; if a pair is out of order, the elements swap. After the first pass, the largest element is guaranteed to land in the last position (it "bubbles up" through every swap along the way). After k passes, the last k elements are already sorted, so each subsequent pass can be shortened. The algorithm stops once a pass makes no swaps at all — a signal the array is already sorted (a simple but useful optimization).
после первого полного прохода последний элемент гарантированно на своём местеafter one full pass, the last element is guaranteed to be in its place
void bubble_sort(std::vector<int>& a) {
for (size_t i = 0; i < a.size(); ++i) {
bool swapped = false;
for (size_t j = 0; j < a.size() - i - 1; ++j) { // окно сужается на i с каждым проходом// the window shrinks by i each pass
if (a[j] > a[j + 1]) {
std::swap(a[j], a[j + 1]);
swapped = true;
}
}
if (!swapped) break; // уже отсортирован — ранний выход// already sorted — early exit
}
}Красная рамка — сравниваемая пара соседей. Зелёная заливка — "осевший" хвост массива, который проходы уже не трогают.The red outline is the adjacent pair being compared. Green fill is the "settled" tail the passes no longer touch.
нажмите «Вперёд» или «Играть», чтобы начатьpress "Forward" or "Play" to begin
Оба алгоритма — Θ(n²) в худшем случае, оба стабильны, оба in-place. Но bubble sort делает больше обменов при той же асимптотике: каждый обмен двигает элемент только на одну позицию за раз, тогда как insertion sort может логически "сдвинуть" элемент сразу на несколько позиций (реализовано как последовательные присваивания без промежуточных обменов). На практике bubble sort почти всегда медленнее insertion sort на реальном железе из-за этой разницы в константах — поэтому в промышленном коде и стандартных библиотеках bubble sort не встречается, оставаясь исключительно учебным примером.Both algorithms are Θ(n²) worst case, both stable, both in-place. But bubble sort makes more swaps at the same asymptotic complexity: every swap moves an element only one position at a time, whereas insertion sort can logically "shift" an element several positions at once (implemented as sequential assignments with no intermediate swaps). In practice bubble sort is almost always slower than insertion sort on real hardware because of this constant-factor difference — which is why bubble sort never appears in production code or standard libraries, remaining strictly a teaching example.
Простота реализации (два вложенных цикла, одно сравнение, один обмен) делает bubble sort стандартной первой иллюстрацией понятия "алгоритм" и вложенных циклов — не потому что он эффективен, а потому что он нагляден.Its implementation simplicity (two nested loops, one comparison, one swap) makes bubble sort the standard first illustration of "algorithm" and nested loops — not because it's efficient, but because it's easy to visualize.
Оптимизированная версия с флагом swapped даёт O(n) на уже отсортированном входе — редкий случай, когда наивный на вид алгоритм иллюстрирует ту же идею адаптивности, что и insertion sort, просто менее эффективно.The optimized version with a swapped flag gives O(n) on an already-sorted input — a rare case where a naive-looking algorithm illustrates the same adaptivity idea as insertion sort, just less efficiently.