Обменная сортировка простой выборкой

Алгоритм сортировки простой выборкой, однако, редко применяется в том варианте, в каком он описан выше. Гораздо чаще применяется его, так называемый, обменный вариант. При обменной сортировке выборкой входное и выходное множество располагаются в одной и той же области памяти; выходное - в начале области, входное - в оставшейся ее части. В исходном состоянии входное множество занимает всю область, а выходное множество - пустое. По мере выполнения сортировки входное множество сужается, а выходное - расширяется.

Обменная сортировка простой выборкой показана в программном примере 4. Процедура имеет только один параметр - сортируемый массив.

{===== Программный пример 4 =====}

Procedure Sort(var a: SEQ);

Var x, i, j, m: integer;

begin

for i:=1 to N-1 do { перебор элементов выходного множества}

{ входное множество - [i:N]; выходное - [1:i-1] }

begin m:=i;

for j:=i+1 to N do { поиск минимума во входном множестве }

if (a[j]<a[m]) then m:=j;

{ обмен 1-го элемента вх. множества с минимальным }

if i<>m then begin

x:=a[i]; a[i]:=a[m]; a[m]:=x;

end;end; end;

Результаты трассировки программного примера 4 представлены в таблице 2. Двоеточием показана граница между входным и выходным множествами.

Очевидно, что обменный вариант обеспечивает экономию памяти. Очевидно также, что здесь не возникает проблемы "пустого" значения. Общее число сравнений уменьшается вдвое - N*(N-1)/2, но порядок алгоритма остается степенным - O(N²). Количество перестановок N-1, но перестановка, по-видимому, вдвое более времяемкая операция, чем пересылка в предыдущем алгоритме.

Таблица 2

Шаг

Содержимое массива а

исходный результат

: 242 447 286 708 24 11 192 860 937 561 11:447 286 708 24 242 192 860 937 561 11 24:286 708 447 242 192 860 937 561 11 24 192:708 447 242 286 860 937 561 11 24 192 242:447 708 286 860 937 561 11 24 192 242 286:708 447 860 937 561 11 24 192 242 286 447:708 860 937 561 11 24 192 242 286 447 561:860 937 708 11 24 192 242 286 447 561 708:937 860 11 24 192 242 286 447 561 708 860:937 11 24 192 242 286 447 561 708 860 937

Довольно простая модификация обменной сортировки выборкой предусматривает поиск в одном цикле просмотра входного множества сразу и минимума, и максимума и обмен их с первым и с последним элементами множества соответственно. Хотя итоговое количество сравнений и пересылок в этой модификации не уменьшается, достигается экономия на количестве итераций внешнего цикла.

Приведенные выше алгоритмы сортировки выборкой практически нечувствительны к исходной упорядоченности. В любом случае поиск минимума требует полного просмотра входного множества. В обменном варианте исходная упорядоченность может дать некоторую экономию на перестановках для случаев, когда минимальный элемент найден на первом месте во входном множестве.

Министерство образования и науки Республики Казахстан

Евразийский национальный университет им. Л.Н. Гумилева

Кафедра Информационных систем

(наименование кафедры)

План практических занятий

1FNS 12017 Алгоритмы, структуры данных и языки программирование

(шифр и наименование модуля)

по дисциплине ASDYaP1202 Алгоритмы, структуры данных и языки программирование

(код и полное наименование дисциплины по рабочему учебному плану)

для студентов специальности 5В070300 Информационные системы

(шифр и наименование специальности/специализации)

Астана

Дата добавления: 2015-07-15