Сортировка пузырьком - простейший для понимания и реализации алгоритм сортировки. Эффективен только для небольших массивов, считается учебным и не применяется в практических задачах. С другой стороны, метод используется в учебных целях, поскольку лежит в основе некоторых других сортировок, более эффективных, таких как шейкерная (Коктейльная) сортировка, пирамидальная сортировка и быстрая сортировка.

Алгоритм сортировки

Алгоритм заключается в многократном проходе по массиву — сначала от первого до последнего элемента, потом от первого до предпоследнего, потом от первого до третьего с конца и т.д. При проходе сравниваются два соседних элемента. Если они не упорядочены относительно друг друга, то меняются местами. В конце каждого прохода на своё место будет вставать один элемент.

Визуализация работы алгоритма

Оптимизации

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

Саму пузырьковую сортировку можно различными способами улучшать и получать некоторые другие обменные алгоритмы:

• Коктейльная сортировка. Двунаправленная пузырьковая сортировка. Дойдя до конца массива начинаем проход в начало, тем самым вытесняем большие элементы в конец, а маленькие - в начало массива.
• Чётно-нечётная сортировка. За один проход нечётные индексы сравниваются с чётными, затем чётные — с нечётными.
• Сортировка расчёской. Сравниваются не соседи, а элементы между которыми некоторое расстояние, уменьшающееся после каждого прохода по массиву.

Реализация алгоритма

void bubbleSort(int arr[], int n)
{
   int i, j;
   for (i = 0; i < n-1; i++)      

       // Last i elements are already in place   
       for (j = 0; j < n-i-1; j++) 
           if (arr[j] > arr[j+1])
              swap(&arr[j], &arr[j+1]);
}

Оптимизированная версия сортировки

static void BubbleSort(List<int> a)
        {
            bool NotSorted = true;
            while (NotSorted)
            {
                NotSorted = false;                  
                for (int i = 1; i < a.Count(); i++)
                {
                    if (a[i] < a[i - 1])
                    {
                        int temp = a[i];
                        a[i] = a[i - 1];
                        a[i - 1] = temp;
                        NotSorted = true;
                    }
                }
            }
        }

Характеристики алгоритма