Массив дан случайным образом

3. Массив дан случайным образом.

Здесь два метода - "включение" и "выбор" - равнозначны. Метод "пузырька" наиболее медленный из всех. Здесь при каждом проходе чаще всего идет обмен соседних элементов. Даже в случае уже отсортированного массива, хотя сами перестановки и не совершаются, внутренний цикл сравнивает все соcедние элементы.

13.5 Улучшенный метод сортировки. QUICK – сортировка

Все рассмотренные выше методы сортировки допускают определенное улучшение. Однако наибольший эффект достигается при модификации наиболее быстрого из всех известных методов - метода прямого обмена. Эта модификация получила название QUICK - сортировка.

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

Эта идея приводит к тому, что нужно построить процедуру, которая допускает обращение самой к себе, т.е. рекурсивную процедуру, имеющую входными параметрами номера элеметов:

1-ый - левый элемент: L,

2-ой - правый элемент: R.

На начало процедуры эти параметры должны получить значения:

L = 1; R = N.

В процедуре используется цикл REPEAT по сближению левой и правой границ.

procedure QUICKSORT (L, R: integer; var M: MAS);

var I,J,W,X: integer;

begin

¦ {Установка границ, от которых идет движение к середине}

¦ I:= L; J:= R;

¦ {Выбор граничного элемента}

X:= M[(L+R) div 2];

¦ repeat

¦ ¦ { Поиск слева элемента, большего X }

¦ ¦ while X > M[I] do I:= I+1;

¦ ¦ { Поиск справа элемента, меньшего X }

¦ ¦ while X < M[J] do J:= J-1;

¦ ¦ if I <= J then

¦ ¦ begin

¦ ¦ ¦ W:= M[I]; {Обмен местами

¦ ¦ ¦ M[I]:= M[J]; I-го и J-го

¦ ¦ ¦ M[J]:= W; элементов,

¦ ¦ ¦ I:=I+1; дальнейшее продвижение

¦ ¦ ¦ J:=J-1; вперед (назад)}

¦ ¦ end;

¦ ¦ {Выход из цикла, если левый край перевалил за правый}

¦ until I > J;

¦ { Повтор обмена для левой части }

¦ if L < J then QUICKSORT (L,J,M);

¦ { Повтор обмена для правой части }

¦ if R > i then QUICKSORT (I,R,M);

¦

end;

ПОЯСНЕНИE. Рассмотрим работу этой процедуры на примере сортировки следующего массива:

Здесь имеем значения L=1; I=1; J=7; R=7. Цикл WHILE X > M[I] при Х = 2 дает сразу же отказ и значение I остается старым, т.е. I = 1. Цикл WHILE X < M[J] при Х = 2 дает J = 6. Сравнение IF I <= J дает 1 <= 6, т.е. истина, отсюда идет обмен между I-м и J-м элементами - первый элемент 6 меняется местом с шестым элементом 1:

и индекс I (J) увеличивается (уменьшается):

I:=I+1, т.е. I = 2;

J:=J-1, т.е. J = 5.

Сравнение I > J, т.е. 2 > 5, является ложным, поэтому идет возврат наверх. Циклы WHILE доводят значения переменной I до 2, а значение J становится равным 4. Так как I=2 <= J=4, то идет обмен между 2-м и 4-м элементами:

и индексы получают значения: I = 3, J = 3.

При таких значениях индексов имеем M[I]=M[J]=3, что в результате работы циклов WHILE дает I=3 и J=2. Сравнение I<=J будет ложным, поэтому обмена элементов нет, кроме того, становится истинным условие проверки окончания работы цикла REPEATE (I>J) и происходит переход на рекурсивное обращение к самой процедуре.

Из двух условий истинным является первое (сравнение L < J дает 1< 2), поэтому идет обращение к процедуре при параметрах L=1 и R=2. Однако для этих праметров упорядочивание уже произошло. Затем формируется отрезок [3,7], где происходит обмен между 5-м и 7-м элементами:

В результате этой работы массив уже упорядочен, однако затем формируются отрезки [3,6] и [5,6], при которых никаких обменов не происходит, но параметры I, J получают значения: I=6, J=4. Ни одно из сравнений L<J (5<4) и R>I (6>6) не является истинным, поэтому рекурсия завершается и процедура заканчивает свою работу.

ЗАМЕЧАНИЕ. Данная процедура очень медленно обрабатывает уже упорядоченный массив.

Похожие работы

Основы программирования на языке Паскаль

Скачать

168304

7

26

... .....-46.780 Program Prim24; Var r1,r2:real; BEGIN r1:=-46.78; r2:=-46.78; writeln('r1=',r1:12:3,' r2=',r2:9:4); writeln('_______________________________'); readln; END. 6. Массивы   6. 1. Описание массивов В языке Паскаль можно обрабатывать не только отдельные переменные, но и их совокупности. Одной из таких совокупностей (структурированных) данных является массив. ...

Алгоритмические языки и программирование Системное программное обеспечение Технология программирования"

Скачать

112819

0

0

... . Объясните, для чего служат разрешения и привилегии в Windows NT. Зав. кафедрой --------------------------------------------------   Экзаменационный билет по предмету СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ Билет № 22 Перечислите возможности и инструменты системы программирования Microsoft Developer Studio. Укажите для чего предназначается буфер в системах ввода-вывода, ...

Основные понятия алгоритмического языка

Скачать

91405

0

0

... с внешнего устройства (из входного файла) в основную память ЭВМ, операция вывода - это пересылка данных из основной памяти на внешнее устройство (в выходной файл). Файлы на внешних устройствах часто называют физическими файлами. Их имена определяются операционной системой. В программах на языке Паскаль имена файлов задаются с помощью строк. Например, имя файла на диске может иметь вид: ...