Working of the Bubble Sort
Урок 2 из 11 курса Сортировка пузырьком на Coddy.
Пузырьковая сортировка (Bubble sort) — это простой алгоритм сортировки, который проходит по элементам списка, сравнивает соседние элементы и меняет их местами, если они находятся в неправильном порядке.
Проход по списку повторяется до тех пор, пока список не будет отсортирован.
Пример-
Нам нужно отсортировать список из 4 элементов: [3,4,2,1]
Первый проход:
Сравнение первых двух элементов
[3,4,2,1] -> [3,4,2,1] (Без изменений, так как они уже отсортированы)
Сравнение следующих двух элементов
[3,4,2,1] -> [3,2,4,1] (Элементы меняются местами для достижения правильного порядка)
Сравнение следующих двух элементов
[3,2,4,1] -> [3,2,1,4] (Элементы меняются местами для достижения правильного порядка)
Первый проход завершен, что вы заметили?
Отсортирован ли список? — Нет, верно?
Значит, нам придется повторить процесс снова.
Обратите внимание, что после первого прохода максимальный элемент оказался в конце списка. И это именно то, чего мы будем пытаться достичь в ходе последующих проходов.
Второй проход:
Сравнение первых двух элементов
[3,2,1,4] -> [2,3,1,4] (Элементы меняются местами для достижения правильного порядка)
Сравнение следующих двух элементов
[2,3,1,4] -> [2,1,3,4] (Элементы меняются местами для достижения правильного порядка)
Сравнение следующих двух элементов
[2,1,3,4] -> [2,1,3,4] (Без изменений, так как они уже отсортированы)
После второго прохода заметьте, что последние два элемента отсортированы.
Третий проход:
Сравнение первых двух элементов
[2,1,3,4] -> [1,2,3,4] (Элементы меняются местами для достижения правильного порядка)
Заметьте, что после этого прохода мы получили нужный список.
Вот так работает ПУЗЫРЬКОВАЯ СОРТИРОВКА!
Теперь давайте разберем алгоритм пузырьковой сортировки в следующем уроке.
Приятного обучения!
Задание
ЛегкоСоздайте функцию с именем swap_list, которая принимает массив, размер массива и два индекса. Функция меняет местами элементы по этим двум индексам и возвращает новый список.
Например:
list=[1,2,3,4] (индексация с нуля)
n=4 (Количество элементов в списке)
i=1 j=3 (индексы для перестановки)
[1,2,3,4] -> [1,4,3,2]
Возвращает: list= [1,4,3,2]
Попробуйте сами
#include <stdio.h>
#include <stdlib.h>
int* swap_list(int* arr, int arr_size, int n, int i, int j, int* returnSize) {
// Напишите здесь код
*returnSize = n;
return arr;
}
Все уроки раздела Сортировка пузырьком
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm