Главная | Обратная связь

Оформить данную сортировку в виде процедуры(функции)

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

Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов.

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

Итак, главной особенностью алгоритма является обмен. Алгоритм основан на сравнении и смене места для 2-х соседних элементов массива. Процесс продолжается до тех пор, пока не будут упорядочены все элементы. Если задан одномерный массив Х из N элементов, то последовательно упорядочиваются например Х₁ и Х_2, Х₃ и Х_4,…, Х_n-1 и Х_n. В итоге максимальное (минимальное) значение переместится в Х_n. Затем эту процедуру повторяют до Х_n-1 и т.д., вплоть до цепочки из двух элементов Х₁ и Х₂.

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

Рассмотрим применение метода на начальном массиве с ключами 44 55 12 42 94 18 6 67. Запишем массив вертикально.

 

I 1 2 3 4 5 6 7 8

1 44 06 06 06 06 06 06 06

2 55 44 12 12 12 12 12 12

3 12 55 44 18 18 18 18 18

4 42 12 55 44 42 42 42 42

5 94 42 18 55 44 44 44 44

6 18 94 42 42 55 55 55 55

7 06 18 94 67 67 67 67 67

8 67 67 67 94 94 94 94 94

Обозначения:

Пузырек в массиве обозначен серым фоном;

Только всплывший пузырек обозначен голубым фоном.

Число сравнений

С=(n^2-n)/2;

число перестановок

M(мин)=0;

M(мах)=3*(n^2-n)/2;

M(ср)=3*(n^2-n)/4;

Представим этот алгоритм в другом изложении:

Пример №1

Сортировка массивов методом выбора (выделения) осуществляется таким образом:

Слева направо поочерёдно сравниваются два соседних элемента, и если их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до конца массива.

После одного такого прохода на последней n-ой позиции массива будет стоять максимальный элемент ("всплыл" первый "пузырёк"). Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до n-1-ого элемента. И так далее. Всего требуется n-1 проход.

Рассмотрим схему алгоритма сортировки методом прямого обмена по неубыванию.

 

Пример №2

 

Пример работы алгоритма

 

Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.

 

 

Первый проход:

 

(5 1 4 2 8) (1 5 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами.

 

(1 5 4 2 8) (1 4 5 2 8), Меняет местами, так как 5 > 4

 

(1 4 5 2 8) (1 4 2 5 8), Меняет местами, так как 5 > 2

 

(1 4 2 5 8) (1 4 2 5 8), Теперь, ввиду того, что элементы стоят на своих местах (8 > 5), алгоритм не меняет их местами.

 

 

Второй проход:

 

(1 4 2 5 8) (1 4 2 5 8)

 

(1 4 2 5 8) (1 2 4 5 8), Меняет местами, так как 4 > 2

 

(1 2 4 5 8) (1 2 4 5 8)

 

(1 2 4 5 8) (1 2 4 5 8)

 

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

 

 

Третий проход:

 

(1 2 4 5 8) (1 2 4 5 8)

 

(1 2 4 5 8) (1 2 4 5 8)

 

(1 2 4 5 8) (1 2 4 5 8)

 

(1 2 4 5 8) (1 2 4 5 8)

 

Теперь массив отсортирован и алгоритм может быть завершён.

 

 

Представлена блок схема сортировки элементов массива

 

 

Нет

 

ДА

 

НЕТ НЕТ

НЕТ

 

Для сдачи зачета по данной сортировки выполнить:

Задание

1. По заданному алгоритму составить программу.
2. Организовать вывод промежуточных значений массива.
3. По программе SORT2 составить алгоритм.
4. Проанализировать работу двух алгоритмов.

Варианты заданий(по журнальному списку)

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

1. Четные элементы;
2. Нечетные элементы;
3. Положительные элементы;
4. Отрицательные элементы;
5. Меньшие заданного значения N;
6. Большие заданного значения N;
7. Кратные трем;
8. Не кратные трем;
9. Четные положительные элементы;
10. Нечетные положительные элементы;
11. Четные отрицательные элементы;
12. Нечетные отрицательные элементы.

Необходимо(Дома):

1. Составить алгоритм.
2. Написать и отладить программу.
3. Описать используемые переменные.

 

В аудитории

оформить данную сортировку в виде процедуры(функции)