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

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

#Сравнение алгоритмов сортировки массива. (182120 hits)
#Рисование Фрактала (листьев папоротника). (53157 hits)
#Динамическое изменение цвета полоски прокрутки в IE5.5 и выше. (30927 hits)
#Сортировка Шелла, обший принцип. (145033 hits)
#Часики на js. (92938 hits)
#Улучшение быстрой сортировки. (76905 hits)
#Шейкер-сортировка. (71197 hits)
#Сортировка выбором, общий подход. (72847 hits)
#Вычисление эксцесса и коэффициентов асимметрии заданной выборки. (45811 hits)
#Программное создание ссылок. (99854 hits)
#Рисование прямоугольника. (31301 hits)
#Вычисление двойного интеграла с использованием MPI. (60332 hits)
#Сглаживание кривой В-сплайном. (38770 hits)
#Вставка новой записи в таблицу БД. (36576 hits)
#Преобразование сумм из цифрового представления в строковое. (175687 hits)
#Заливка замкнутой области. (62459 hits)
#Создание простейшей таблицы. (37130 hits)
#Рисование тора. (34735 hits)
#Использование компилируемых (prepared) запросов. (30661 hits)
#Вычисление медианы заданной выборки. (49212 hits)


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

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

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