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

Сортировка вставкой — простой алгоритм сортировки.

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

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

Описание

• Глагол:

 ЗАДАЧА Упорядочить-(ряд+:РЯД ИЗ ЦЕЛ);
 (* Цель:  упорядочивание ряда целых чисел простой вставкой
  * До:    <ряд> - исходный ряд
  * После: <ряд> - упорядоченный ряд *)
 ПЕР
   число:ЦЕЛ;     (* обрабатываемое число *)
   позНеуп:ЦЕЛ;   (* до этой позиции ряд уже упорядочен *)
   позВставки:ЦЕЛ;(* позиция вставки для обрабатываемого числа *)
   поз:ЦЕЛ;
 УКАЗ
   ОТ позНеуп:=1 ДО РАЗМЕР(ряд)-1 ВЫП
     число:=ряд[позНеуп];
     (* ищем прямым перебором позицию вставки *)
     позВставки:=0;
     ПОКА число < ряд[позВставки] ВЫП
       УВЕЛИЧИТЬ(позВставки)
     КОН;
     (* раздвигаем в этом месте ряд *)
     ОТ поз:=позНеуп-1 ДО позВставки ПО -1 ВЫП
       ряд[поз+1]:=ряд[поз]
     КОН;
     (* вставляем туда число *)
     ряд[позВставки]:=число
   КОН
 КОН Упорядочить;

Сортировка двоичной вставкой

• Глагол:

 ЗАДАЧА Упорядочить-(ряд+:РЯД ИЗ ЦЕЛ);
 (* Цель:  упорядочивание ряда целых чисел двоичной вставкой
  * До:    <ряд> - исходный ряд
  * После: <ряд> - упорядоченный ряд *)
 ПЕР
   число:ЦЕЛ;     (* обрабатываемое число *)
   позНеуп:ЦЕЛ;   (* до этой позиции ряд уже упорядочен *)
   позВставки:ЦЕЛ;(* позиция вставки для обрабатываемого числа *)
   позНачала,поз:ЦЕЛ;
 УКАЗ
   ОТ позНеуп:=1 ДО РАЗМЕР(ряд)-1 ВЫП
     число:=ряд[позНеуп];
     (* двоичный поиск позиции вставки *)
     позНачала:=0; позВставки:=позНеуп;
     ПОКА позНачала < позВставки ВЫП
       поз:=(позВставки+позНачала) ДЕЛИТЬ 2;
       ЕСЛИ число >= ряд[поз] ТО
         позВставки:=поз
       ИНАЧЕ
         позНачала:=поз+1
       КОН
     КОН;
     (* раздвигаем в этом месте ряд *)
     ОТ поз:=позНеуп-1 ДО позВставки ПО -1 ВЫП
       ряд[поз+1]:=ряд[поз]
     КОН;
     (* вставляем туда число *)
     ряд[позВставки]:=число
   КОН
 КОН Упорядочить;