Ефективність швидкого сортуванн

Програмна реалізація алгоритму

Можливість розпаралелення

Збіжність алгоритму швидкого сортування

Виконання сортування в такому випадку може бути

розділене на два послідовних етапи.

Усі відповіді вірні.

Для алгоритму Шелла топологія комунікаційної

мережі може бути ефективно представлена у вигляді N мірного

На першому етапі (N ітерацій) здійснюється

взаємодія

Загальна ідея

сортування складається в порівнянні на початкових

стадіях сортування пар значень, наявних досить далеко один від одного у

впорядкованому наборі даних.  Така

модифікація методу сортування дозволяє швидко переставляти далекі

невпорядковані пари значень (сортування таких пар зазвичай вимагає великої

кількості перестановок, якщо використовується порівняння тільки сусідніх

елементів).

На першій ітерації методу здійснюється розподіл

вихідного набору даних на перші дві частини - для організації такого поділу

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

елементу, переносяться в перший формуючий

Суть  полягає в тому, що в алгоритм

сортування вводяться два різних правила виконання ітерацій методу: в залежності

від парності або непарності номера ітерації сортування для обробки вибираються

елементи з парними або непарними індексами відповідно, порівняння виділених

значень завжди здійснюється з їх правими сусідніми елементами.

парної-непарної перестановки (the odd-even

transposition method)

 "порівняти і переставити" (compare-exchange)

"порівняти і розділити"

 "порівняти і переслати"

декомпозиція даних

розпаралелювання обчислень,

розрапалелення даних

розбиття на підзадачі

«гонки процесів»

«гонки потоків»

«гонки змінних»

«гонки даних»

«гонки процесів»

«гонки потоків»

«гонки змінних»

«гонки даних»