"Пузырьковая" cортировка

Программа сортирует значения массива следующим образом: сначала она сравнивает элементы массива a[0] и а[1], меняя местами их значения, если они не упорядочены, затем проделывает то же самое с элементами а[1] и а[2], а[2] и а[3] и т.д.. При выполнении этой последовательности операций элементы с большим значанием будут продвигаться вправо, и на самом деле элемент с наибольшим значением займет положение а[7]. При многократном выполнении этого процесса соответствующие элементы попадут в позиции а[6], а[5] и т.д., так что в конце концов все элементы будут упорядочены.

Главное достоинство пузырьковой сортировки заключается в простоте ее программирования. Однако, выполняется она медленно. Это становится очевидным при сортировке больших массивов.

На рисунке представлено действие данной сортировки на восьми числах.

Рисунок - Пузырьковая сортировка

Ряд чисел удобно представить не горизонтально, а вертикально, чтобы элемент а[7] был сверху, а а[0] - снизу. Используемая при сортировке техника, получила название метода пузырька (пузырьковая сортировка ), потому что большие элементы, подобно пузырькам, "всплывают" на соответствующую позицию.

Пример:

Возьмем массив из чисел:

Первый проход:

Второй проход:

Третий проход:

Четвертый проход:

Массив отсортирован

Реализация алгоритма:

// "Пузырьковая" сортировка

#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>
#include <time.h>

template <typename T>
void BSort(T array[] /* Сортируемый массив */, int size /* Размер массива */)
{
 // Флаг сортировки 
 // (false-массив не отсортирован, true-массив отсортирован)
 // Изначально предполагаем оптимистический вариант
 bool flag = true; 
 
 // Переменные циклов
 int i, j;

 // Временная переменная для обмена значений элементов
 T temp;

 // Создаем бесконечный цикл
 for (j = 1; ; j++) 
 {
 // С помощью переменной j не учитываем уже отсортированные элементы
 for(i = 0; i < size - j; i++)
 if (array[i] > array[i + 1]) 
 {
 //выполняем перестановку
 temp = array[i];
 array[i] = array[i + 1];
 array[i + 1] = temp;
 flag = false;
 }
 if(flag) //массив отсортирован?
 break; //да - выход из цикла
 flag = true; //иначе - устанавливаем флаг сортировки
 }
}

// Функция для вывода массива
template <typename T>
void PrintArray(T array[], int size)
{
 // функция setw(n) создает поле для вывода с шириной n символов
 for(int i = 0; i < size; i++)
 {
 if(i % 5 == 0)
 cout << endl;
 cout << setw(15) << array[i];
 }
 cout << endl;
}

// Тестирование
void main()
{
 // Инициализация генератора случайных чисел
 srand(time(0));
 // Размер массивов
 const N = 10;
 
 int i;
 int a[N];
 float b[N];

 // Инициализация массивов случайными числами в диапазоне от -10 до 10
 for(i = 0; i < N; i++)
 {
 a[i] = rand() % 21 - 10;
 b[i] = rand() / (float)32767 * 20 - 10;
 }

 // Вывод массивов
 cout << "Array A:\n";
 PrintArray(a, N); 

 cout << "Array B:\n";
 PrintArray(b, N); 

 // Сортировка массивов
 BSort(a, N);
 BSort(b, N);

 // Вывод отсортированных массивов
 cout << endl;
 cout << "Array A:\n";
 PrintArray(a, N); 

 cout << "Array B:\n";
 PrintArray(b, N); 
}