Программа пузырьковой сортировки

Часто требуется расположить элементы массива по возрастанию или по убыванию. Это можно сделать с помощью следующей программы:

const int N=5;

int i,j,t,massiv[N];

cout<<RUS("Введите одномерный массив целых чисел:\n");

for(i=0;i<N;i++)cin>>massiv[i];      //ввод массива

  for(i=N-1;i>0;i--)         //начало сортировки

        for(j=0;j<i;j++)

          if(massiv[j]>massiv[j+1])

          {

            t=massiv[j];                //тело внутреннего цикла

            massiv[j]=massiv[j+1];        //

            massiv[j+1]=t;            //

          }       //конец сортировки

cout<<RUS("\nМассив упорядоченный по возрастанию:\n");

for(i=0;i<N;i++)  //вывод массива

cout<<"\nmassiv["<<i<<"] = "<<massiv[i];       //вывод массива

Собственно алгоритм выделен комментариями "начало сортировки" и "конец сортировки". Его суть заключается в последовательной перестановке соседних элементов массива с целью продвижения самого большого элемента в конец массива. Этот процесс поясняется на рис. 1.1. Один проход внутреннего цикла for …(по переменной j) перемещает в конец 1 элемент. На следующем проходе, благодаря уменьшению на 1 переменной внешнего цикла (i), установленный в конце массива элемент уже не рассматривается. Его рассмотрение не изменило бы результата, но выполнение операций требует времени, которое тратить впустую нецелесообразно. Так после выполнения N-2 внутренних циклов массив будет упорядочен по возрастанию.

Тело внутреннего цикла алгоритма решает задачу взаимной перестановки двух элементов массива. Задача решается перемещением значения переменных через третью вспомогательную переменную (t).

Рис. 1.1

Перемещение самого большого элемента по массиву подобно всплытию пузырька воздуха в воде. Это и определило название алгоритма.

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