Сортировка

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

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

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

Отсортируем список А по возрастанию:
А= [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].

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

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

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

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

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