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

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

#Доступ ко всем полям и методам. (58458 hits)
#Как посчитать одинаковые пары за 1 проход (самая быстрая версия!). (2646 hits)
#Рисование 3D объекта. (35575 hits)
#Динамическое изменение цвета полоски прокрутки в IE5.5 и выше. (31362 hits)
#Переворот символов строки (или элементов одномерного массива). (112997 hits)
#Просмотр изображения во всплывающем окне. (89854 hits)
#Рисование Фрактала (листьев папоротника). (53640 hits)
#Сохранение данных формы после перезагрузки через куки. (205769 hits)
#Рисование множества Мандельброта. (44925 hits)
#Перестановка фрагментов строки(или одномерного массива). (61279 hits)
#Поиск дубликатов внутри файла. (31828 hits)
#Сравнение алгоритмов быстрой сортировки. (74391 hits)
#Случайный выбор нескольких несовпадающих значений из множества. (59277 hits)
#Постепенное затемнение. (51758 hits)
#Вращение фигуры в плоскости. (40463 hits)
#Поразрядная сортировка, общий принцип. (131449 hits)
#Предварительная загрузка изображений. (47715 hits)
#Шейкер-сортировка. (71913 hits)
#Поразрядная сортировка массива подсчетом. (133844 hits)
#Заполнение 2-го выпадающего списка (select) в соответствии с выбором в первом. (46770 hits)


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

Шейкер-сортировка

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

Шейкер-сортировка представляет собой дальнейшую и довольно качественную оптимизацию пузырьковой сортировки(без знания которой данная задача останется непонятной).

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

Например, имеем: [7,3,4,6] - после первого прохода получим уже [3,4,6,7] - т.о. 7 пройдя через весь массив встало на свое место уже на первом проходе. Другое дело - маленькие числа в данной ситуации: на каждой итерации они продвигаются к своему месту не больее чем на 1 позицию: [7,6,5,2,1] - после 1-ой итерации имеем [6,5,2,1,7], после 2-ой - [5,2,1,6,7] и т.д.

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

С учетом всего вышесказанного получим:

 псевдокод: Шейкер сортировка  ссылка
  1. left = 1
  2. right = n-1
  3.  
  4. last = n-1
  5.  
  6. /* основной цикл до тех пор пока границы
  7. отсортированных с разных сторон отрезков
  8. не пересекутся */
  9. while left < right
  10. /* проход снизу вверх */
  11. for j = right downto 1
  12. if x[j-1] > x[j]
  13. swap(x, j-1, j)
  14. last = j
  15.  
  16. /* Корректируем нижнюю границу
  17. до которой уже все элементы получились
  18. отсортироваными */
  19. left = last + 1
  20.  
  21. /* проход сверху вниз */
  22. for j = 1 to right
  23. if (x[j-1] > x[j] )
  24. swap(x, j-1, j)
  25. last = j
  26.  
  27. /* Корректируем верхнюю границу
  28. после которой уже все элементы получились
  29. отсортироваными */
  30. right = last - 1
  31.  


Данный сортировка работает быстрее чем пузырьковая, но по-прежнему производительность алгоритма в среднем ~ O(n2), а число обменов вообще не поменялось даже по-сравнению базовой реализацией пузырькового метода. Всеми этими манипуляциями с оптимизацией мы сократили только количество сравнений.

Из преимуществ можно отметить быструю(сравнимую с другими истинно быстрыми алгоритмами) сортировку частично упорядоченного массива.

 

Реализации:

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

1) Шейкер-сортировка на C++, code #25[автор:this]