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

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

 

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









 

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

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)/4,

Mmax = 3(n2 - n)/2.

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


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

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


  • Я конечно не критикую. Просто скажу, как лично я сейчас разбирался с этим видом сортировки. Приведенная иллюстрация всё-таки сжатая. Не просто с первого раза понять идею. То, что на картинке называется шагом, на самом деле является шагом по внешнему циклу по i, тогда как во внутреннем цикле по j, каждый раз происходит попарное последовательное сравнение элементов от первого до последнего в массиве, и перестановка в текущей паре, если необходимо. Мне помогло разобраться это видео: https://www.youtube.com/watch?v=5JMInXAtnQg

  • Николай
    Здравствуйте, скажите пожалуйста, почему во внутреннем цикле j>i
    1
    for (int j = (size - 1); j > i; j--)

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

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

Ваш адрес email не будет опубликован.