Алгоритмы сортировки в Python

Сортировка определяется как упорядочение данных в определенном порядке. Методы сортировки используются для упорядочения данных (в основном числовых) в порядке возрастания или убывания. Это метод, используемый для представления данных в более понятном формате. Это важная область компьютерных наук. Сортировка большого объема данных может потребовать значительных вычислительных ресурсов, если методы, которые мы используем для сортировки данных, неэффективны. Эффективность алгоритма пропорциональна количеству элементов, которые он обрабатывает. Для небольшого объема данных сложный метод сортировки может принести больше хлопот, чем пользы. С другой стороны, при обработке больших объемов данных мы хотим максимально повысить эффективность и скорость. Теперь мы обсудим несколько методов сортировки и сравним их с точки зрения их временной сложности

# Неотсортированный список
[2, 1, 4, 3]

# Массив, отсортированный в порядке возрастания
[1, 2, 3, 4]

# Массив, отсортированный в порядке убывания
[4, 3, 2, 1]

Вот некоторые из реальных примеров сортировки:

1. Телефонный справочник: Это книга, содержащая номера телефонов и адреса людей в алфавитном порядке.
2. Словарь: Это огромная коллекция слов с указанием их значений в алфавитном порядке.
3. Список контактов: Это список контактных номеров людей в алфавитном порядке на мобильном телефоне.

Прежде чем обсуждать различные алгоритмы, используемые для сортировки предоставленных нам данных, мы должны подумать об операциях, которые могут быть использованы для анализа процесса сортировки. Во-первых, нам нужно сравнить значения, чтобы увидеть, какое из них меньше, а какое больше, чтобы их можно было отсортировать по порядку, необходимо будет иметь организованный способ сравнения значений, чтобы увидеть, находятся ли они в заданном порядке.

Существуют различные типы порядков:

1. Возрастающий порядок: набор значений называется возрастающим, если каждый последующий элемент больше предыдущего. Например,: 1, 2, 3, 4, 5. Здесь данная последовательность приведена в порядке возрастания.
2. Порядок убывания: набор значений называется расположенным в порядке убывания, когда последующий элемент всегда меньше предыдущего. Например: 5, 4, 3, 2, 1. Здесь данная последовательность приведена в порядке убывания.
3. Нерастущий порядок: набор значений называется расположенным в нерастущем порядке, если каждый n-й элемент, присутствующий в последовательности, больше или равен своему (n-1)-му элементу. Этот порядок используется всякий раз, когда есть повторяющиеся числа. Например: 1, 2, 2, 3, 4, 5. Здесь 2 повторяется два раза.
4. Порядок неубывания: набор значений называется расположенным в порядке неубывания, если каждый n-й элемент, присутствующий в последовательности, меньше или равен своему (n-1)-му элементу. Этот порядок используется всякий раз, когда есть повторяющиеся числа. Например: 5, 4, 3, 2, 2, 1. Здесь 2 повторяется два раза.

Методы сортировки

Различными реализациями методов сортировки в Python являются:

1. Сортировка пузырьком
2. Сортировка выбором
3. Сортировка вставками

Сортировка пузырьком

Пузырьковая сортировка - это простой алгоритм сортировки. Этот алгоритм сортировки многократно сравнивает два соседних элемента и меняет их местами, если они расположены в неправильном порядке. Он также известен как потоковая сортировка. Он имеет временную сложность O(n²) в среднем и наихудшем сценариях и O(n) в наилучшем сценарии. Пузырьковую сортировку можно представить в виде очереди, в которой люди выстраиваются, меняясь местами друг с другом, так что все они могут располагаться в порядке возрастания их высоты. Или, другими словами, мы сравниваем два соседних элемента и смотрим, не перепутан ли их порядок, если порядок неправильный, мы меняем их местами. (т.е. arr[i] > arr[j] for 1 <= i < j <= s; где s - размер массива, если массив должен быть в порядке возрастания, и наоборот).

Пример. Здесь мы сортируем следующую последовательность, используя пузырьковую сортировку

Последовательность: 2, 23, 10, 1

Первая итерация

(2, 23, 10, 1) –> (2, 23, 10, 1), Здесь сравниваются первые 2 элемента, которые остаются неизменными, поскольку они уже расположены в порядке возрастания.

(2, 23, 10, 1) –> (2, 10, 23, 1), Здесь 2-й и 3-й элементы сравниваются и меняются местами (10 меньше, чем 23) в порядке возрастания.

(2, 10, 23, 1) –> (2, 10, 1, 23), Здесь 3-й и 4-й элементы сравниваются и меняются местами (1 меньше 23) в порядке возрастания

В конце первой итерации самый большой элемент находится в крайней правой позиции, которая отсортирована правильно.

Вторая итерация

(2, 10, 1, 23) –> (2, 10, 1, 23), Здесь снова сравниваются первые 2 элемента, которые остаются неизменными, поскольку они уже расположены в порядке возрастания.

(2, 10, 1, 23) –> (2, 1, 10, 23), Здесь 2-й и 3-й элементы сравниваются и меняются местами (1 меньше 10) в порядке возрастания.

В конце второй итерации второй по величине элемент находится в позиции, смежной с самым большим элементом.

Третья итерация

