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

Цель работы: научиться сортировать данные в массивах методом пузырька.

1. Теоретические сведения:

Рассмотрим простой алгоритм сортировки, называемый пу­зырьковой сортировкой или сортировкой методом обмена. Задача заключается в том, чтобы отсортировать исходный мас­сив целых чисел так, чтобы элементы располагались в нем в по­рядке возрастания. В пузырьковой сортировке последовательно просматриваются пары соседних элементов массива, и если левый элемент пары больше правого, то есть порядок нарушен, то они меняются местами (отсюда происходит название «метод обмена»). В результате самый большой элемент массива оказы­вается на своем законном последнем месте. Он как бы «всплы­вает» наверх подобно пузырькам в стакане газировки, самые большие из которых проталкиваются к поверхности (отсюда второе название метода - пузырьковая сортировка). Для того чтобы все элементы оказались на своих местах, надо проделать процедуру просмотра и обмена элементов несколько раз. Сколь­ко именно, выясним на примере.

Пусть задан антиупорядоченный массив В = (20,10,8,7,5,2), тогда шаги сортировки будут выглядеть следующим образом:

На первом шаге вначале сравниваются 1-й и 2-й элементы массива - 20 и 10. Так как 20 > 10, они меняются местами, в ре­зультате элемент 20 оказывается на 2-м месте. Затем сравнива­ются 2-й и 3-й элементы массива, а именно 20 и 8, и они меня­ются местами. В результате элемент 20 оказывается уже на 3-м месте и т.д. Последними сравниваются 5-й и 6-й элементы массива (на 5-м месте к этому моменту находится 20) и также меняются местами. После выполнения 1-го шага элемент 20 пе­ремещается на последнее место. Запомним, что на первом шаге выполнялось сравнение следующих элементов: 1-го и 2-го, 2-го и 3-го, 3-го и 4-го, 4-го и 5-го, 5-го и 6-го.

На втором шаге все действия первого шага повторяются, но последними сравниваются 4-й и 5-й элементы, т.е. 10 и 2, и они меняются местами: 5-й и 6-й элементы сравнивать не имеет смысла, так как на предыдущем шаге на 6-е место был передви­нут самый большой элемент.

На третьем шаге выполняется сравнение элементов 1-го и 2-го, 2-го и 3-го, 3-го и 4-го, так как 5-й и 6-й элементы уже сто­ят на своих местах.

На четвертом шаге выполняется сравнение элементов только в двух парах, а именно 1-го и 2-го, 2-го и 3-го.

На пятом шаге сравниваются и переставляются первый и второй элементы массива - 5 и 2, остальные элементы, начиная с третьего, уже располагаются в порядке возрастания.

После того как правильно расставлены 5 элементов масси­ва, 6-й (наименьший элемент) «автоматически» оказывается на 1-м месте.

Итак, для сортировки массива из 6 элементов понадобилось выполнить 5 шагов. Легко догадаться, что отсортировать мас­сив, состоящий из п чисел, можно, выполнив п — 1 шагов.

Перейдем к построению алгоритма. Задан массив А[1..n] из п элементов. Обозначим переменной i номер шага выполнения сортировки, а переменной j - номер первого элемента в паре элементов A[j], A[j + 1], которые надо сравнивать.

i = 1: просматриваются пары, в которых номер j изменяется от 1 до п -1 (последними сравниваются элементы, A[n-1],A[n]).

i = 2: просматриваются пары, в которых номер j изменяется от 1 до n-2 (последними сравниваются элементы A[n-2], А[п-1]).

i = 3: просматриваются пары, в которых номер j изменяется от 1 до п — 3 (последними сравниваются элементы A[n —3], А[п-2]).

…

i = n-1: просматриваются пары, в которых номер j изменя­ется от 1 до п - (п -1) = 1 (сравниваются только элементы А [1], A[2]).

Из описанного выше можно сделать следующие выводы:

1. всего выполняется (п —1) шагов, то есть переменная i из­меняется от 1 до (n -1);

2. на i -м шаге просматриваются пары, в которых номеру из­меняется от 1 до (n-1).

Схема алгоритма методома сортировки пузырька представлена на рис. 2.

Рисунок 2. Блок-схема алгоритма сортировки методом пузырька

Реализация алгоритма пузырька для двумерного массива представлена на рис.3.

void bubble_sort(int *a, int length) { for (int j = 0; j < length-1; j++) { for (int i = 0; i < length - j - 1; i++) { if (a[i] > a[i+1]) { int b = a[i]; //change for elements a[i] = a[i+1]; a[i+1] = b; } } } }

Рис.3. Реализация алгоритма на С++

2. Постановка задачи:

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

Массивы сгенероровать с помощью генератора случайных чисел, вывести на печать.