Способы сортировки массива питон

Топ-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 (сортировка слиянием)

Сортировка слиянием — элегантный пример использования подхода «Разделяй и властвуй». Он состоит из двух этапов:

1. Несортированный список последовательно делится на N списков, где каждый включает один «несортированный» элемент, а N — это число элементов в оригинальном массиве.
2. Списки последовательно сливаются группами по два, создавая новые отсортированные списки до тех пор, пока не появится один финальный отсортированный список.

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). Он состоит из трех этапов:

1. Выбирается один опорный элемент.
2. Все элементы меньше опорного перемешаются слева от него, остальные — направо. Это называется операцией разбиения.
3. Рекурсивно повторяются 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

Стандартный метод сортировки списка по возрастанию – 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]

Но будет полезно знать и другие виды сортировки, так как не всегда встроенные методы будут подходить под все ваши задачи.

Пузырьковая сортировка

Алгоритм попарно сравнивает элементы списка, меняя их местами, если это требуется. Он не так эффективен, если нам нужно сделать только один обмен в списке, так как данный алгоритм при достижении конца списка будет повторять процесс заново. Чтобы алгоритм не выполнялся бесконечно, мы вводим переменную, которая поменяет свое значение с 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 и сравнили их эффективность, а также рассмотрели встроенные методы. Надеюсь, данная статья была полезна для вас!
 
Источник
 
Читайте также:  Java what is spliterator