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

В этом модуле мы будем рассматривать различные алгоритмы сортировки. Начнем с самого очевидного – пузырьковой сортировки.

Как бы мы руками отсортировали большой список чисел, если бы он лежал перед нами? Первое, что приходит на ум – сравнивать соседние элементы в списке и менять местами, если нужно. Так же работает и пузырьковая сортировка:

    void bubble_sort(vector<int> &A) {
    	int N = A.size();

    	for (int i = 0; i < N - 1; ++i) {
			for (int j = 0; j < N - i - 1; ++j) {
				if (A[j] > A[j+1])
					swap(A[j], A[j+1]);
			}
    	}
    }

Пусть есть массив $[6,5,4,3,2,1]$.

В первый проход внутреннего цикла поменяются местами элементы $6$ и $5$. Получится массив $[5,6,4,3,2,1]$. Во второй проход поменяются местами элементы $6$ и $4$, в итоге получаем список $[5,4,6,3,2,1]$. В третий проход поменяются $6$ и $3$ и так далее. Таким образом, $6$ как бы “упадет на дно” массива, а меньшие элементы, подобно пузырькам, “всплывут на поверхность”.

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

Алгоритм сортировки пузырьком сработает за $O(N^2)$ операций в худшем случае – полностью неотсортированный массив, поэтому кроме как в школьной программе он мало где применяется. Но стоит также отметить, что этот алгоритм лежит в основе более совершенных сортировок, в частности быстрой сортировки, которую мы рассмотрим в дальнейшем.