Сортировка — упорядочивание элементов в списке.
Потребность в сортировках встречается во многих задачах.
Отсортируем список А по возрастанию:
А= [31, 24, 88, 91, 10, 6, 54, 78]
Простая сортировка: организовать два цикла, сравнивать i-ый элемент со всеми последующими, если они идут не в нужном порядке — менять местами.
Такой метод понятен, но он имеет недостаток быстродействия. Происходит слишком много операций сравнения. При нескольких элементов сортировка сработает, а при больших данных нет. В промышленной разработке такая сортировка не используется.
Варианты сортировок:
Способов много, главное их отличие друг от друга время работы и сложность.
В следующих шагах рассмотрим методы работы и реализации некоторых сортировок 🙂
Сортировка простым обменом или сортировка пузырьком — простой алгоритм сортировки.
Алгоритм сортировки:
В каждом проходе внешнего цикла совершается серия обменов так, что наибольший элемент передвигается в конец массива перед элементом, который поместился туда на прошлой итерации.
Процесс происходит до тех пор, пока массив не будет отсортирован.
📍Внешний цикл в худшем варианте повторится N-1 раз, где N-кол-во элементов списка для сортировки).
Иногда сортируемые элементы имеют небольшой диапазон возможных значений.
Например: нужно отсортировать список натуральных чисел, каждое из которых меньше 1000 -> список чисел огромный, но сами числа лежат в очень узком диапазоне.
Для таких целей используется алгоритм сортировки подсчётом.
Как он работает? 😯
Подробная реализация на картинке 👇
Рассмотрим пример:
Есть список a=[3,1,5,1,6,7,6,5]
max значение = 7. Значит в вспомогательном списке будет 7 ячеек: counters=[0,0,0,0,0,0,0].
Незаполненные ячейки остаются пустыми.
Быстрая сортировка или сортировка Хоара, один из самых быстрых универсальных алгоритмов сортировки массивов. Именно он применяется в стандартных функциях сортировки во многих ЯП (в Python — sort() ).
Быстрая сортировка относится к алгоритмам «разделяй и властвуй» (парадигма разделения одной подзадачи на несколько меньшего размера).
Алгоритм состоит из трёх шагов:
Авторизуйтесь, чтобы оставить комментарий.