Пузырьковая сортировка
Каждый проход переносит максимальное неотсортированное значение в конец.
Что такое Пузырьковая сортировка?
Каждый проход переносит максимальное неотсортированное значение в конец.
Сортируйте обменом соседних инверсий.
Важные моменты
- Проверяйте пустые, одиночные, повторяющиеся и отсортированные данные.
- Отделяйте корректность от оптимизации.
- В production предпочитайте стандартную библиотеку.
Визуализация: Пузырьковая сортировка
O(n²)Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.
Примеры кода на C и C++
main.c
#include <stdio.h>
int main(void) {
int values[] = {5, 1, 4, 2};
for (int end = 3; end > 0; --end) {
int changed = 0;
for (int index = 0; index < end; ++index) {
if (values[index] > values[index + 1]) {
int temporary = values[index];
values[index] = values[index + 1];
values[index + 1] = temporary;
changed = 1;
}
}
if (!changed) break;
}
for (int index = 0; index < 4; ++index) {
printf("%d ", values[index]);
}
}
1 2 4 5C++
main.cpp
#include <iostream>
#include <vector>
int main() {
std::vector values{5, 1, 4, 2};
for (auto end = values.end(); end != values.begin(); --end) {
bool changed = false;
for (auto item = values.begin(); item + 1 != end; ++item) {
if (*item > *(item + 1)) {
std::iter_swap(item, item + 1);
changed = true;
}
}
if (!changed) break;
}
for (int value : values) {
std::cout << value << ' ';
}
}
1 2 4 5Сравнение C и C++
Алгоритм учебный и O(n²); ранний выход даёт O(n) на sorted input, а production C++ обычно использует std::sort.
C
Циклы, указатели, длины и буферы задаются явно.
C++
Итераторы и алгоритмы отделяют операцию от хранения.
Практические задания
Запустите обе версии и изменяйте их, сравнивая гарантии языков.
- Проследите каждое сравнение.
- Проверьте дубликаты и крайние значения.
- Сравните со стандартной библиотекой.