Квадратичные сортировки в Python

Это сортировки, количество операций в которых не превышает квадрат количества сортируемых элементов. То есть, если мне понадобилось отсортировать список из n элементов с помощью этих сортировок, то на это понадобится (n*(n-1))/2 операций, но не более n².

1. Первый из трёх типов квадратичных сортировок — сортировка вставкой или insert sort.

Её особенность в том, что первый элемент массива принимается за уже отсортированный в самом себе массив. Следующий элемент сравнивается с крайним (в случае с первым элементом, единственным) отсортированного массива, и в случае, если крайний больше следующего, они меняются местами.

Сортировка вставкой на Python может выглядеть следующим образом:

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

3. Сортировка методом пузырька, пузырьковая сортировка, или bubble sort, называется так потому, что наибольший элемент (при сортировке от меньшего к большему) как бы выталкивается на правый край массива, подобно тому, как пузырёк газа выталкивается из жидкости.

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

#python