Студопедия Главная Случайная страница Задать вопрос

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Упражнение № 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:=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Пх-Ь; рг1п"Ь; дихск__зог-Ыпд (1,10) ; ^гх'Ье1п ( 1 отсортированный массив 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.






Дата добавления: 2014-11-10; просмотров: 260. Нарушение авторских прав

Studopedia.info - Студопедия - 2014-2017 год . (0.025 сек.) русская версия | украинская версия