Сортировка пузырьком (реализация на C++)

C++   16 февраля 2012  Автор статьи:  

Приведем пример реализации алгоритма сортировки выбором. На вход алгоритму подается массив чисел типа int, заданный своим размером и элементами. В результате работы алгоритм выводит отсортированный массив.

На практике алгоритм применяется чрезвычайно редко в силу своей неэффективности по сравнению с более быстрыми алгоритмами сортировки. Тем не менее этот алгоритм является основой для некоторых других, более сложных методов сортировки.

Сложность алгоритма — O(n^2), где n — это число элементов массива.

Заметим, что приведенная реализация алгоритма является устойчивой, т.е. она не меняет относительный порядок элементов с одинаковыми значениями.


#include
using namespace std;

int main()
{
// Считываем размер массива,
// который необходимо отсортировать
int size;
cin >> size;

// Динамически выделяем память под
// хранение массива размера size
int *a = new int[size];

// Считываем массив
for (int i = 0; i < size; i++) { cin >> a[i];
}

// Внешний цикл алгоритма совершает
// ровно size итераций
for (int i = 0; i < size; i++) { // Массив просматривается с конца до // позиции i и "легкие элементы всплывают" for (int j = size - 1; j > i; j--)
{
// Если соседние элементы расположены
// в неправильном порядке, то меняем
// их местами
if (a[j] < a[j - 1]) { swap (a[j], a[j - 1]); } } } // Выводим отсортированный массив for (int i = 0; i < size; i++) { cout << a[i] << ' '; } return 0; }

  • Fess

    Подскажите, а почему во втором цикле (где массив просматривается с конца до позиции i и «легкие элементы всплывают»)

    for (int j = size — 1) — используется не просто size, а size — 1? Потому что нумерация элементов массива начинается с нуля?

  • Sergey

    Самый нормальный код пузырька из всех что я видел..

Научиться программировать

  • на Delphi

  • на Java

  • на C++