Лабораторная работа 3 Операции над массивами и создание структурированных массивов

Простая сортировка вставкой (insertion sort) многократно находит минимальное значение из списка и выполняет перестановки до тех пор, пока список не будет отсортирован. Это можно запрограммировать с помощью всего нескольких строк кода на языке Python:

import numpy as np

def selection_sort(x):

for i in range(len(x)):

swap = i + np.argmin(x[i:])

(x[i], x[swap]) = (x[swap], x[i])

return x
x = np.array([2, 1, 4, 3, 5])

selection_sort(x)

Out: array([1, 2, 3, 4, 5])

Сортировка вставкой удобна из-за своей простоты, но слишком медлительна, чтобы подходить для массивов большего размера. Для списка из N значений она потребует N циклов, каждый из них выполняет порядка ~N сравнений для поиска значения, которое нужно переставить. На языке нотации «О-большого», часто используемой для описания характеристик этих алгоритмов, временная сложность сортировки вставкой в среднем имеет порядок O[N²]: при удвоении количества элементов списка время выполнения вырастет примерно в четыре раза.

Даже сортировка выбором гораздо лучше среди всех алгоритмов сортировки – случайной сортировки (bogosort):

def bogosort(x):

while np.any(x[:-1] > x[1:]):

np.random.shuffle(x)

return x
x = np.array([2, 1, 4, 3, 5])

bogosort(x)

Out: array([1, 2, 3, 4, 5])

Этот алгоритм сортировки опирается в своей работе на чистое везение: он многократно перетасовывает массив случайным образом до тех пор, пока результат не окажется отсортированным. При средней сложности порядка O[N × N!]: (это N умножить на N факториал) его не стоит использовать ни для каких реальных расчетов.