Сортировка прямым обменом (метод «пузырька»)

Алгоритмы сортировки и поиска / Сортировка прямым обменом (метод «пузырька»)

 

Алгоритм сортировки прямым обменом основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут отсортированы все элементы. Как и в методе прямого выбора, совершаются проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к началу массива.

Если рассматривать массивы как вертикальные, а не горизонтальные построения, то элементы можно интерпретировать как пузырьки в банке с водой, причем вес каждого соответствует его ключу. В этом случае при каждом проходе один пузырек как бы поднимается до уровня, соответствующего его весу. Такой метод известен под именем «пузырьковая сортировка».
Пузырьковая сортировка
Реализация сортировки методом "пузырька" на Си

1
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
#define _CRT_SECURE_NO_WARNINGS // для корректной работы scanf()
#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)/2,

Mmax = 3(n2 - n)/4.

 
Резюме: «обменная сортировка» представляет собой нечто среднее между сортировками с помощью включений и с помощью выбора; фактически в пузырьковой сортировке нет ничего ценного, кроме привлекательного названия.


Назад: Алгоритмы сортировки и поиска

Комментариев к записи: 2

  • Маленькую поправочку нужно внести в код. Во внешнем цикле нужно поставить не i<size
    а i<size-1 т.к. нет смысла запускать последний проход внешнего цикла, потому что все элементы уже будут отсортированы на предпоследнем проходе.


Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *