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

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

//Пузырьковая сортировка или сортировка погружением.

#include <iostream>

using namespace std;

int main()
{

    const int arraysize = 10;
    int array[arraysize] = {7, 12, 100, 1, 78, 1234, 3, 18900, 512, 5021};
    int hold;

    //выводим на экран исходный неотсортированный массив
    for (int i = 0; i < arraysize; i++)

        cout << array[i] << "; ";

    cout << endl << endl;

    for (int j = 1; j < arraysize; j++)

        for (int k = 0; k < arraysize - 1; k++)

            if (array[k] > array[k + 1])
            {

                hold = array[k];
                array[k] = array[k + 1];
                array[k + 1] = hold;

            }

    //выводим на экран отсортированный массив
    for (int l = 0; l < arraysize; l++)

        cout << array[l] << "; ";

    cout << endl << endl;

    return 0;

}

Результат работы программы:

Разберем код программы.

Для демонстрации работы алгоритма пузырьковой сортировки нам понадобятся две переменные: массив целых чисел и переменная целого типа, с помощью которой мы будем обменивать местами значения элементов массива. Массив инициализируем произвольными значениями целого типа в количестве десяти штук. Этого будет вполне достаточно для демонстрации данного алгоритма. Выводим на экран исходный неотсортированный массив:

for (int i = 0; i < arraysize; i++)

    cout << array[i] << "; ";

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

hold = array[k];
array[k] = array[k + 1];
array[k + 1] = hold;

Как вы понимаете, сразу присвоить так

array[k] = array[k + 1];
array[k + 1] =array[k];

нельзя, иначе будет потеряно предыдущее значение в ячейке array[k]. Для временного хранения этого значения используем переменную hold.

Сначала программа сравнивает array[0] с array[1], затем array[1] c array[2], ..., array[8] c array[9]. Всего в общем счете происходит девять сравнений, т.к. элементов десять. За сравнение элементов у нас отвечает внутренний цикл for

for (int j = 1; j < arraysize; j++)

    for (int k = 0; k < arraysize - 1; k++)

        if (array[k] > array[k + 1])
        {

            hold = array[k];
            array[k] = array[k + 1];
            array[k + 1] = hold;

        }

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

for (int j = 1; j < arraysize; j++)

   for (int k = 0; k < arraysize - 1; k++)

       if (array[k] > array[k + 1])
       {

           hold = array[k];
           array[k] = array[k + 1];
           array[k + 1] = hold;

       }

Если просматривать содержимое массива после каждого внешнего цикла, то можно увидеть следующее:

В самом верху расположен исходный массив, а ниже мы видим наш массив после каждой итерации внешнего цикла.

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

Вы, наверное, заметили из предыдущего рисунка, что последние несколько строчек одинаковы, т.е. сортироовка выполнятеся все еще тогда, когда массив по сути уже отсортирован. То же можно наблюдать и во внутреннем цикле (вы можете поэксперементировать, вставив код вывода массива на экран в нужный цикл). Конечно же эти все моменты можно исправить и усовершенствовать алгоритм пузырьковой сортировки, соответственно повлиять на скорость выполнения. Предыдущая версия программы была представлена больше как пример, т.к. она проще для понимания, а сейчас будет представлена улучшенная версия пузырьковой сортировки:

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

#include <iostream>
#include <iomanip>

void printArray(int[], int); //прототип функции для вывода массива на печать

using namespace std;

int main()
{

    const int size = 25;
    int array[size] = {34,56,15,31,78,
    45,91,12,1,4,
    7,89,23,47,2,
    21,25,67,68,79,
    73,27,93,22,0};
    int temp;

    cout << " No sorted a array" << endl << endl;
    printArray(array, size);

    for (int i = 1; i < size; i++) //цикл проходов
    {

        int label = 0; //обнуляется при каждом входе в цикл проходов
        for (int j = 0; j < size - i; j++) //количество сравнений сокращается при уменьшении количества проходов
        {

            if (array[j] > array[j + 1])
            {

                temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
                label++;

            }

        }
        if (label == 0) //если в массиве уже сортировать нечего, то выходим из цикла

            i = size - 1;

    }

    cout << " The sorted a array" << endl << endl;
    printArray(array, size);

    return 0;

}

void printArray(int a[], int sizeOfArray) //печать массива
{

    for (int k = 0; k < sizeOfArray; k++)
    {

        cout << setw(4) << a[k];
        if ((k + 1) % 5 == 0)

            cout << endl;

    }
    cout << endl << endl;

}

Для примера был взят массив целых цисел, состоящий из 25 элементов. В начале и в конце программы мы выводим наш массив на экран с помощью функции printArray. Теперь давайте разберем непосредственно сам алгоритм сортировки.

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

Учтем еще такой момент, что данные в массиве уже могут находиться в необходимом порядке, либо близком к нему, поэтому нет необходимости делать все девять проходов. Программа после каждого прохода проверяет, были ли сделаны какие-либо изменения (перестановки), если не было, то значит, что сортировать уже нечего - выходим из цикла, т.к. массив отсортирован. Если изменения были сделаны, то, как минимум, нужно совершить еще один проход. Для этой цели в программу добавлена переменная label, которая перед каждым входом во внутренний цикл сравнений обнуляется, а в цикле увеличивается ее значение на один с помощью операции инкремента (++). В случае, если эта переменная не увеличила свое значение, а это произойдет в случае, если мы не производили перестановок в блоке if, мы выходим из цикла.

Произведя вот такие изменения мы добились повышения производительноси пузырькового алгоримтма сортировки.

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

//Пузырьковая сортировка двумерного массива

#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <time.h>

void printMatrix(int[][12], const int);

using namespace std;

int main()
{
    const int SIZE = 12;
    int matrix[SIZE][SIZE];
    int temp;
    srand(time(NULL));
   
    //заполняем массив случайным образом
    for(int i = 0; i < SIZE; i++)
        for(int j = 0; j < SIZE; j++)
             matrix[i][j] = 1 + rand() % 1000;
         
    //сортируем пузырьком
    for(int N = 1; N < SIZE * SIZE; N++)
    {
       for(int i = 0; i < SIZE; i++)
       {
            for(int j = 0; j < SIZE - 1; j++)
            {
                if(matrix[i][j + 1] < matrix[i][j])
                {
                   temp = matrix[i][j + 1];
                   matrix[i][j + 1] = matrix[i][j];
                   matrix[i][j] = temp;
                }
            }
            
            //сравниваем последний элемент текущей строки
            //с перым элементом следующей
            if(matrix[i + 1][0] < matrix[i][SIZE - 1])
            {
                temp = matrix[i + 1][0];
                matrix[i + 1][0] = matrix[i][SIZE - 1];
                matrix[i][SIZE - 1] = temp;
            }
        }
    }
   
    printMatrix(matrix, SIZE);
    
    return 0;
}

//печать массива
void printMatrix(int mx[][12], const int SIZE)
{
    for(int i = 0; i < SIZE; i++)
    {
        cout << endl;
        
        for(int j = 0; j < SIZE; j++)
            cout << setw(4) << mx[i][j];
            
        cout << endl;
    }
}