Алгоритм СОРТ-1 (попарне сортування)

↑

▷ Содержание

⇐ ПредыдущаяСтр 6 из 8Следующая ⇒

Крок 1. Введення початкових даних:

input N (N - кількість сортованих даних)

for i = 1 to N do read (x(i)) od.

Крок 2. Взвод прапора F (перестановка) для штучного запуску циклу

while-do:

F = 1.

Крок 3. Зовнішній цикл по прапору F - була чи ні перестановка при черговому переборі всіх пар:

while F = 1 do

F = 0 (скидання прапора перед черговим перебором пар)

[внутрішній цикл - формування пар і порівняння їх елементів]

for i = 1 to N - 1 do

[порівняння елементів чергової пари]

if x(i)> x(i + 1) then

[перестановка чисел і взвод прапора]

а = x(i); x(i)= x(i + 1); x(i + 1)= а: F = 1

fi

od

od

Крок 4. Виведення результатів. for i = 1 to N do write (x(i)) od

Крок 5. Кінець.

ОБМІННЕ СОРТУВАННЯ відрізняється від попарної методом формування приватного завдання - пари порівнюваних елементів:

ініціалізувався покажчик Р, яким фіксується довільний, наприклад, 1-й елемент. Серед тих, що залишилися (що знаходяться "нижче" за покажчик Р) відшукується найменший, який фіксується покажчиком V. Елементи, помічені покажчиками P і V, і утворюють елементи приватного завдання, яке як і в СОРТ-1 вирішується єдиним і очевидним чином.

В результаті (продумайте це!) на місце, помічене покажчиком Р, потрапить найменший елемент послідовності, повторна обробка якого виключається інкрементом покажчика Р після рішення чергової приватної задачі.

Послідовне застосування викладеної процедури до частини завдання, що залишилася, гарантує, що на кожному черговому кроці до вже впорядкованих елементів додаватиметься найменший елемент з тих, що залишилися, тобто

(i) послідовність упорядковуватиметься належним чином

(ii) трудомісткість сортування прогресивно падатиме, оскільки після кожного кроку для перегляду і вибору найменшого залишатиметься все менше і менше елементів.

Для довгих послідовностей доцільно спочатку застосувати метод розділення завдання на рівні частини - розділити початкову послідовність дві або чотири і так далі рівних частин, і тільки потім до кожної з цих частин застосувати метод розділення на нерівні частини, зокрема у вигляді обмінного сортування. При цьому, проте, виникає нова проблема: як об'єднати приватні рішення в одне загальне і не втратити виграш! Це забезпечує алгоритм ЗЛИТТЯ (merge) - сортування по методу розділення завдання на нерівні частини, в якому приватне завдання - формування пари елементів для чергового порівняння, - вирішується з використанням стекової пам'яті.

Стеками при цьому служать приватні відсортовані рішення, і на чергове порівняння завжди поступають елементи з вершин стеків. Менший з вершинних елементів записується у вихідний список, а покажчик вершини відповідного стека зрушується (інкрементується) на одну позицію. Якщо один із стеків вичерпається раніше іншого, то елементи другого стека, що залишилися, просто дописуються у вихідний список.

Наступна схема ілюструє механізм злиття:

1) ініціюються два покажчики L, що визначає початок лівої відсортованої частини, і R, що визначає початок правої відсортованої частини;

2) далі в циклі від 1 до N кожного разу порівнюються вершинні елементи X(L) і X(R) лівого і правого стеків (у яких після введення покажчиків перетворилися відсортовані частини), у вихідний список Z виводиться менший з них, а відповідний покажчик зрушується на одну позицію:

Зрозуміло, що в загальному випадку швидкість вичерпання стеків буде різна, і один із стеків спустіє раніше іншого. Тому в механізм злиття необхідно ввести 2 заглушки для перевірки вичерпання лівого і/або правого стеків:

...

if L>s (вичерпаний лівий стек) then

z(i)= x(R); R = R + 1 [дописати в буфер Z елементи правого стека]

fi

if R>n (вичерпаний правий стек) then

z(i)= x(L); L = L + 1; [дописати в буфер Z елементи лівого стека]

fi

...

РЕКУРСИВНЕ СОРТУВАННЯ.

Алгоритм К. Хоара з використанням методу половинного ділення

1. Знайти середній Ел і записати його індекс в S
2. Переглядаючи, лівий підінтервал (зліва направо), запам'ятати індекс A(i), який більше або рівний A(S)
3. Переглядаючи, правий підінтервал (справа наліво), запам'ятати індекс A(j), який менше або рівний A(S)
4. Поміняти місцями A(i) і A(j)
5. Продовжувати з к.2 поки індекси i і j не перетнуться (зустрінуться); в результаті початковий масив буде впорядкований відносно A(S) (зліва від нього всі Ел будуть менший або рівні A(S), а справа - рівні або більше)

Продовжити з к.1 поки довжина чергового лівого або правого підінтервалу не виявиться рівною одному елементу.

ЛАБОРАТОРНА РОБОТА № 7

Познавательные статьи:



Где возникла философия и почему?

Относительная высота сжатой зоны бетона

Сущность проекции Гаусса-Крюгера и использование ее в геодезии

Тарифы на перевозку пассажиров