Теория и практика параллельных вычислений



             

Последовательный алгоритм


Последовательный алгоритм пузырьковой сортировки (the bubble sort algorithm) (см., например, [[26], [50]]) сравнивает и обменивает соседние элементы в последовательности, которую нужно отсортировать. Для последовательности

(a1, a2, ..., an)

алгоритм сначала выполняет n-1 базовых операций "сравнения-обмена" для последовательных пар элементов

(a1, a2), (a2, a3), ..., (an-1, an).

В результате после первой итерации алгоритма самый большой элемент перемещается ("всплывает") в конец последовательности. Далее последний элемент в преобразованной последовательности может быть исключен из рассмотрения, и описанная выше процедура применяется к оставшейся части последовательности

(a'1, a'2, ..., a'n-1).

Как можно увидеть, последовательность будет отсортирована после n-1 итерации. Эффективность пузырьковой сортировки может быть улучшена, если завершать алгоритм в случае отсутствия каких- либо изменений сортируемой последовательности данных в ходе какой-либо итерации сортировки.

Алгоритм 9.1. Последовательный алгоритм пузырьковой сортировки

// Алгоритм 9.1. // Последовательный алгоритм пузырьковой сортировки void BubbleSort(double A[], int n) { for (int i = 0; i < n - 1; i++) for (int j = 0; j < n - i; j++) compare_exchange(A[j], A[j + 1]); }




Содержание  Назад  Вперед