logo
УП_САОД_2003

Сортировка простым извлечением.

В этом методе массив также делится на уже отсортированную часть A[i+1], A[i+1], ..., A[n] и еще не отсортированную A[1], A[2], ..., A[i]. Но здесь из неотсортированной части на каждом шаге извлекается максимальный элемент, просматривая ее заново на каждом шаге. Этот элемент будет минимальным элементом отсортированной части, так как все большие его элементы были извлечены на предыдущих шагах, поэтому ставим извлеченный элемент в начало отсортированной части, точнее меняем его с A[i] местами.

Теперь запишем алгоритм.

procedure ExtractSort(n: integer;

var A: array[1..n] of integer);

{Процедура сортировки простым извлечением}

var

i, j, MaxIndex, Tmp: integer;

begin

for i := n downto 2 do begin

{Ищем максимальный элемент в неотсортированной части}

MaxIndex := 1;

for j := 2 to i do

if A[j] > A[MaxIndex] then MaxIndex := j;

{Меняем найденный элемент с первым из отсортированных}

Tmp := A[i]; A[i] := A[MaxIndex];

A[MaxIndex] := Tmp;

end;

end;

Рисунок 43. Сортировка простым извлечением

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

        1.