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

 

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

 

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).

j:

 

j: 10

1

t

t

 

Рис. 1.1

 

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

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