(2, 1, 10, 23) –> (1, 2, 10, 23), Здесь сравниваются первые 2 элемента и меняются местами в порядке возрастания.

Остальные элементы уже отсортированы на первой и второй итерациях. После трех итераций данный массив сортируется в порядке возрастания. Таким образом, конечный результат равен 1, 2, 10, 23.

Реализация пузырьковой сортировки:

def bubble_sort(array):
     
    n = len(array)
 
    # Цикл for по всем элементам массива
    for i in range(n):
        for j in range(0, n - i - 1):
             
            # Диапазон значений массива составляет от 0 до n-i-1
            # Меняем местами элементы, если найденный 
            # элемент больше соседнего
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]

# Создадим массив для проверки
array = [2, 1, 10, 23]

# Используем функцию сортировки
bubble_sort(array)
 
print("Отсортированный массив:")
for i in range(len(array)):
    print(f'{array[i]}')

Вывод:

Отсортированный массив:
1
2
10
23

Временная сложность: O(n²)

Вспомогательное пространство: O(1)

Сортировка выбором

Этот метод сортировки позволяет повторно находить минимальный элемент и сортировать его по порядку. Пузырьковая сортировка не занимает дополнительного пространства в памяти. Во время выполнения этого алгоритма сохраняются два подмассива: подмассив, который уже отсортирован, и оставшийся подмассив, который не отсортирован. Во время выполнения выборочной сортировки для каждой итерации минимальный элемент несортированного подмассива помещается в отсортированный подмассив. Выборочная сортировка является более эффективным алгоритмом, чем пузырьковая сортировка. Временная сложность сортировки составляет O(n²) в среднем, худшем и лучшем случаях.

Пример использования алгоритма выборочной сортировки:

Последовательность: 7, 2, 1, 6

(7, 2, 1, 6) –> (1, 7, 2, 6), При первом обходе он находит минимальный элемент (т.е. 1) и помещает его на 1-ю позицию.

(1, 7, 2, 6) –> (1, 2, 7, 6), При втором обходе он находит 2-й минимальный элемент (т.е. 2) и помещает его на 2-ю позицию.

(1, 2, 7, 6) –> (1, 2, 6, 7), При третьем обходе он находит следующий минимальный элемент (т.е. 6) и помещает его на 3-ю позицию.

После описанных выше итераций конечный массив будет отсортирован в порядке убывания, т.е. 1, 2, 6, 7.

Реализация сортировки выбором

def selection_sort(array, size):
     
    for s in range(size):
        min_idx = s
         
        for i in range(s + 1, size):
             
            # Для сортировки в порядке убывания
            # минимального элемента в каждом цикле
            if array[i] < array[min_idx]:
                min_idx = i
 
        # Установим минимальный в правильную позицию
        (array[s], array[min_idx]) = (array[min_idx], array[s])

data = [ 7, 2, 1, 6 ]
size = len(data)
selection_sort(data, size)
 
print('Отсортированный массив в порядке возрастания:')
print(data)

Вывод:

Отсортированный массив в порядке возрастания:
[1, 2, 6, 7]

Временная сложность: O(n²)

Вспомогательное пространство: O(1)

Сортировка вставками

Этот алгоритм сортировки поддерживает постоянную сортировку подмассива. Значения из несортированной части массива размещаются в правильной позиции в отсортированной части. На практике он более эффективен, чем другие алгоритмы, такие как сортировка по выбору или пузырьковая сортировка. Временная сложность сортировки при вставке составляет O(n²) в среднем и наихудшем случае и O(n) в лучшем случае.

Пример работы алгоритма сортировки вставками

Последовательность: 7, 2, 1, 6

(7, 2, 1, 6) –> (2, 7, 1, 6), На первой итерации сравниваются первые 2 элемента, здесь 2 меньше 7, поэтому вставьте 2 перед 7.

(2, 7, 1, 6) –> (2, 1, 7, 6), На второй итерации сравниваются 2-й и 3-й элементы, здесь 1 меньше 7, поэтому вставьте 1 перед 7.

(2, 1, 7, 6) –> (1, 2, 7, 6), После второй итерации (1, 7) элементы расположены не в порядке возрастания, поэтому сначала располагаются эти два элемента. Итак, вставьте 1 перед 2.

(1, 2, 7, 6) –> (1, 2, 6, 7), Во время этой итерации последние 2 элемента сравниваются и меняются местами после того, как все предыдущие элементы будут заменены.

Реализация сортировки вставками

def insertion_sort(list1):  
   
        # Внешний цикл по len(list1)  
        for i in range(1, len(list1)):  
   
            a = list1[i]  
   
            # Переместим элементы списка list1[0 to i-1], 
            # которые больше, на одну позицию
            # выше их текущей позиции  
            j = i - 1 
           
            while j >= 0 and a < list1[j]:  
                list1[j + 1] = list1[j]  
                j -= 1 
                 
            list1[j + 1] = a  
             
        return list1  

list1 = [ 7, 2, 1, 6 ]
print("Отсортированный список:", insertion_sort(list1))

Вывод:

Отсортированный список:
[1, 2, 6, 7]

Временная сложность: O(n²)

Вспомогательное пространство: O(1)

Статья была переведена по материалам GeeksForGeeks.