Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов.

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

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

Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию.

Популярные алгоритмы сортировки. Что такое алгоритм?

Пример кода на языке PHP.

for ($i=(count($A)-1);$i>=0;$i--) {
    for ($j=0;$j<=($i-1);$j++)
        if ($A[]>$A[$j+1]) {
            $tmp = $A[$j];
            $A[$j] = $A[$j+1];
            $A[$j+1] = $tmp;
        }
}

Пример кода на языке C++.

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
template <class T>
void bubbleSort(T a[], long size){
    long i, j;
	T x;
	for(i=0;i<size;i++){            // i - номер прохода
		for(j=size-1;j>i;j--){     // внутренний цикл прохода
			if(a[j-1]>a[j]){
				x=a[j-1];
				a[j-1]=a[j];
				a[j]=x;
			}
		}
	}
}

void main(){
	srand(time(NULL));
	const long SIZE=10;
	int ar[SIZE];
	
	// до сортировки
	for(int i=0;i<SIZE;i++){
		ar[i]=rand()%100;
		cout<<ar[i]<<"\t";
	}
	cout<<"\n\n";
	bubbleSort(ar,SIZE);

	// после сортировки
	for(int i=0;i<SIZE;i++){
		cout<<ar[i]<<"\t";
	}
	cout<<"\n\n";
}

Среднее число сравнений и обменов имеют квадратичный порядок роста, отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен. Тем не менее, у него есть громадный плюс: он прост и его можно по-всякому улучшать. Чем мы сейчас и займемся.

Рассмотрим ситуацию, когда на каком-либо из проходов не произошло ни одного обмена. Это значит, что все пары расположены в правильном порядке, так что массив уже отсортирован. И продолжать процесс не имеет смысла. Таким образом первый шаг оптимизации заключается в запоминании, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу.

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

Качественно другое улучшение алгоритма можно получить из следующего наблюдения. Хотя "легкий" пузырек снизу поднимется наверх за один проход, "тяжелые" пузырьки опускаются со минимальной скоростью: один шаг за итерацию. Так что массив 2 3 4 5 6 1 будет отсортирован за 1 проход, а сортировка последовательности 6 1 2 3 4 5 потребует 5 проходов.

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

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
template <class T>
void shakerSort(T a[], long size) {
  long j, k=size-1;
  long lb=1, ub=size-1; // границы неотсортированной части массива
  T x;

  do{
      // проход снизу вверх 
	for(j=ub;j>0;j--){
		if(a[j-1]>a[j]){
			x=a[j-1];
			a[j-1]=a[j];
			a[j]=x;
			k=j;
		}
	}
    lb = k+1;

    // проход сверху вниз 
    for(j=1;j<=ub;j++){
		if(a[j-1]>a[j]){
			x=a[j-1];
			a[j-1]=a[j];
			a[j]=x;
			k=j;
		}
    }
    ub=k-1;

  }while (lb<ub);
}

void main(){
	srand(time(NULL));
	const long SIZE=10;
	int ar[SIZE];
	
	// до сортировки
	for(int i=0;i<SIZE;i++){
		ar[i]=rand()%100;
		cout<<ar[i]<<"\t";
	}
	cout<<"\n\n";
	shakerSort(ar,SIZE);

	// после сортировки
	for(int i=0;i<SIZE;i++){
		cout<<ar[i]<<"\t";
	}
	cout<<"\n\n";
}

Таким образом, мы выяснили, что можем оптимизировать сортировку "пузырьком" на свой вкус.