Сортировка вставками (Insertion Sort) в Python

Введение

Сортировка вставками (Insertion Sort) простой алгоритм, часто используется при изучение компьютерных наук и обычно, является одним из первых алгоритмов сортировки, с которым знакомя учеников. Он интуитивно понятен и прост в реализации, но он очень медленный для больших массивов и поэтому почти никогда не используется для сортировки реальных данных.

Спонсор поста Сайт легального бесплатного софта biblsoft.ru.
Бесплатные программы для компьютеров Windows и macOS, а также мобильных устройств Android и iOS.
Например: KingRoot Утилита предоставляющая Root-права на Android

Insertion Sort является stable и in-place алгоритмом, который действительно хорошо работает только для почти отсортированных или небольших массивов.

Что значит stable и in-place:

• in-place: Требует небольшого постоянного дополнительного пространства памяти (независимо от входного размера коллекции),он перезаписывает исходные ячейки памяти элементов в коллекции.
• stable: Алгоритм поддерживает относительный порядок равных объектов из исходного массива. Другими словами, скажем, база данных сотрудников вашей компании возвращает двух сотрудников «Дейв Уотсон» и «Дейв Браун» в указанном порядке. Если бы вы отсортировали их по (общему) имени, stable алгоритм гарантирует, что этот порядок останется неизменным.

Так же при сортировке вставками вам не обязательно нужно иметь весь массив заранее перед сортировкой. Алгоритм может получать по одному элементу в процессе сортировки. Это очень удобно, если нам нужно добавлять больше элементов во время сортировки — алгоритм будет вставлять новый элемент элемент в нужное место без «повторного выполнения» сортировки всего массива.

Сортировка вставками может используется на практике из-за ее эффективности для небольших (~ 10 элементов) наборов данных. Но мы поговорим об этом позже.

Как работает сортировка вставками

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

Первый элемент в несортированном массиве оценивается так, что мы можем вставить его на свое место в отсортированном подмассиве.

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

Это продолжается, пока весь наш массив не будет отсортирован.

Имейте в виду, однако, что когда мы говорим, что элемент больше или меньше, чем другой элемент — это не обязательно означает большие или меньшие целые числа.

Мы можем определить слова «больше» и «меньше», как нам нравится при использовании пользовательских объектов. Например, точка A может быть «больше», чем точка B, если она находится дальше от центра системы координат.

Мы помечаем отсортированный подмассив жирными числами и используем следующий массив для иллюстрации алгоритма:

8, 5, 3, 11, 9

Первым шагом было бы «добавить» 8 в наш отсортированный подмассив.

8, 5, 3, 11, 9

Теперь рассмотрим первый несортированный элемент — 5. Мы сохраняем это значение в отдельной переменной, например, current, для сохранности. 5 меньше 8. Мы перемещаем 8 на одно место вправо, фактически перезаписывая 5, которые было там ранее сохранено (отсюда и отдельная переменная для безопасного хранения):

8, 8, 3, 11, 9 (current = 5)

5 меньше всех элементов в нашем отсортированном подмассиве, поэтому мы вставляем его на первую позицию:

5, 8, 3, 11, 9

Далее мы смотрим на номер 4. Мы сохраняем это значение в current. 4 меньше 8, поэтому мы перемещаем 8 вправо и делаем то же самое с 5.

5, 5, 8, 11, 9 (current = 3)

Мы снова столкнулись с элементом, меньшим, чем весь наш отсортированный подмассив, поэтому мы поместили его на первую позицию:

3, 5, 8, 11, 9

10 больше, чем наш самый правый элемент в отсортированном подмассиве, и поэтому больше, чем любой из элементов слева от 8. Поэтому мы просто переходим к следующему элементу:

3, 5, 8, 11, 9

9 меньше 10, поэтому мы переместимся на 10 вправо:

3, 5, 8, 11, 10 (current = 9)

Однако 9 больше 8, поэтому мы просто вставляем 9 сразу после 8.

3, 5, 8, 9, 11

Реализация

Как мы уже упоминали, Insertion Sort довольно легко реализовать. Мы реализуем это сначала на простом массиве целых чисел, а затем на некоторых пользовательских объектах.

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

Пример реализации в псевдокоде

INSERTION-SORT(A)
   for i = 1 to n
   	key ← A [i]
    	j ← i – 1
  	 while j > = 0 and A[j] > key
   		A[j+1] ← A[j]
   		j ← j – 1
   	End while 
   	A[j+1] ← key
  End for 

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

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >=0 and key < arr[j] :
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key 


arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print ("Sorted array is:")
for i in range(len(arr)):
    print arr[i]

Давайте заполним простой массив и отсортируем его:

array = [4, 22, 41, 40, 27, 31, 36, 1, 42, 39, 14, 9, 3, 6, 34, 9, 21, 4, 29, 49]
insertion_sort(array)
print("sorted: " + str(array))

Вывод:

sorted: [1, 3, 4, 4, 6, 9, 9, 14, 21, 22, 27, 29, 31, 34, 36, 39, 40, 41, 42, 49]

Анализ сложности

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

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

Например, в Java используется быстрая сортировка Dual Pivot в качестве основного алгоритма сортировки, но так же используется сортировка вставками всякий раз, когда массив (или коллекция, созданная быстрой сортировкой) содержит менее 7 элементов.

Еще одно место, где Insertion Sort оставил свой след, — это очень популярный алгоритм Shell Sort. Shell Sort работает, вызывая Insertion Sort для сортировки пар элементов далеко друг от друга, затем постепенно уменьшая разрыв между элементами для сравнения.

Заключение

Сортировка вставками — это очень простой, и неэффективный алгоритм, который, тем не менее, имеет несколько конкретных преимуществ, которые делают его актуальным даже после того, как были разработаны многие другие, как правило, более эффективные алгоритмы.

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