Сортировка — одна из наиболее часто используемых функций в программировании. И потребуется время, чтобы завершить сортировку, если мы использовали неправильный алгоритм.
В этой статье мы обсудим различные алгоритмы сортировки.
Мы познакомим вас с различными алгоритмами сортировки на каждом этапе реализации. Часть реализации будет на Python. Вы можете легко преобразовать его на любой язык, как только получите алгоритм. Это вопрос синтаксиса языка.
В этом руководстве мы увидим разные алгоритмы от худшего к лучшему. Так что не волнуйтесь. Следуйте статье и применяйте их.
Давайте углубимся в алгоритмы сортировки.
Содержание
Сортировка вставками
Сортировка вставками — один из самых простых алгоритмов сортировки. Это легко реализовать. И это будет стоить вам больше времени на сортировку массива. Он не будет использоваться в большинстве случаев сортировки для больших массивов.
Алгоритм сортировки вставками поддерживает отсортированные и несортированные части в заданном массиве.
Отсортированная часть содержит только первый элемент в начале процесса сортировки. Мы возьмем элемент из несортированного массива и поместим его в правильное положение в отсортированном подмассиве.
Давайте рассмотрим наглядные иллюстрации сортировки вставками шаг за шагом на примере.
Давайте посмотрим, как реализовать сортировку вставками.
- Инициализируйте массив фиктивными данными (целыми числами).
- Перебрать заданный массив из другого элемента.
- Возьмите текущую позицию и элемент в двух переменных.
- Напишите цикл, который повторяется до тех пор, пока не встретится первый элемент массива или элемент, меньший, чем текущий элемент.
- Обновите текущий элемент предыдущим элементом.
- Уменьшить текущую позицию.
- Здесь цикл должен либо достичь начала массива, либо найти элемент, меньший, чем текущий элемент. Заменить элемент текущей позиции текущим элементом.
Временная сложность сортировки вставками составляет O (n ^ 2), а пространственная сложность — O (1).
Вот и все; мы отсортировали данный массив. Давайте запустим следующий код. Надеюсь, у вас установлен Python, если нет, смотрите руководство по установке. Кроме того, вы можете использовать онлайн-компилятор Python.
def insertion_sort(arr, n): for i in range(1, n): ## current position and element current_position = i current_element = arr[i] ## iteratin until ### it reaches the first element or ### the current element is smaller than the previous element while current_position > 0 and current_elementСелецтион Сорт
Сортирање избора је слично сортирању уметањем са малом разликом. Овај алгоритам такође дели низ на сортиране и несортиране под-делове. А онда ћемо, на свакој итерацији, узети минимални елемент из несортираног поддела и поставити га на последњу позицију сортираног поддела.
Хајде да сортирамо илустрације селекције ради бољег разумевања.
Хајде да видимо кораке за имплементацију сортирања селекције.
- Инициализируйте массив фиктивными данными (целыми числами).
- Перебрать заданный массив.
- Сохраняйте минимальный индекс элемента.
- Напишите цикл, который повторяется от текущего элемента к последнему элементу.
- Проверьте, меньше ли текущий элемент минимального элемента или нет.
- Если текущий элемент меньше минимального элемента, замените индекс.
- У нас есть минимальный индекс элемента с нами. Замените текущий элемент минимальным элементом, используя индексы.
Временная сложность сортировки выбором составляет O (n ^ 2), а пространственная сложность — O (1).
Попробуйте реализовать алгоритм, так как он похож на сортировку вставками. Вы можете увидеть код ниже.
def selection_sort(arr, n): for i in range(n): ## to store the index of the minimum element min_element_index = i for j in range(i + 1, n): ## checking and replacing the minimum element index if arr[j]Буббле Сорт
Буббле сортирање је једноставан алгоритам. Он мења суседне елементе на свакој итерацији узастопно док се дати низ не сортира.
Итерира низ низ и помера тренутни елемент на следећу позицију све док не буде мањи од следећег елемента.
Илустрације нам помажу да визуелно разумемо сортирање мехурића. Хајде да их видимо.
Хајде да видимо кораке за имплементацију сортирања мехурића.
Временная сложность пузырьковой сортировки составляет O (n ^ 2), а пространственная сложность — O (1).
Теперь вы можете легко реализовать пузырьковую сортировку. Давайте посмотрим код.
def bubble_sort(arr, n): for i in range(n): ## iterating from 0 to n-i-1 as last i elements are already sorted for j in range(n - i - 1): ## checking the next element if arr[j] > arr[j + 1]: ## swapping the adjucent elements arr[j], arr[j + 1] = arr[j + 1], arr[j] if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] bubble_sort(arr, 9) ## printing the array print(str(arr))
Сортировка слиянием
Сортировка слиянием — это рекурсивный алгоритм сортировки заданного массива. Он более эффективен, чем рассмотренные ранее алгоритмы с точки зрения временной сложности. Он следует принципу «разделяй и властвуй».
Алгоритм сортировки слиянием разбивает массив на две половины и сортирует их по отдельности. После сортировки двух половин массива он объединяет их в один отсортированный массив.
Поскольку это рекурсивный алгоритм, он делит массив до тех пор, пока массив не станет самым простым (массив с одним элементом) для сортировки.
Настало время иллюстрации. Давайте посмотрим.
Давайте посмотрим, как реализовать сортировку слиянием.
- Инициализируйте массив фиктивными данными (целыми числами).
- Напишите функцию с именем merge для объединения подстрок в один отсортированный массив. Он принимает массив аргументов, левый, средний и правый индексы.
- Получите длины длины левой и правой подстрок, используя заданные индексы.
- Скопируйте элементы из массива в соответствующие левый и правый массивы.
- Перебрать два подмассива.
- Сравните два элемента подстроки.
- Замените элемент массива меньшим из двух подмассивов для сортировки.
- Убедитесь, что остальные элементы есть в обеих подстроках.
- Добавьте их в массив.
- Напишите функцию с именем merge_sort с массивом параметров, левым и правым индексами.
- Если левый индекс больше или равен правому индексу, возврат.
- Найдите середину последовательности, чтобы разделить последовательность на две половины.
- Рекурсивно вызовите merge_sort, используя левый, правый и средний индексы.
- После рекурсивных вызовов объедините массив с помощью функции объединения.
Временная сложность сортировки слиянием составляет O (nlogn), а пространственная сложность — O (1).
Вот и все для реализации алгоритма сортировки слиянием. Проверьте код ниже.
def merge(arr, left_index, mid_index, right_index): ## left and right arrays left_array = arr[left_index:mid_index+1] right_array = arr[mid_index+1:right_index+1] ## getting the left and right array lengths left_array_length = mid_index - left_index + 1 right_array_length = right_index - mid_index ## indexes for merging two arrays i = j = 0 ## index for array elements replacement k = left_index ## iterating over the two sub-arrays while i = right_index: return ## finding the middle index mid_index = (left_index + right_index) // 2 ## recursive calls merge_sort(arr, left_index, mid_index) merge_sort(arr, mid_index + 1, right_index) ## merging the two sub-arrays merge(arr, left_index, mid_index, right_index) if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] merge_sort(arr, 0, 8) ## printing the array print(str(arr))
Заключение
Существует множество других алгоритмов сортировки, но выше приведены некоторые из наиболее часто используемых. Надеюсь, вам понравилось учиться сортировать.
Тогда изучите алгоритмы поиска.
Удачного кодирования ? ??
![Как проверить версию Python в Windows, Linux и macOS [2023]](https://alltechreviews.ru/wp-content/uploads/2023/03/Как-проверить-версию-Python-в-Windows-Linux-и-macOS-2023-150x150.png)