Сортировка методом выбора

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

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

Описание[править]

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