Топ-5 алгоритмов сортировки на Python
Сортировка — это навык, которым должен обладать каждый программист. Не только для прохождения собеседований, но и для понимания дисциплины в целом. Разные алгоритмы сортировки — отличная демонстрация того, как внутренняя логика может влиять на сложность, скорость и эффективность программы.
Разберем 5 самых распространенных алгоритмов и реализуем их в Python.
Bubble Sort (пузырьковая сортировка)
Этот вид сортировки изучают в начале знакомства с дисциплиной Computer Science, поскольку он максимально просто демонстрирует саму концепцию сортировки.
При этом подходе осуществляется перебор по списку и сравнение соседних элементов. Они меняются местами в том случае, если порядок неправильный. Так продолжается до тех пор, пока все элементы не расположатся в нужном порядке. Из-за большого количества повторений у пузырьковой сортировки его сложность в худшем случае — O(n^2).
def bubble_sort(arr): def swap(i, j): arr[i], arr[j] = arr[j], arr[i] n = len(arr) swapped = True x = -1 while swapped: swapped = False x = x + 1 for i in range(1, n-x): if arr[i - 1] > arr[i]: swap(i - 1, i) swapped = True Selection Sort (сортировка выбором)
Сортировка выбором — также простой алгоритм, но более эффективный по сравнению с пузырьковой сортировкой. В большинстве случаев сортировка выбором будет более удачным выбором из двух.
В этом алгоритме список (или массив) делится на две части: список с отсортированными элементами и список с элементами, которые только нужно сортировать. Сначала ищется самый маленький элемент во втором. Он добавляется в конце первого. Таким образом алгоритм постепенно формирует список от меньшего к большему. Так происходит до тех пор, пока не будет готовый отсортированный массив.
def selection_sort(arr): for i in range(len(arr)): minimum = i for j in range(i + 1, len(arr)): # Выбор наименьшего значения if arr[j] arr[minimum]: minimum = j # Помещаем это перед отсортированным концом массива arr[minimum], arr[i] = arr[i], arr[minimum] return arr Insertion Sort (сортировка вставками)
Сортировка вставками быстрее и проще двух предыдущих. Именно так большинство людей тасует карты любой игре. На каждой итерации программа берет один из элементов и подыскивает для него место в уже отсортированном списке. Так происходит до тех пор, пока не останется ни одного неиспользованного элемента.
def insertion_sort(arr): for i in range(len(arr)): cursor = arr[i] pos = i while pos > 0 and arr[pos - 1] > cursor: # Меняем местами число, продвигая по списку arr[pos] = arr[pos - 1] pos = pos - 1 # Остановимся и сделаем последний обмен arr[pos] = cursor return arr Merge Sort (сортировка слиянием)
Сортировка слиянием — элегантный пример использования подхода «Разделяй и властвуй». Он состоит из двух этапов:
- Несортированный список последовательно делится на N списков, где каждый включает один «несортированный» элемент, а N — это число элементов в оригинальном массиве.
- Списки последовательно сливаются группами по два, создавая новые отсортированные списки до тех пор, пока не появится один финальный отсортированный список.
def merge_sort(arr): # Последнее разделение массива if len(arr) 1: return arr mid = len(arr) // 2 # Выполняем merge_sort рекурсивно с двух сторон left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:]) # Объединяем стороны вместе return merge(left, right, arr.copy()) def merge(left, right, merged): left_cursor, right_cursor = 0, 0 while left_cursor len(left) and right_cursor len(right): # Сортируем каждый и помещаем в результат if left[left_cursor] right[right_cursor]: merged[left_cursor+right_cursor]=left[left_cursor] left_cursor += 1 else: merged[left_cursor + right_cursor] = right[right_cursor] right_cursor += 1 for left_cursor in range(left_cursor, len(left)): merged[left_cursor + right_cursor] = left[left_cursor] for right_cursor in range(right_cursor, len(right)): merged[left_cursor + right_cursor] = right[right_cursor] return merged Quick Sort (быстрая сортировка)
Как и сортировка слиянием, быстрая сортировка использует подход «Разделяй и властвуй». Алгоритм чуть сложнее, но в стандартных реализациях он работает быстрее сортировки слиянием, а его сложность в худшем случае редко достигает O(n^2). Он состоит из трех этапов:
- Выбирается один опорный элемент.
- Все элементы меньше опорного перемешаются слева от него, остальные — направо. Это называется операцией разбиения.
- Рекурсивно повторяются 2 предыдущих шага к каждому новому списку, где новые опорные элементы будут меньше и больше оригинального соответственно.
def partition(array, begin, end): pivot_idx = begin for i in xrange(begin+1, end+1): if array[i] array[begin]: pivot_idx += 1 array[i], array[pivot_idx] = array[pivot_idx], array[i] array[pivot_idx], array[begin] = array[begin], array[pivot_idx] return pivot_idx def quick_sort_recursion(array, begin, end): if begin >= end: return pivot_idx = partition(array, begin, end) quick_sort_recursion(array, begin, pivot_idx-1) quick_sort_recursion(array, pivot_idx+1, end) def quick_sort(array, begin=0, end=None): if end is None: end = len(array) - 1 return quick_sort_recursion(array, begin, end) Объяснение алгоритмов сортировки с примерами на Python
В этой статье рассмотрены популярные алгоритмы, принципы их работы и реализация на Python. Также сравним, как быстро они сортируют элементы в списке.
В этой статье будут рассмотрены популярные алгоритмы, принципы их работы и реализация на Python. А ещё сравним, как быстро они сортируют элементы в списке.
В качестве общего примера возьмём сортировку чисел в порядке возрастания. Но эти методы можно легко адаптировать под ваши потребности.
Пузырьковая сортировка
Этот простой алгоритм выполняет итерации по списку, сравнивая элементы попарно и меняя их местами, пока более крупные элементы не «всплывут» в начало списка, а более мелкие не останутся на «дне».
Алгоритм
Сначала сравниваются первые два элемента списка. Если первый элемент больше, они меняются местами. Если они уже в нужном порядке, оставляем их как есть. Затем переходим к следующей паре элементов, сравниваем их значения и меняем местами при необходимости. Этот процесс продолжается до последней пары элементов в списке.
При достижении конца списка процесс повторяется заново для каждого элемента. Это крайне неэффективно, если в массиве нужно сделать, например, только один обмен. Алгоритм повторяется n² раз, даже если список уже отсортирован.
Для оптимизации алгоритма нужно знать, когда его остановить, то есть когда список отсортирован.
Чтобы остановить алгоритм по окончании сортировки, нужно ввести переменную-флаг. Когда значения меняются местами, устанавливаем флаг в значение True , чтобы повторить процесс сортировки. Если перестановок не произошло, флаг остаётся False и алгоритм останавливается.
Реализация
def bubble_sort(nums): # Устанавливаем swapped в True, чтобы цикл запустился хотя бы один раз swapped = True while swapped: swapped = False for i in range(len(nums) - 1): if nums[i] > nums[i + 1]: # Меняем элементы nums[i], nums[i + 1] = nums[i + 1], nums[i] # Устанавливаем swapped в True для следующей итерации swapped = True # Проверяем, что оно работает random_list_of_nums = [5, 2, 1, 8, 4] bubble_sort(random_list_of_nums) print(random_list_of_nums) Алгоритм работает в цикле while и прерывается, когда элементы ни разу не меняются местами. Вначале присваиваем swapped значение True , чтобы алгоритм запустился хотя бы один раз.
Время сортировки
Если взять самый худший случай (изначально список отсортирован по убыванию), затраты времени будут равны O(n²), где n — количество элементов списка.
Сортировка выборкой
Этот алгоритм сегментирует список на две части: отсортированную и неотсортированную. Наименьший элемент удаляется из второго списка и добавляется в первый.
Алгоритм
На практике не нужно создавать новый список для отсортированных элементов. В качестве него используется крайняя левая часть списка. Находится наименьший элемент и меняется с первым местами.
Теперь, когда нам известно, что первый элемент списка отсортирован, находим наименьший элемент из оставшихся и меняем местами со вторым. Повторяем это до тех пор, пока не останется последний элемент в списке.
Реализация
def selection_sort(nums): # Значение i соответствует кол-ву отсортированных значений for i in range(len(nums)): # Исходно считаем наименьшим первый элемент lowest_value_index = i # Этот цикл перебирает несортированные элементы for j in range(i + 1, len(nums)): if nums[j] < nums[lowest_value_index]: lowest_value_index = j # Самый маленький элемент меняем с первым в списке nums[i], nums[lowest_value_index] = nums[lowest_value_index], nums[i] # Проверяем, что оно работает random_list_of_nums = [12, 8, 3, 20, 11] selection_sort(random_list_of_nums) print(random_list_of_nums)По мере увеличения значения i нужно проверять меньше элементов.
Время сортировки
Затраты времени на сортировку выборкой в среднем составляют O(n²), где n — количество элементов списка.
Сортировка вставками
Как и сортировка выборкой, этот алгоритм сегментирует список на две части: отсортированную и неотсортированную. Алгоритм перебирает второй сегмент и вставляет текущий элемент в правильную позицию первого сегмента.
Алгоритм
Предполагается, что первый элемент списка отсортирован. Переходим к следующему элементу, обозначим его х . Если х больше первого, оставляем его на своём месте. Если он меньше, копируем его на вторую позицию, а х устанавливаем как первый элемент.
Переходя к другим элементам несортированного сегмента, перемещаем более крупные элементы в отсортированном сегменте вверх по списку, пока не встретим элемент меньше x или не дойдём до конца списка. В первом случае x помещается на правильную позицию.
Реализация
def insertion_sort(nums): # Сортировку начинаем со второго элемента, т.к. считается, что первый элемент уже отсортирован for i in range(1, len(nums)): item_to_insert = nums[i] # Сохраняем ссылку на индекс предыдущего элемента j = i - 1 # Элементы отсортированного сегмента перемещаем вперёд, если они больше # элемента для вставки while j >= 0 and nums[j] > item_to_insert: nums[j + 1] = nums[j] j -= 1 # Вставляем элемент nums[j + 1] = item_to_insert # Проверяем, что оно работает random_list_of_nums = [9, 1, 15, 28, 6] insertion_sort(random_list_of_nums) print(random_list_of_nums) Время сортировки
Время сортировки вставками в среднем равно O(n²), где n — количество элементов списка.
Пирамидальная сортировка
Также известна как сортировка кучей. Этот популярный алгоритм, как и сортировки вставками или выборкой, сегментирует список на две части: отсортированную и неотсортированную. Алгоритм преобразует второй сегмент списка в структуру данных «куча» (heap), чтобы можно было эффективно определить самый большой элемент.
Алгоритм
Сначала преобразуем список в Max Heap — бинарное дерево, где самый большой элемент является вершиной дерева. Затем помещаем этот элемент в конец списка. После перестраиваем Max Heap и снова помещаем новый наибольший элемент уже перед последним элементом в списке.
Этот процесс построения кучи повторяется, пока все вершины дерева не будут удалены.
Реализация
Создадим вспомогательную функцию heapify() для реализации этого алгоритма:
def heapify(nums, heap_size, root_index): # Индекс наибольшего элемента считаем корневым индексом largest = root_index left_child = (2 * root_index) + 1 right_child = (2 * root_index) + 2 # Если левый потомок корня — допустимый индекс, а элемент больше, # чем текущий наибольший, обновляем наибольший элемент if left_child < heap_size and nums[left_child] >nums[largest]: largest = left_child # То же самое для правого потомка корня if right_child < heap_size and nums[right_child] >nums[largest]: largest = right_child # Если наибольший элемент больше не корневой, они меняются местами if largest != root_index: nums[root_index], nums[largest] = nums[largest], nums[root_index] # Heapify the new root element to ensure it's the largest heapify(nums, heap_size, largest) def heap_sort(nums): n = len(nums) # Создаём Max Heap из списка # Второй аргумент означает остановку алгоритма перед элементом -1, т.е. # перед первым элементом списка # 3-й аргумент означает повторный проход по списку в обратном направлении, # уменьшая счётчик i на 1 for i in range(n, -1, -1): heapify(nums, n, i) # Перемещаем корень Max Heap в конец списка for i in range(n - 1, 0, -1): nums[i], nums[0] = nums[0], nums[i] heapify(nums, i, 0) # Проверяем, что оно работает random_list_of_nums = [35, 12, 43, 8, 51] heap_sort(random_list_of_nums) print(random_list_of_nums) Время сортировки
В среднем время сортировки кучей составляет O(n log n), что уже значительно быстрее предыдущих алгоритмов.
Сортировка слиянием
Этот алгоритм относится к алгоритмам «разделяй и властвуй». Он разбивает список на две части, каждую из них он разбивает ещё на две и т. д. Список разбивается пополам, пока не останутся единичные элементы.
Соседние элементы становятся отсортированными парами. Затем эти пары объединяются и сортируются с другими парами. Этот процесс продолжается до тех пор, пока не отсортируются все элементы.
Алгоритм
Список рекурсивно разделяется пополам, пока в итоге не получатся списки размером в один элемент. Массив из одного элемента считается упорядоченным. Соседние элементы сравниваются и соединяются вместе. Это происходит до тех пор, пока не получится полный отсортированный список.
Сортировка осуществляется путём сравнения наименьших элементов каждого подмассива. Первые элементы каждого подмассива сравниваются первыми. Наименьший элемент перемещается в результирующий массив. Счётчики результирующего массива и подмассива, откуда был взят элемент, увеличиваются на 1.
Реализация
def merge(left_list, right_list): sorted_list = [] left_list_index = right_list_index = 0 # Длина списков часто используется, поэтому создадим переменные для удобства left_list_length, right_list_length = len(left_list), len(right_list) for _ in range(left_list_length + right_list_length): if left_list_index < left_list_length and right_list_index < right_list_length: # Сравниваем первые элементы в начале каждого списка # Если первый элемент левого подсписка меньше, добавляем его # в отсортированный массив if left_list[left_list_index] Обратите внимание, что функция merge_sort() , в отличие от предыдущих алгоритмов, возвращает новый список, а не сортирует существующий. Поэтому такая сортировка требует больше памяти для создания нового списка того же размера, что и входной список.
Время сортировки
В среднем время сортировки слиянием составляет O(n log n).
Быстрая сортировка
Этот алгоритм также относится к алгоритмам «разделяй и властвуй». Его используют чаще других алгоритмов, описанных в этой статье. При правильной конфигурации он чрезвычайно эффективен и не требует дополнительной памяти, в отличие от сортировки слиянием. Массив разделяется на две части по разные стороны от опорного элемента. В процессе сортировки элементы меньше опорного помещаются перед ним, а равные или большие —позади.
Алгоритм
Быстрая сортировка начинается с разбиения списка и выбора одного из элементов в качестве опорного. А всё остальное передвигаем так, чтобы этот элемент встал на своё место. Все элементы меньше него перемещаются влево, а равные и большие элементы перемещаются вправо.
Реализация
Существует много вариаций данного метода. Способ разбиения массива, рассмотренный здесь, соответствует схеме Хоара (создателя данного алгоритма).
def partition(nums, low, high): # Выбираем средний элемент в качестве опорного # Также возможен выбор первого, последнего # или произвольного элементов в качестве опорного pivot = nums[(low + high) // 2] i = low - 1 j = high + 1 while True: i += 1 while nums[i] < pivot: i += 1 j -= 1 while nums[j] >pivot: j -= 1 if i >= j: return j # Если элемент с индексом i (слева от опорного) больше, чем # элемент с индексом j (справа от опорного), меняем их местами nums[i], nums[j] = nums[j], nums[i] def quick_sort(nums): # Создадим вспомогательную функцию, которая вызывается рекурсивно def _quick_sort(items, low, high): if low < high: # This is the index after the pivot, where our lists are split split_index = partition(items, low, high) _quick_sort(items, low, split_index) _quick_sort(items, split_index + 1, high) _quick_sort(nums, 0, len(nums) - 1) # Проверяем, что оно работает random_list_of_nums = [22, 5, 1, 18, 99] quick_sort(random_list_of_nums) print(random_list_of_nums)Время выполнения
В среднем время выполнения быстрой сортировки составляет O(n log n).
Обратите внимание, что алгоритм быстрой сортировки будет работать медленно, если опорный элемент равен наименьшему или наибольшему элементам списка. При таких условиях, в отличие от сортировок кучей и слиянием, обе из которых имеют в худшем случае время сортировки O(n log n), быстрая сортировка в худшем случае будет выполняться O(n²).
Встроенные функции сортировки на Python
Иногда полезно знать перечисленные выше алгоритмы, но в большинстве случаев разработчик, скорее всего, будет использовать функции сортировки, уже предоставленные в языке программирования.
Отсортировать содержимое списка можно с помощью стандартного метода sort() :
>>> apples_eaten_a_day = [2, 1, 1, 3, 1, 2, 2] >>> apples_eaten_a_day.sort() >>> apples_eaten_a_day [1, 1, 1, 2, 2, 2, 3] Или можно использовать функцию sorted() для создания нового отсортированного списка, оставив входной список нетронутым:
>>> apples_eaten_a_day_2 = [2, 1, 1, 3, 1, 2, 2] >>> sorted_apples = sorted(apples_eaten_a_day_2) >>> sorted_apples [1, 1, 1, 2, 2, 2, 3] Оба эти метода сортируют в порядке возрастания, но можно изменить порядок, установив для флага reverse значение True :
# Обратная сортировка списка на месте >>> apples_eaten_a_day.sort(reverse=True) >>> apples_eaten_a_day [3, 2, 2, 2, 1, 1, 1] # Обратная сортировка, чтобы получить новый список >>> sorted_apples_desc = sorted(apples_eaten_a_day_2, reverse=True) >>> sorted_apples_desc [3, 2, 2, 2, 1, 1, 1] В отличие от других алгоритмов, обе функции в Python могут сортировать также списки кортежей и классов. Функция sorted() может сортировать любую последовательность, которая включает списки, строки, кортежи, словари, наборы и пользовательские итераторы, которые вы можете создать.
Функции в Python реализуют алгоритм Tim Sort, основанный на сортировке слиянием и сортировке вставкой.
Сравнение скоростей сортировок
Для сравнения сгенерируем массив из 5000 чисел от 0 до 1000. Затем определим время, необходимое для завершения каждого алгоритма. Повторим каждый метод 10 раз, чтобы можно было более точно установить, насколько каждый из них производителен.
Пузырьковая сортировка — самый медленный из всех алгоритмов. Возможно, он будет полезен как введение в тему алгоритмов сортировки, но не подходит для практического использования.
Быстрая сортировка хорошо оправдывает своё название, почти в два раза быстрее, чем сортировка слиянием, и не требуется дополнительное место для результирующего массива.
Сортировка вставками выполняет меньше сравнений, чем сортировка выборкой и в реальности должна быть производительнее, но в данном эксперименте она выполняется немного медленней. Сортировка вставками делает гораздо больше обменов элементами. Если эти обмены занимают намного больше времени, чем сравнение самих элементов, то такой результат вполне закономерен.
Вы познакомились с шестью различными алгоритмами сортировок и их реализациями на Python. Масштаб сравнения и количество перестановок, которые выполняет алгоритм вместе со средой выполнения кода, будут определяющими факторами в производительности. В реальных приложениях Python рекомендуется использовать встроенные функции сортировки, поскольку они реализованы именно для удобства разработчика.
Виды алгоритмов сортировки в Python
В одной из прошлых статей я рассматривал списки в Python, а также затронул их сортировку. Теперь давайте разберем эту тему более подробно: изучим виды алгоритмов сортировки и сравним их скорость на примере сортировки чисел в порядке возрастания.
Встроенные методы сортировки в Python
Стандартный метод сортировки списка по возрастанию – sort(). Пример использования:
nums = [54, 43, 3, 11, 0] nums.sort() print(nums) # Выведет [0, 3, 11, 43, 54]
Метод sorted() создает новый отсортированный список, не изменяя исходный. Пример использования:
nums = [54, 43, 3, 11, 0] nums2 = sorted(nums) print(nums, nums2) # Выведет [54, 43, 3, 11, 0] [0, 3, 11, 43, 54]
Если нам нужна сортировка от большего числа к меньшему, то установим флаг reverse=True. Примеры:
nums = [54, 43, 3, 11, 0] nums.sort(reverse=True) print(nums) # Выведет [54, 43, 11, 3, 0] nums = [54, 43, 3, 11, 0] nums2 = sorted(nums, reverse=True) print(nums, nums2) # Выведет [54, 43, 3, 11, 0] [54, 43, 11, 3, 0]
Но будет полезно знать и другие виды сортировки, так как не всегда встроенные методы будут подходить под все ваши задачи.
Комьюнити теперь в Телеграм
Подпишитесь и будьте в курсе последних IT-новостей
Пузырьковая сортировка
Алгоритм попарно сравнивает элементы списка, меняя их местами, если это требуется. Он не так эффективен, если нам нужно сделать только один обмен в списке, так как данный алгоритм при достижении конца списка будет повторять процесс заново. Чтобы алгоритм не выполнялся бесконечно, мы вводим переменную, которая поменяет свое значение с True на False, если после запуска алгоритма список не изменился.
Сравниваются первые два элемента. Если первый элемент больше, то они меняются местами. Далее происходит все то же самое, но со следующими элементами до последней пары элементов в списке.
Пример пузырьковой сортировки:
def bubble(list_nums): swap_bool = True while swap_bool: swap_bool = False for i in range(len(list_nums) - 1): if list_nums[i] > list_nums[i + 1]: list_nums[i], list_nums[i + 1] = list_nums[i + 1], list_nums[i] swap_bool = True nums = [54, 43, 3, 11, 0] bubble(nums) print(nums) # Выведет [0, 3, 11, 43, 54]
Сортировка вставками
Алгоритм делит список на две части, вставляя элементы на их правильные места во вторую часть списка, убирая их из первой.
Если второй элемент больше первого, то оставляем его на своем месте. Если он меньше, то вставляем его на второе место, оставив первый элемент на первом месте. Далее перемещаем большие элементы во второй части списка вверх, пока не встретим элемент меньше первого или не дойдем до конца списка.
Пример сортировки вставками:
def insertion(list_nums): for i in range(1, len(list_nums)): item = list_nums[i] i2 = i - 1 while i2 >= 0 and list_nums[i2] > item: list_nums[i2 + 1] = list_nums[i2] i2 -= 1 list_nums[i2 + 1] = item nums = [54, 43, 3, 11, 0] insertion(nums) print(nums) # Выведет [0, 3, 11, 43, 54]
Сортировка выборкой
Как и сортировка вставками, этот алгоритм в Python делит список на две части: основную и отсортированную. Наименьший элемент удаляется из основной части и переходит в отсортированную.
Саму отсортированную часть можно и не создавать, обычно используют крайнюю часть списка. И когда находится наименьший элемент списка, то переносим его на первое место, вставляя первый элемент на прошлое порядковое место наименьшего. Далее делаем все то же самое, но со следующим элементом, пока не достигнем конца списка.
Пример сортировки выборкой:
def selection(sort_nums): for i in range(len(sort_nums)): index = i for j in range(i + 1, len(sort_nums)): if sort_nums[j] < sort_nums[index]: index = j sort_nums[i], sort_nums[index] = sort_nums[index], sort_nums[i] nums = [54, 43, 3, 11, 0] selection(nums) print(nums) # Выведет [0, 3, 11, 43, 54]
Пирамидальная сортировка
Этот алгоритм, как и сортировки вставками или выборкой, делит список на две части. Алгоритм преобразует вторую часть списка в бинарное дерево для эффективного определения самого большого элемента.
Преобразуем список в бинарное дерево, где самый большой элемент является вершиной дерева, и помещаем этот элемент в конец списка. После перестраиваем дерево и помещаем новый наибольший элемент перед последним элементом в списке. Повторяем этот алгоритм, пока все вершины дерева не будут удалены.
Хоть алгоритм и кажется сложным, он значительно быстрее остальных, что особенно заметно при обработке больших списков.
Пример пирамидальной сортировки:
def heapify(sort_nums, heap_size, root): l = root left = (2 * root) + 1 right = (2 * root) + 2 if left < heap_size and sort_nums[left] >sort_nums[l]: l = left if right < heap_size and sort_nums[right] >sort_nums[l]: l = right if l != root: sort_nums[root], sort_nums[l] = sort_nums[l], sort_nums[root] heapify(sort_nums, heap_size, l) def heap(sort_nums): size = len(sort_nums) for i in range(size, -1, -1): heapify(sort_nums, size, i) for i in range(size - 1, 0, -1): sort_nums[i], sort_nums[0] = sort_nums[0], sort_nums[i] heapify(sort_nums, i, 0) nums = [54, 43, 3, 11, 0] heap(nums) print(nums) # Выведет [0, 3, 11, 43, 54]
Сортировка слиянием
Алгоритм разделяет список на две части, каждую из них он разделяет еще на две и так далее, пока не останутся отдельные единичные элементы. Далее соседние элементы сортируются парами. Затем эти пары объединяются и сортируются с другими парами, пока не обработаются все элементы в списке.
Пример сортировки слиянием:
def mergeSort(sort_nums): if len(sort_nums)>1: mid = len(sort_nums)//2 lefthalf = sort_nums[:mid] righthalf = sort_nums[mid:] mergeSort(lefthalf) mergeSort(righthalf) i=0 j=0 k=0 while iБыстрая сортировка в Python
Один из самых популярных алгоритмов при сортировке списков. При правильном использовании он не требует много памяти и выполняется очень быстро.
Алгоритм разделяет список на две равные части, принимая псевдослучайный элемент и используя его в качестве опоры, то есть центра деления. Элементы, меньшие, чем опора, перемещаются влево от опоры, а элементы, размер которых больше опоры – вправо. Этот процесс повторяется для списка слева от опоры, а также для массива элементов справа от опоры, пока весь массив не будет отсортирован. Алгоритм быстрой сортировки будет работать медленно, если опорный элемент равен наименьшему или наибольшему элементу списка.
Пример быстрой сортировки:
def partition(sort_nums, begin, end): part = begin for i in range(begin+1, end+1): if sort_nums[i] = end: return part = partition(sort_nums, begin, end) quick(sort_nums, begin, part-1) quick(sort_nums, part+1, end) return quick(sort_nums, begin, end) nums = [54, 43, 3, 11, 0] quick_sort(nums) print(nums) # Выведет [0, 3, 11, 43, 54]Скорость работы алгоритмов
Сортировка слиянием почти в два раза медленнее, чем быстрая сортировка. Сортировка выборкой выполняет больше сравнений, чем сортировка вставками, но выполняется немного быстрее.
Пузырьковая сортировка не подойдет для практического применения, так как она является самой медленной из всех. Но знать данный алгоритм будет полезно тем, кто хочет полностью изучить тему алгоритмов сортировки списков в Python.
Итог
Мы изучили виды сортировки списков в Python и сравнили их эффективность, а также рассмотрели встроенные методы. Надеюсь, данная статья была полезна для вас!
8 методов сортировок Python
Если вы программист или уже проходили собеседование, то наверняка знаете о важности знания алгоритмов, чтобы повысить свой уровень программирования или получить шанс получить работу.
При работе с данными сортировка - одна из важнейших задач. Cуществует множество методов сортировки данных, некоторые из них лучше других, некоторые более эффективны для конкретных целей.
В зависимости от метода (рекурсия, итерация, сравнения) или используемых структур данных, можно использовать разные методы сортировки.Самые популярные методы сортировки Python:
Пузырьковая сортировка:
Пузырьковая сортировка - простой алгоритм сортировки, который работает, меняя местами элементы между собой, если они находятся в неправильном порядке.
Пример :#Bubble Sort Algorithm def bubbleSort(data): lenght = len(data) for iIndex in range(lenght): swapped = False for jIndex in range(0, lenght - iIndex - 1): if data[jIndex] > data[jIndex + 1]: data[jIndex], data[jIndex + 1] = data[jIndex + 1], data[jIndex] swapped = True if swapped == False: break print(data)Пузырьковая сортировка используется, когда:
- предпочтителен простой код;
- сложность не имеет значения.
Выборочная сортировка
Выборочная сортировка, или сортировка выбором - это улучшенная версия пузырьковой сортировки, повышающая производительность. Даже в случае, если они имеют одинаковую производительность, выборочная сортировка выполняет меньше замен.
Сортировка выбором работает одним из двух способов: либо ищет наименьший элемент в списке и помещает его в начало списка (обеспечивая правильное расположение элемента), либо ищет самый крупный элемент и помещает его в конец списка.
Пример:#Selection Sort Algorithm def selectionSort(data): for scanIndex in range(0, len(data)): minIndex = scanIndex for compIndex in range(scanIndex + 1, len(data)): if data[compIndex] < data[minIndex]: minIndex = compIndex if minIndex != scanIndex: data[scanIndex], data[minIndex] = data[minIndex], data[scanIndex] print(data)Сортировка по выбору используется, когда:
- Сортировка небольших массивов
- Требуется меньше подкачки
Сортировка вставками
Сортировка вставками - это алгоритм сортировки методом "грубой силы", он выполняет меньше сравнений, чем сортировка выбором.
Сортировка вставкой работает, выбирая элемент и сравнивает соседние элементы в массиве, чтобы определить позицию, где первый элемент меньше, а второй больше, чем выбранный элемент. По мере увеличения числа отсортированных элементов алгоритм сравнивает новые элементы с отсортированными и вставляет новый элемент в нужную позицию в списке.
Пример :#Insertion Sort Algorithm def insertionSort(data): for scanIndex in range(1, len(data)): tmp = data[scanIndex] minIndex = scanIndex while minIndex > 0 and tmp < data[minIndex - 1]: data[minIndex] = data[minIndex - 1] minIndex -= 1 data[minIndex] = tmp print(data)Сортировка вставкой используется, когда:
- Осталось отсортировать несколько элементов;
- Массив небольшой.
Быстрая сортировка
Быстрая сортировка - эффективный алгоритм сортировки. Он использует подход «разделяй-властвуй» для разделения массива на подмассивы, которые рекурсивно вызываются для сортировки элементов.
Для реализации алгоритма быстрой сортировки необходимо выбрать точку поворота, затем разделить массив на два подмассива в соответствии с точкой поворота, а затем расположить их, если они больше / меньше точки поворота. Затем мы сортируем два подмассива и повторяем процесс снова.
Пример :#Quick Sort Algorithm def quickSort(data, left, right): if right= leftIndex and data[rightIndex] >= pivot: rightIndex -= 1 if rightIndexQuickSort используется, когда:
- Рекурсия необходима и поддерживается;
- Массив небольшой;
- Осталось отсортировать несколько элементов.
Сортировка слиянием
Сортировка слиянием работает, применяя подход «разделяй и властвуй». Сортировка начинается с разбиения набора данных на отдельные части и сортировки частей. Затем он объединяет части таким образом, чтобы гарантировать, что она отсортировала объединенную часть.
Сортировка и объединение продолжаются до тех пор, пока весь набор данных снова не станет единым целым.
Пример:Пример сортировки слиянием. Сначала разделите список на наименьшую единицу (1 элемент), затем сравните каждый элемент со смежным списком, чтобы отсортировать и объединить два соседних списка. Наконец, все элементы сортируются и объединяются.
#Merge Sort Algorithm def mergeSort(data): """This function determines whether the list is broken into individual parts""" if len(data) < 2: return data middle = len(data)//2 # We break the list in two parts left = mergeSort(data[:middle]) right = mergeSort(data[middle:]) # Merge the two sorted parts into a larger piece. print("The left side is: ", left) print("The right side is: ", right) merged = merge(left, right) print("Merged ", merged) return merged def merge(left, right): """When left side/right side is empty, It means that this is an individual item and is already sorted.""" #We make sure the right/left side is not empty #meaning that it's an individual item and it's already sorted. if not len(left): return left if not len(right): return right result = [] leftIndex = 0 rightIndex = 0 totalLen = len(left) + len(right) # while (len(result) < totalLen): #Perform the required comparisons and merge the two parts if left[leftIndex] < right[rightIndex]: result.append(left[leftIndex]) leftIndex += 1 else: result.append(right[rightIndex]) rightIndex += 1 if leftIndex == len(left) or rightIndex == len(right): result.extend(left[leftIndex:] or right[rightIndex:]) break return resultСортировка по сегментам
Алгоритм сортировки по сегментам работает путем разделения массива на сегменты. Затем элементы в каждом сегменте сортируются с использованием любых алгоритмов сортировки или путем рекурсивного вызова алгоритма сортировки сегментами.
Процесс сортировки можно рассматривать как метод разброса-сбора. Элементы сначала раскладываются по сегментам, затем элементы сегментов сортируются. Наконец, элементы собраны по порядку.
Пример:Код:
#Bucket Sort Algorithm def bucketSort(data): bucket = [] for iIndex in range(len(data)): bucket.append([]) for jIndex in data: index_bucket = int(10 * jIndex) bucket[index_bucket].append(jIndex) print(bucket) for iIndex in range(len(data)): #I used the built-in method sorted() to sort the array. bucket[iIndex] = sorted(bucket[iIndex]) kIndex = 0 for iIndex in range(len(data)): for jIndex in range(len(bucket[iIndex])): data\[kIndex] = bucket[iIndex\][jIndex] kIndex += 1 print(data)Сортировка сегментами используется в следующих случаях:
- С плавающими числами;
- Входные данные равномерно распределяются по диапазону.
Сортировка Шелла
Сортировка Шелла - это разновидность сортировки вставкой. С помощью этого алгоритма массив сортируется с определенным интервалом на основе выбранной последовательности. Интервал между элементами постепенно уменьшается в зависимости от используемой последовательности. Производительность сортировки оболочки зависит от типа последовательности, используемой для данного входного массива.
Пример:Gif от GfyCat
Код:#Shell Sort Algorithm def shellSort(data, length): gap = length//2 while gap > 0: for iIndex in range(gap, length): temp = data[iIndex] jIndex = iIndex while jIndex >= gap and data[jIndex - gap] > temp: data[jIndex] = data[jIndex - gap] jIndex -= gap data[jIndex] = temp gap //= 2 print(data)Сортировка Шелла используется, когда:
- Рекурсия превышает предел.
- Вставка не работает, когда соседние элементы находятся далеко.
Пирамидальная сортировка
Пирамидальная сортировка (ее еще называют сортировкой кучей) - один из лучших методов сортировки без квадратичной сложности наихудшего случая. Это метод сортировки сравнением, основанный на такой структуре данных как двоичная куча. Она похожа на сортировку выбором, где мы сначала ищем максимальный элемент и помещаем его в конец. Далее мы повторяем ту же операцию для оставшихся элементов.
Пирамида - это полное двоичное дерево. Он также проверяет такие правила, как:
- Дети меньше родителей;
- Самый большой / самый маленький элемент находится в корне кучи, в зависимости от того, как вы его отсортировали.
Чтобы создать алгоритм сортировки кучи, мы должны сначала создать кучу массива. Когда закончите, теперь мы можем написать алгоритм сортировки кучи. Преимущество сортировки состоит в том, что значение в корне всегда больше, чем все значения, поэтому мы можем поместить его в конец отсортированного массива, удалить его из кучи, а затем снова скопировать двоичное дерево, чтобы получить большее значение. снова наверху.
Пример:
Код:
#Heap Sort Algorithm def createHeap(data, length, index): largest = index left = 2 * index + 1 right = 2 * index + 2 if left < length and data[index] < data[left]: largest = left if right < length and data[largest] < data[right]: largest = right if largest != index: data[index], data[largest] = data[largest], data[index] createHeap(data, length, largest) def heapSort(data): length = len(data) #We build max heap for index in range(length, 0, -1): createHeap(data, length, index) for index in range(length -1, 0, -1): data[index], data[0] = data[0], data[index] createHeap(data, index, 0) print(data)
Пирамидальная сортировка отлично подходит, когда вам нужно знать только «самый маленький» (или «самый большой») из коллекции элементов, без накладных расходов на сохранение оставшихся элементов в отсортированном порядке. Например, приоритетная очередь.
Зарегистрируйтесь на Портале
и получите красивый адрес своей странички вида: senior.ua/sergey.ivanov