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

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

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

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

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

Реализация сортировки методом "пузырька"
void bubbleSort(int *num, int size) {
  int i, j, temp;
  for (i = 0; i < size; i++) {
    for (j = (size - 1); j > i; j--) {
      if (num[j-1] > num[j]) {
        temp = num[j-1];
        num[j-1] = num[j];
        num[j] = temp;
      }
    }
  }
}
Анализ алгоритма

Число сравнений в алгоритме прямого обмена

С = (n2 - n)/2,

а минимальное, среднее и максимальное число перемещений элементов равно соответственно

Mmin = 0,

Mср = 3(n2 - n)/2,

Mmax = 3(n2 - n)/4.

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

Назад


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

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

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


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

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