Теория и практика параллельных вычислений
Последовательный алгоритм
Последовательный алгоритм пузырьковой сортировки (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]); }
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий