Редактирование: Сортировка вставками

Перейти к: навигация, поиск

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
'''Сортировка вставками''' (англ. ''Insertion sort'') — квадратичный алгоритм [[Сортировка|сортировки]].
+
'''Сортировка вставками''' (англ. ''Insertion sort'') — квадратичный алгоритм сортировки.
  
 
==Алгоритм==
 
==Алгоритм==
Строка 75: Строка 75:
 
== Оптимизации ==
 
== Оптимизации ==
 
=== Бинарные вставки ===
 
=== Бинарные вставки ===
Теперь вместо линейного поиска позиции мы будем использовать [[Целочисленный двоичный поиск | бинарный поиск]], следовательно количество сравнений изменится с <tex>O(N^2)</tex> до <tex> O(N\log N) </tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить элемент на своё место, всё ещё необходимо переместить большое количество элементов. В итоге время выполнения алгоритма в асимптотически не уменьшилось. Бинарные вставки выгодно использовать только в случае когда сравнение занимает много времени по сравнению со сдвигом. Например когда мы используем массив длинных чисел.  
+
Теперь вместо линейного поиска позиции мы будем использовать [[Целочисленный двоичный поиск | бинарный поиск]], следовательно количество сравнений изменится с <tex>O(N^2)</tex> до <tex> O(N\log N) </tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить элемент на на своё место, всё ещё необходимо переместить большое количество элементов. В итоге время выполнения алгоритма в асимптотически не уменьшилось. Бинарные вставки выгодно использовать только в случае когда сравнение занимает много времени по сравнению со сдвигом. Например когда мы используем массив длинных чисел.  
 
  '''function''' insertionSort(a):
 
  '''function''' insertionSort(a):
 
   '''for''' i = 1 '''to''' n - 1
 
   '''for''' i = 1 '''to''' n - 1
Строка 91: Строка 91:
 
!style="background-color:#EEE"| Описание шага
 
!style="background-color:#EEE"| Описание шага
 
|-
 
|-
|colspan=3|''Первый проход (проталкиваем первый элемент — '''''5''''')''
+
|colspan=3|''Первый проход (проталкиваем второй элемент — '''''5''''')''
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 10px"|  
 
|style="background-color:#FFF;padding:2px 10px"|  
 
|style="background-color:#FFF;padding:2px 30px"| '''5'''
 
|style="background-color:#FFF;padding:2px 30px"| '''5'''
|style="background-color:#FFF;padding:2px 10px"| Так как в поле вывода нет элементов, то мы просто добавляем элемент туда.
+
|style="background-color:#FFF;padding:2px 10px"| Так как в поле вывода нет элементов то мы просто добавляем элемент туда.
 
|-
 
|-
|colspan=3|''Второй проход (проталкиваем второй элемент — '''''7''''')''
+
|colspan=3|''Второй проход (проталкиваем третий элемент — '''''7''''')''
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 30px"| 5  
 
|style="background-color:#FFF;padding:2px 30px"| 5  
 
|style="background-color:#FFF;padding:2px 30px"| 5 '''7'''
 
|style="background-color:#FFF;padding:2px 30px"| 5 '''7'''
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и, так как позиция крайняя, то сдвигать ничего не приходится.
+
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и так как позиция крайняя то сдвигать ничего не приходится.
 
|-   
 
|-   
|colspan=3|''Третий проход (проталкиваем третий — '''''3''''')''
+
|colspan=3|''Третий проход (проталкиваем четвертый — '''''3''''')''
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 30px"| 5 7
 
|style="background-color:#FFF;padding:2px 30px"| 5 7
 
|style="background-color:#FFF;padding:2px 20px"| '''3''' 5 7
 
|style="background-color:#FFF;padding:2px 20px"| '''3''' 5 7
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и, так как позиция крайняя, то сдвигать ничего не приходится.
+
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и так как позиция крайняя то сдвигать ничего не приходится.
 
|-
 
|-
|colspan=3|''Четвертый проход (проталкиваем четвертый элемент — '''''4''''')''
+
|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''4''''')''
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 20px"| 3 5 7
 
|style="background-color:#FFF;padding:2px 20px"| 3 5 7
 
|style="background-color:#FFF;padding:2px 10px"| 3 '''4''' 5 7
 
|style="background-color:#FFF;padding:2px 10px"| 3 '''4''' 5 7
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию. Расстояние до левого края зоны вывода меньше, чем до правого, значит сдвигаем левую часть.
+
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию. Расстояние до левого края зоны вывода меньше ем до правого то сдвигаем левую часть.
 
|-
 
|-
 
|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''6''''')''
 
|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''6''''')''

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: