Что такое сортировка пузырьковым методом

Сортировка массива

Одной из самых распространенных операций, выполняемых над массивами, является сортировка. Существует множество различных алгоритмов сортировки. Широко применяется, например, сортировка перемешиванием и сортировка методом Шелла. Известен также алгоритм Quicksort (быстрая сортировка с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины). Однако самым простым считается алгоритм сортировки пузырьковым методом. Несмотря на то что пузырьковая сортировка не отличается зысокой эффективностью (и в самом деле, его производительность неприемлема для сортировки больших массивов), его вполне успешно можно применять для сортировки массивов малого размера.

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

Код программы который сортирует элементы массива с помощью пузырьковой сортировки.

#include <iostream>
#include <cstdlib>
using namespace std;
int main () {
    int nums[10];
    int a, b, t;
    int size;
    size = 10; // Количество элементов, подлежащих сортировке.
    // Помещаем в массив случайные числа.
    for(t=0; t<size; t++) nums[t] = rand();
    // Отображаем исходный массив
    for(t=0; t<size; t++) cout << nums[t] << '    ';
    cout << '\n';
    // алгоритм реализации пузырьковой сортировки
    for (a=1; a<size; a++){
        for (b=size-1; b>=a; b--){
            if (nums[b-1] > nums[b] ){
                t = nums[b-1];
                nums[b-1]= nums[b];
                nums[b]=t;
            }
        }
    }
    for(t=0; t<size; t++) cout << nums[t] << '    ';
    return 0;
}

Хотя алгоритм пузырьковой сортировки пригоден для небольших массивов, для массивов большого размера он становится неэффективным. Более универсальным считается алгоритм Quicksort. В стандартную библиотеку C++ включена функция qsort (), которая реализует одну из версий этого алгоритма.