Сортировка

Инф 💻

Редакция Без Сменки

Честно. Понятно. С душой.

Сортировка — упорядочивание элементов в списке.

Потребность в сортировках встречается во многих задачах.

они нужны для поиска и представления данных.
некоторые задачи с неотсортированными данными решить сложно.

Отсортируем список А по возрастанию:
А= [31, 24, 88, 91, 10, 6, 54, 78]

Простая сортировка: организовать два цикла, сравнивать i-ый элемент со всеми последующими, если они идут не в нужном порядке — менять местами.

Такой метод понятен, но он имеет недостаток быстродействия. Происходит слишком много операций сравнения. При нескольких элементов сортировка сработает, а при больших данных нет. В промышленной разработке такая сортировка не используется.

Варианты сортировок:

Пузырьковая сортировка:
Шейкерная сортировка:
Сортировка подсчетом:
Сортировка вставками:
Быстрая сортировка и другие.

Способов много, главное их отличие друг от друга время работы и сложность.
В следующих шагах рассмотрим методы работы и реализации некоторых сортировок 🙂

Сортировка Пузырьком

Сортировка простым обменом или сортировка пузырьком — простой алгоритм сортировки.

Алгоритм сортировки:

сравнить текущий элемент со следующим;
если следующий элемент больше/меньше текущего, поменять их местами;
если массив отсортирован, закончить алгоритм, иначе перейти к шагу 1.

В каждом проходе внешнего цикла совершается серия обменов так, что наибольший элемент передвигается в конец массива перед элементом, который поместился туда на прошлой итерации.
Процесс происходит до тех пор, пока массив не будет отсортирован.

📍Внешний цикл в худшем варианте повторится N-1 раз, где N-кол-во элементов списка для сортировки).

Сортировка Подсчётом

Иногда сортируемые элементы имеют небольшой диапазон возможных значений.

Например: нужно отсортировать список натуральных чисел, каждое из которых меньше 1000 -> список чисел огромный, но сами числа лежат в очень узком диапазоне.

Для таких целей используется алгоритм сортировки подсчётом.

Как он работает? 😯

Найти максимальное значение в списке;
Создать вспомогательный список счётчиков повторений counters (количество ячеек этого списка = максимальному значению начального списка);
Пройти по начальному списку и увеличить счетчики, равные значению текущего элемента в вспомогательном списке;
Составить из списка счётчиков последовательность: число на индексе i встречается counters[i] раз.

Подробная реализация на картинке 👇

Рассмотрим пример:

Есть список a=[3,1,5,1,6,7,6,5]
max значение = 7. Значит в вспомогательном списке будет 7 ячеек: counters=[0,0,0,0,0,0,0].

Проходим по списку а:
a[0]=3, увеличиваем counters[3] на 1: сounters[3]=0+1=1
a[1]=1, сounters[1]=0+1=1
a[2]=5, сounters[5]=0+1=1
a[3]=1, сounters[1]=1+1=2
a[4]=6, сounters[6]=0+1=1
a[5]=7, сounters[7]=0+1=1
a[6]=6, сounters[6]=1+1=2
a[7]=5, сounters[5]=1+1=2

Незаполненные ячейки остаются пустыми.

Записываем ответ: 2 раза “1”, 0 раз “2”, 1 раз “3”, 0 раз “4”, 2 раза “5”, 2 раза “6”, 1 раз “7”=> 1 1 3 5 5 6 6 7		

Сортировка Хоара

Быстрая сортировка или сортировка Хоара, один из самых быстрых универсальных алгоритмов сортировки массивов. Именно он применяется в стандартных функциях сортировки во многих ЯП (в Python — sort() ).

Быстрая сортировка относится к алгоритмам «разделяй и властвуй» (парадигма разделения одной подзадачи на несколько меньшего размера).

Алгоритм состоит из трёх шагов:

Выбрать элемент из массива. Назовём его опорным.
Разбиение: перераспределение элементов в массиве таким образом, что элементы меньше опорного помещаются перед ним, а больше или равные после.
Рекурсивно применить первые два шага к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один элемент или отсутствуют элементы.