Алгоритм сортировки прямым обменом основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут отсортированы все элементы. Как и в методе прямого выбора, совершаются проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к началу массива.
Если рассматривать массивы как вертикальные, а не горизонтальные построения, то элементы можно интерпретировать как пузырьки в банке с водой, причем вес каждого соответствует его ключу. В этом случае при каждом проходе один пузырек как бы поднимается до уровня, соответствующего его весу. Такой метод известен под именем «пузырьковая сортировка».
Реализация сортировки методом «пузырька» на Си
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
#include <stdio.h>
// Функция сортировки прямым обменом (метод "пузырька")
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[10]; // Объявляем массив из 10 элементов
// Вводим значения элементов массива
for (int i = 0; i < 10; i++)
{
printf("a[%d] = ", i);
scanf("%d", &a[i]);
}
bubbleSort(a, 10); // вызываем функцию сортировки
// Выводим отсортированные элементы массива
for (int i = 0; i<10; i++)
printf("%d ", a[i]);
getchar(); getchar();
return 0;
}
Результат выполнения
Анализ алгоритма
Число сравнений в алгоритме прямого обмена
С = (n2 - n)/2,
а минимальное, среднее и максимальное число перемещений элементов равно соответственно
Mmin = 0,
Mср = 3(n2 - n)/4,
Mmax = 3(n2 - n)/2.
Резюме: «обменная сортировка» представляет собой нечто среднее между сортировками с помощью включений и с помощью выбора; фактически в пузырьковой сортировке нет ничего ценного, кроме привлекательного названия.
Назад: Алгоритмы сортировки и поиска
Комментариев к записи: 9