Сортировка: пузырьковая, выборочная и сортировка вставками
Упорядочивание массива
- Сортировка упорядочивает массив так, чтобы элементы шли от наименьшего к наибольшему.
- Мы сортируем на месте: перемещаем элементы внутри одного и того же массива без возврата результата.
- Три классических метода делают это: пузырьковая, вставками и выбором (селективная) сортировка.
Обмен двух элементов
- Любая сортировка требует обмена двух элементов. Сохраните один во временную переменную, затем перезапишите.
int t = a[i]; a[i] = a[j]; a[j] = t;меняет местами индексыiиj.- Забыв про временную переменную, вы потеряете одно из значений — всегда сохраняйте её.
Пузырьковая сортировка
- Пройдите по массиву и сравните каждую пару соседних элементов:
a[j]иa[j + 1]. - Если они в неправильном порядке, поменяйте их местами. Наибольшее значение «всплывает» к концу.
- Повторяйте проходы, пока весь массив не будет упорядочен.
Сортировка вставками
- Рассматривайте левую часть массива как уже отсортированную и постепенно расширяйте её на один элемент за раз.
- Возьмите следующий элемент как ключ, сдвиньте большие отсортированные элементы вправо, затем поместите ключ на освободившееся место.
- Именно так многие люди сортируют игральные карты в руке.
#include <stdio.h>
int main(void) {
int a[] = {3, 1, 2};
// one bubble pass: compare neighbours and swap if out of order
for (int j = 0; j < 2; j++) {
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
printf("%d %d %d\n", a[0], a[1], a[2]); // 1 2 3
return 0;
}
Распространенные ошибки
- Пузырьковая, селективная и сортировка вставками имеют сложность O(n²).
- Трассируйте маленький массив вручную, чтобы проверить свою сортировку.
Теперь попробуйте сами
- Сортируйте по возрастанию (от меньшего к большему), на месте, без возврата значения.
- Чекер проверяет несколько вариантов массивов, включая отрицательные числа и уже отсортированный массив.
- Не пишите
main— проверяющая система предоставит его.
Просмотр работы сортировки
Пузырьковая, выборочная и сортировка вставками сравнивают элементы и меняют их местами для упорядочивания.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Заполните void swap(int a[], int i, int j) так, чтобы она меняла местами элементы с индексами i и j на месте (без возврата значения). Не пишите main.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Заполните void bubble_sort(int a[], int n) так, чтобы она сортировала массив по возрастанию на месте, используя сортировку пузырьком. Не пишите main.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Заполните void insertion_sort(int a[], int n) так, чтобы она сортировала массив по возрастанию на месте, используя сортировку вставками (берем каждый элемент как ключ и сдвигаем большие элементы вправо). Не пишите main.
Нажмите Запустить, чтобы увидеть результат здесь.