CodeLAB
на главную карта сайта обратная связь

Популярные задачи:

#Динамическое изменение цвета полоски прокрутки в IE5.5 и выше. (31826 hits)
#Счетчик времени с точностью до микросекунд. (131257 hits)
#Арктангенс. (46794 hits)
#Сортировка Шелла, оптимальный выбор приращений. (198046 hits)
#Программное создание ссылок. (101052 hits)
#Рисование окружности (по Брезенхэму). (34944 hits)
#Посчитать количество пар чисел (number of equal pairs). (7837 hits)
#сортировка пузырьком. (155032 hits)
#qForms, библиотека типичного функционала валидации/построения/связки html-форм. (149814 hits)
#Динамическое формирование выпадающего списка. (53356 hits)
#Создание нестандартного (custom-ного) окна браузера. (36894 hits)
#Передача данных из основного во всплывающее-popup окно через POST. (119065 hits)
#Пирамидальная сортировка. (208579 hits)
#Рисование линии. (39815 hits)
#Добавление истории операций(undo&redo) в компонент. (41180 hits)
#Загрузчик классов. (44540 hits)
#Переключатель в кириллицу. (33977 hits)
#Преобразование RGB в HEX и обратно HEX в RGB. (58015 hits)
#Код. (183015 hits)
#Плоттеры для рисования графиков. (30545 hits)


Главная >> Каталог задач >> Сортировка >> Пузырьковая сортировка (bubble sort) >> сортировка пузырьком

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

Aвтор:
Дата:
Просмотров: 155031
реализации(C++: 3шт...) +добавить

Очень простой, компактный, но медленный алгоритм сортировки. На каждой итерации мы вытягиваем наименьшие(наибольшие) элементы на свои позиции по некоторой аналогии с всплытием пузырьков на поверхность воды.

На каждой итерации(шаге) сортировки осуществляется проход по неотсотированной части массива и если текущий элемент меньше(при сортировке по-убыванию конечно) следующего - то меняем их местами(swap-им) друг с другом. Таким образом после первой итерации наш наименьший элемент "всплывет": окажется в конце последовательности. Затем такая же процедура, но только уже до предпоследнего элемента: последний-то, наименьший из всех - уже стоит на своем месте. И так до (n-1)-ой итерации, после которой в неотсортированной последовательности окажется 1 элемент, который очевидно будет занимать свое законное место там.

Пример. Пусть имеем последовательность из n=5 элементов: x=[3,7,2,5,6]. Будем сортировать по возрастанию. Получим:

1 шаг: цикл по всем элементам. 3>7? нет. Оставляем как есть. 7>2? да. меняем 7 и 2: [3,2,7,5,6]. 7>5? да. Меняем 7 и 5:[3,2,5,7,6]. Далее. 7>6? Да. Меняем 6 и 7:[3,2,5,6,7].

2 шаг: цикл по всем элементам кроме последнего. Аналогично осуществляя, получим в конце:[2,3,5,6,7].

3 шаг: цикл до 3-го элемента в нашем случае. Перестановок не будет, все остается по-прежнему:[2,3,5,6,7].

4 шаг: цикл до второго элемента. Перестановок тоже не будет.

5 шаг: цикл по одному первому элементу. Он не больше своего соседа(2 < 3), поэтому и здесь перестановок не будет. Т.о. алгоритм завершил свою работу и мы получили отсортированную последовательность: [2,3,5,6,7].

Данный алгоритм имеет вид:

 псевдокод: сортировка пузырьком, версия #1  ссылка
  1. for i = 0 to n-1
  2. j = n-1
  3. while (j > i)
  4. if (x[j-1] > x[j])
  5. swap(x, j-1, j)
  6. j--
  7.  


Улучшения

Приведенный выше пример как раз наводит на мысль о таком улучшении: после 2-го шага мы уже получили отсортированную последовательность, проходы на 3-ем, 4-ом и 5-ом шаге отработали вхолостую, не сделав уже никаких перестановок конечно. Поэтому их следовало бы уже исключить. Правило такое, если на какой-то итерации не было сделано ни одной перестановки - значит этот проход последний и мы уже имеем отсортированную последовательность. Реализовать это очень просто: на каждой итерации помимо всего прочего устанавливаем некоторый флаг при первой сделанной сортировке:

 псевдокод: сортировка пузырьком, добавление признака отсортированности, версия #2  ссылка
  1. for i = 0 to n-1
  2. j = n-1
  3. sorted = true
  4. while (j > i)
  5. if (x[j-1] > x[j])
  6. swap(x, j-1, j)
  7. sorted = false
  8. j--
  9. if sorted
  10. break
  11.  


Анализируя алгоритм дальше можно прийти еще к одному выводу: если на некоторой итерации после определенного индекса(=k например) - перестановок уже не было, то их не будет и на всех следующих итерациях. Возвращаясь к нашему примеру - имеем это на 2-ом шаге: после перестановки 3 и 2, других уже больше не было. Т.е. k = 1 в данном случае. Очевидно, что раз на следующих после k элементах перестановок не было, то они уже расположены в правильном порядке.

Соответственно получим следующий алгоритм:

 псевдокод: сортировка пузырьком, оптимизация #2, версия #3  ссылка
  1. last = -1
  2. for i = 0 to n-1
  3. j = n-1
  4. k = i
  5. if last > 0 && last > i
  6. k = last
  7. while (j > k)
  8. if (x[j-1] > x[j])
  9. swap(x, j-1, j)
  10. last = j
  11. j--
  12. if last == k
  13. break
  14.  


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

Реализации:

C++(3)   +добавить

1) Сортировка пузырьком в чистом виде, без оптимизации, версия #1 на C++, code #26[автор:this]
2) Сортировка пузырьком с признаком отсортированности массива. Версия #2 на C++, code #27[автор:this]
3) Сортировка пузырьком, дальнейшая оптимизация. Версия #3 на C++, code #28[автор:this]