Алгоритм сортировки прямым обменом основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут отсортированы все элементы.
Как и в методе прямого выбора, совершаются проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к началу массива.
Если рассматривать массивы как вертикальные, а не горизонтальные построения, то элементы можно интерпретировать как пузырьки в банке с водой, причем вес каждого соответствует его ключу. В этом случае при каждом проходе один пузырек как бы поднимается до уровня, соответствующего его весу. Такой метод известен под именем «пузырьковая сортировка» или «метод пузырька».
Реализация сортировки методом «пузырька» на Си
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#define _CRT_SECURE_NO_WARNINGS // для корректной работы scanf()
#include <stdio.h>
#define SIZE 10 // размер массива сортируемых элементов
// Функция сортировки прямыми включениями
void bubbleSort(int* num, int size)
{
// Для всех элементов
for (int i = 0; i < size - 1; i++)
{
for (int j = (size - 1); j > i; j--) // для всех элементов после i-ого
{
if (num[j - 1] > num[j]) // если текущий элемент меньше предыдущего
{
int temp = num[j - 1]; // меняем их местами
num[j - 1] = num[j];
num[j] = temp;
}
}
}
}
int main()
{
int a[SIZE]; // Объявляем массив из 10 элементов
// Вводим значения элементов массива
for (int i = 0; i < SIZE; i++)
{
printf("a[%d] = ", i);
scanf("%d", &a[i]);
}
bubbleSort(a, SIZE); // вызываем функцию сортировки
// Выводим отсортированные элементы массива
for (int i = 0; i < SIZE; i++)
printf("%d ", a[i]);
getchar();
getchar();
return 0;
}Результат выполнения
Анализ алгоритма
Число сравнений в алгоритме прямого обмена
{\displaystyle{С = \frac {n^2 — n}{2}}}
а число перемещений элементов равно соответственно
{\displaystyle{M_{min} = 0}}
{\displaystyle{M_{max} = 3 \cdot \frac {n^2-n}{2}}}
Резюме: «обменная сортировка» представляет собой нечто среднее между сортировками с помощью включений и с помощью выбора; фактически в пузырьковой сортировке нет ничего ценного, кроме привлекательного названия.
В реальности, когда исходные данные частично отсортированы, количество циклов сравнения может оказаться значительно меньше максимального количества. Поэтому можно ввести дополнительную переменную (в примере ниже это переменная flag), которая будет индицировать наличие перемещений в массиве на каждой итерации внешнего цикла.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#define _CRT_SECURE_NO_WARNINGS // для корректной работы scanf()
#include <stdio.h>
#define SIZE 10 // размер массива сортируемых элементов
// Функция сортировки прямыми включениями
void bubbleSort(int* num, int size)
{
int flag = 0; // для отслеживания перемещений
// Для всех элементов
for (int i = 0; i < size - 1; i++)
{
flag = 0;
for (int j = (size - 1); j > i; j--) // для всех элементов после i-ого
{
if (num[j - 1] > num[j]) // если текущий элемент меньше предыдущего
{
int temp = num[j - 1]; // меняем их местами
num[j - 1] = num[j];
num[j] = temp;
flag = 1;
}
}
if (flag == 0) // последовательность уже отсортирована
break;
}
}
int main()
{
int a[SIZE]; // Объявляем массив из 10 элементов
// Вводим значения элементов массива
for (int i = 0; i < SIZE; i++)
{
printf("a[%d] = ", i);
scanf("%d", &a[i]);
}
bubbleSort(a, SIZE); // вызываем функцию сортировки
// Выводим отсортированные элементы массива
for (int i = 0; i < SIZE; i++)
printf("%d ", a[i]);
getchar();
getchar();
return 0;
}