Упражнение № 9. Обменная сортировка с разделением (сортировка Хоара)

Пример 73. Составить программу «быстрой сортировки». Решение. Пусть исходный массив состоит из восьми элементов:

8 12 3 7 19 11 4 16

В качестве барьерного элемента будем брать средний элемент массива. Барьер­ный элемент — 7. Произведя необходимые перестановки для разделения, получим:

(4 3) 7 (12 19 11 8 16)

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

: з>			(12				16)
			(12				16)
			(8)		(19		16)
				И	(19		16)
						(19	16)
						(16)

 

Массив отсортирован полностью.

Алгоритм «быстрой» сортировки можно определить как рекурсивную процеду­ру, параметрами которой являются нижняя и верхняя границы изменения индек­сов сортируемой части исходного массива.

Ргодгат Ехатр1е_7 3;

Чаг а: Аггау[1..10] 05: 1п1: едег;

Ргосейиге {формирование массива из файла}

Чаг I: ЪехЪ; 1: 1п-Ьедег; Ведхп

Азз1дп(: Е, ^! с: \з.(За^¹); КезеМЛ; Еог 1: =1 То 10 Бо Кеай(а[1]); Еп< 1;

Ргосес1иге Рг±пЬ; {печать массива}

Чаг 1: Iпоедет;

Ведхп

Еог х: =1 То 10 Во ИгхЪе(а[х]: 5); ЭДгИ: е1п Еп< 1;

Ргосейиге 0и1ск_зог" Ыпд (т, 1: 1п1: едег)/

Чаг I поедет;

Ведхп

1: =ш;:): =1; х: =а[(ш+1) ^^V 2]; Кереа-Ь

МЫ1е а[1]< х Во 1пс{±); МЫ1е а[^]> x Бо с1ес(: П; II ТЬеп

Ведхп

^: =а [ х ] / а [ 1 ]: =а[}]; а[Л: =м; 1пс(х); с! ес (□);

Епс!

Ш1*: х1 Х> З;

ш< з ТЬеп ди1ск_зог1: 1пд (ш, з); II: х< 1 ТЬеп дихск__зог-Ыпд (1, 1); Еп< 1;

Ведхп {основная программа}

Правый подмассив:

Левый подмассив:

ЭДгИ: е1п (¹ массив: ¹); 1Пх-Ь; рг1п" Ь; дихск__зог-Ыпд (1, 10); ^гх'Ье1п (¹ отсортированный массив ¹); ргхпЪ; Епс!.

Упражнение № 10. Линейный поиск заданного элемента в массиве

Пример 74. Написать программу поиска элемента х в массиве из п элементов. Значение элемента х вводится с клавиатуры. Решение. Структуры данных:

СопзЪ п=10; {размерность массива}

Уаг а: Аггау[1.. п] о1 1п1: едег; {массив из п элементов целого типа} х: 1п1: едег; {искомый элемент целого типа}

Для решения задачи можно использовать цикл

Еог 11=1 То п Во II а[1]=х ТЬеп к: =1;.

Однако в случае нескольких равных эталону элементов будет найден лишь пос­ледний.

Чтобы прервать просмотр сразу после обнаружения заданного элемента, необ­ходимо использовать цикл с предусловием. В результате:

• либо будет найден искомый элемент, то есть найдется такой индекс /', что аЩ = х;

• либо будет просмотрен весь массив, и искомый элемент не будет обнаружен.

Ргодгат Ехатр1е_7 4; сопз1: п=10;

Уаг а: Аггау[1..п] 01 1п1: едег; х, 1: 1п-Ьедег;

Ргосес1иге 1п11:; {формирование массива из файла} Уаг I: ЬехЬ;

л.: 1п-Ьедег;,

Вед±п

Азз1дп (I, ' с: \з. с! а1: '); Кезе'Ь; Рог л. г —1 То п Во Кеас! (I, а [л_]); Епс1;

Ргосейиге Ргл-пЪ; {печать массива}

Уаг л.: 1п1: едег;

Вед±п

Еог 1: =1 То п Во №гИ: е (а [ 1 ]: 5); ДОгл-1: е1п Епс1;

Вед±п {основная программа}

ЭДгл.1: е1п (' массив: '); л_пл_1:; ргл-пЪ; Мг11: е1п; Мг11: е ('введи эталон х= '); КеасИп (х); 1: =0; ЮЬНе (1< =п) ап< 3 (а[1]Ох) Во Вед±п

1: =1+1; Епс1;

II К=п ЪЪеп Югл.'Ье ('найден элемент на 1, 'месте') Е1зе ЭДгл_1: е ('такого элемента нет'); Епс1.