Сортировка вставками (Insertion Sort) простой алгоритм, часто используется при изучение компьютерных наук и обычно, является одним из первых алгоритмов сортировки, с которым знакомя учеников. Он интуитивно понятен и прост в реализации, но он очень медленный для больших массивов и поэтому почти никогда не используется для сортировки реальных данных.
Спонсор поста Сайт легального бесплатного софта biblsoft.ru.
Бесплатные программы для компьютеров Windows и macOS, а также мобильных устройств Android и iOS.
Например: KingRoot Утилита предоставляющая Root-права на Android
Insertion Sort является stable и in-place алгоритмом, который действительно хорошо работает только для почти отсортированных или небольших массивов.
Что значит stable и in-place:
Так же при сортировке вставками вам не обязательно нужно иметь весь массив заранее перед сортировкой. Алгоритм может получать по одному элементу в процессе сортировки. Это очень удобно, если нам нужно добавлять больше элементов во время сортировки — алгоритм будет вставлять новый элемент элемент в нужное место без «повторного выполнения» сортировки всего массива.
Сортировка вставками может используется на практике из-за ее эффективности для небольших (~ 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(n2). Однако, как мы уже упоминали, он очень эффективный для небольших массивов и почти отсортированных массивов.
Это делает сортировку вставками очень актуальной для использования в сочетании с алгоритмами, которые хорошо работают с большими наборами данных.
Например, в Java используется быстрая сортировка Dual Pivot в качестве основного алгоритма сортировки, но так же используется сортировка вставками всякий раз, когда массив (или коллекция, созданная быстрой сортировкой) содержит менее 7 элементов.
Еще одно место, где Insertion Sort оставил свой след, — это очень популярный алгоритм Shell Sort. Shell Sort работает, вызывая Insertion Sort для сортировки пар элементов далеко друг от друга, затем постепенно уменьшая разрыв между элементами для сравнения.
Сортировка вставками — это очень простой, и неэффективный алгоритм, который, тем не менее, имеет несколько конкретных преимуществ, которые делают его актуальным даже после того, как были разработаны многие другие, как правило, более эффективные алгоритмы.
Он остается отличным алгоритмом для обучения будущих разработчиков программного обеспечения миру алгоритмов сортировки и до сих пор используется на практике для конкретных сценариев, в которых он используется.
Краткий перевод: https://vuejs.org/guide/components/v-model.html Основное использование v-model используется для реализации двусторонней привязки в компоненте. Начиная с Vue…
Сегодня мы рады объявить о выпуске Vue 3.4 «🏀 Slam Dunk»! Этот выпуск включает в…
Vue.js — это универсальный и адаптируемый фреймворк. Благодаря своей отличительной архитектуре и системе реактивности Vue…
Недавно, у меня истек сертификат и пришлось заказывать новый и затем устанавливать на хостинг с…
Каким бы ни было ваше мнение о JavaScript, но всем известно, что работа с датами…
Все, кто следит за последними событиями в мире адаптивного дизайна, согласятся, что введение контейнерных запросов…
View Comments
там ошибок много в статье, оценка 0
Ребята пишите сами статьи, а не нанимайте копирайтеров, которые переписывая источник, не понимают его смысла. Это не для блондинок рецепт, это урок для специалистов. Ресурсу ноль за глупость администраторов.
Аргументируй
Приведен один массив, описание про другой
как он может изначально разбиваться на "отсортированный" и на "неотсортированный" массивы, если изначально весь массив не отсортирован ????
вы че пургу несете , копипастеры