Послідовний алгоритм.

·Алгоритм швидкого сортування, запропонованої Хоаром (Hoare C.A.R.), грунтується на послідовному розділенні сортованого набору даних на блоки меншого розміру таким чином, що між значеннями різних блоків забезпечується відношення впорядкованості (для будь-якої пари блоків всі значення одного з цих блоків не перевищують значень іншого блоку):

·На першій ітерації методу здійснюється розподіл початкового набору даних на перші дві частини - для організації такого розподілу вибирається деякий ведучий елемент і всі значення набору, менші провідного елемента, переносяться в перший формований блок, вся решта значень утворює другий блок набору

·На другій ітерації сортування описані правила застосовуються рекурсивно для обох сформованих блоків і т.д.

При оптимальному виборі провідних елементів після виконання log2n ітерацій початковий масив даних виявляється впорядкованим

Сортування з використанням регулярного набору зразків: паралельний алгоритм.

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

0, m, 2m.,(p-1) m, де m=n/p2

Другий етап: всі сформовані на процесорах набори даних збираються на одному з процесорів системи і об'єднуються в ході послідовного зливання в одну впорядковану множину; з одержаної безлічі значень з елементів з індексами

формується набір провідних елементів, який передається всім процесорам;

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

Третій етап: кожний процесор розсилає виділені раніше частини свого блоку всій решті процесорів системи відповідно до порядку нумерації - частина j, 0Ј j<p, кожного блоку пересилається процесору з номером j

Четвертий етап: кожний процесор виконує злиття p одержаних частин в один відсортований блок.

· Розглянуті способи паралельного виконання трьох широко відомих методу впорядкування даних:

·Алгоритм бульбашкового сортування

·Сортування Шелла

·Швидке сортування

·Для алгоритму швидкого сортування приведено дві додаткові модифікації:

·Узагальнене швидке сортування

·Сортування з використанням регулярного набору зразків

· Представлена програмна реалізація методу узагальненого швидкого сортування

· Використаний порядок викладу паралельних методів сортування можна розглядати як приклад процесу послідовного вдосконалення паралельних обчислень з метою поліпшення показників прискорення і ефективності

Дата добавления: 2015-08-18