Кодинг
★ Рубрика: Кодинг
★ Тема: Алгоритмы

Алгоритм сортировки массива

Задача. Пусть a[1], ..., a[n] - целые числа. Требуется построить массив b[1], ..., b[n], содержащий те же числа, для которых b[1] < = ... < = b[n].
Замечание. Среди чисел a[1]...a[n] могут быть равные. Требуется, чтобы каждое целое число входило в b[1]...b[n] столько же раз, сколько и в a[1]...a[n].
Решение. Удобно считать, что числа a[1]..a[n] и b[1]..b[n] представляют собой начальное и конечное значения массива x. Требование "a и b содержат одни и те же числа" будет заведомо выполнено, если в процессе работы мы ограничимся перестановками элементов x.
 ...
 k := 0;
 {k наименьших элементов массива x установлены на свои места}
 while k < > n do begin
 | s := k + 1; t := k + 1;
 | {x[s] - наименьший среди x[k+1]...x[t] }
 | while t < > n do begin
 | | t := t + 1;
 | | if x[t] < x[s] then begin
 | | | s := t;
 | | end;
 | end;
 | {x[s] - наименьший среди x[k+1]..x[n] }
 | ... переставить x[s] и x[k+1];
 | k := k + 1;
 end;
 Похожие публикации: Алгоритмы

Войдите, чтобы добавить Ваш ответ. [ Регистрация | Вход ]