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

Дата добавления: 2015-07-09; просмотров: 474; Нарушение авторских прав

Идея сортировки с помощью выбора не сложнее двух предыдущих. На j-ом этапе выбирается элемент наименьший среди M[j], M[j+1],. . ., M[N](см. процедуру FindMin) и меняется местами с элементом M[j]. В результате после j-го этапа все элементы M[j],M[j+1],. . ., M[N]будут упорядочены.

Сказанное можно описать следующим образом:

нц для j от 1 до N-1
выбрать среди M[j],. . ., M[N] наименьший элемент и
поменять его местами с M[j]
кц

Более точно:

begin for j:=1 to N-1 do begin FindMin(j, i); swap(M[j],M[i]) end end;

В программе, как уже было сказано, используется процедура FindMin, вычисляющая индекс lowindexэлемента, наименьшего среди элементов массива с индексами не меньше, чем startindex:

procedure FindMin(startindex: integer; var lowindex: integer); var lowelem: ...; u: integer; begin lowindex := startindex; lowelem := M[startindex]; for u:=startindex+1 to N do if M[u] < lowelem then begin lowelem := M[u]; lowindex := u end end;

Индексный массив (в некоторых языках программирования также таблица, ряд) — именованный набор однотипных переменных, расположенных в памяти непосредственно друг за другом, доступ к которым осуществляется по индексу (в отличие от списка).

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

В ряде скриптовых языков, например JavaScript, PHP, Ruby применяются также ассоциативные массивы, в которых переменные не обязаны быть однотипными, и доступ к ним не обязательно осуществляется по индексу.

<== предыдущая лекция	\|	следующая лекция ==>
Сортировка вставками	\|	Общее описание