<< | к задаче | главная | печатать | обсудить(0 сообщений) >>
Задача: сортировка пузырьком
Исходник: Сортировка пузырьком, дальнейшая оптимизация. Версия #3 [C++, code #28, hits: 17392, рейтинг: 3/7,4.9(2635)] +
автор: this [добавлен: 02.02.2006] управление:
  1. template<class T>
  2. void swap(T* x, int i, int j) {
  3. T tmp;
  4. tmp = x[i]; x[i] = x[j]; x[j] = tmp;
  5. }
  6.  
  7. template<class T>
  8. void BubbleSort3(T* x) {
  9. int last = -1;
  10. for (int i = 0; i < n; i++) {
  11. int k = i;
  12. if (last > 0 && last > i) {
  13. k = last;
  14. }
  15. for (int j = n-1; j > k; j-- ) {
  16. if (x[j-1] > x[j]) {
  17. swap(x, j-1, j);
  18. last = j;
  19. }
  20. }
  21. if (last == k) break;
  22. }
  23. }
Добавляется отслеживание окончательно отсортированного отрезка исходного массива, чтобы в пустую уже не делать по нему сравнений. Такой отрезок может появляться с того края последовательности, в направлении которого мы проходимся по массиву в пределах каждой главной итерации.
Следует отметить, что даже при такой оптимизации, количество перестановок элементов не уменьшается даже по сравнению с базовой версией. Всей этой оптимизацией мы уменьшили только количество сравнений между элементами.

Производительность: ~ O(n2)
Расход памяти: - (только пара счетчиков цикла и вызов swap-а)

+добавить реализацию
 
каталог | задачи | паттерны | исходники | стат | форумы | карта сайта | контакты | ссылки 
© 2000-2017 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.004848 секунд
Количество запросов к БД: 9, gzip: 3.3kb/9.5kb(66%)