CodeLAB
на главную карта сайта обратная связь
каталог | задачи | паттерны | исходники | стат | форумы | ссылки
 гость
искать в
Главная >> Каталог задач >> Сортировка >> пузырьком >> сортировка пузырьком

<< назад
распечатать обсудить >>


сортировка пузырьком
реализации: C++, количество: 3

Aвтор: this
Дата: 27.12.2002
Просмотров: 87348
Рейтинг: 3/7,4.92(3106)
+
реализации(исходники) +добавить

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

На каждой итерации(шаге) сортировки осуществляется проход по неотсотированной части массива и если текущий элемент меньше(при сортировке по-убыванию конечно) следующего - то меняем их местами(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), asm(1)   +добавить реализацию

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


<< назад наверх
распечатать обсудить >>

 
каталог | задачи | паттерны | исходники | стат | форумы | карта сайта | контакты | ссылки 
© 2000-2017 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.013736 секунд
Количество запросов к БД: 14, gzip: 12.0kb/53.2kb(78%)