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

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

#Подсветка синтаксиса. (29376 hits)
#Случайный выбор нескольких несовпадающих значений из множества. (55503 hits)
#Рисование куба. (56314 hits)
#"C# и платформа .NET" Эндрю Троелсен (Andrew Troelsen, "C# and the .NET platform"), листинги, код, примеры из книги, исходники. (36143 hits)
#сортировка пузырьком. (148494 hits)
#Выборка конкретной записи из таблицы. (29893 hits)
#Вычисление среднего, среднего отклонения, среднеквадратического отклонения и дисперсии заданной выборки. (43985 hits)
#Доступ ко всем полям и методам. (55083 hits)
#Перестановка фрагментов строки(или одномерного массива). (57479 hits)
#Рисование прямоугольника. (28714 hits)
#Вычисление минимального / максимального значения. (71364 hits)
#Вращение 3D объекта. (33476 hits)
#Поразрядная сортировка, общий принцип. (124003 hits)
#Рисование Фрактала (листьев папоротника). (50108 hits)
#Хранение иерархических деревьев. (50995 hits)
#Утилиты. (110292 hits)
#Работа с камерой. (33321 hits)
#Рисование множества Мандельброта. (41393 hits)
#Арктангенс. (43195 hits)
#Простая геометрическая и текстовая анимация. (398629 hits)


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

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

Aвтор:
Дата:
Просмотров: 148493
реализации(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]