<< | к задаче | главная | печатать | обсудить(0 сообщений) >>
Задача: Улучшение быстрой сортировки
Исходник: Быстрая сортировка QSort3 (оптимизация №1) [C++, code #15, hits: 9542, рейтинг: 3/7,4.81(3246)] +
автор: this [добавлен: 29.01.2006] управление:
  1. template<class T>
  2. void QSort3(T* x, int l, int u) {
  3. if (l >= u)
  4. return;
  5.  
  6. T t, tmp;
  7. int i,j;
  8. t = x[l]; i = l; j = u+1;
  9.  
  10. while (1) {
  11. /* пропуск элементов справа и слева,
  12. чтобы не делать лишней работы */
  13. do i++; while (i <= u && x[i] < t);
  14. do j--; while (x[j] > t);
  15.  
  16. if (i > j)
  17. break;
  18. // Делаем swap(i, j):
  19. tmp = x[i]; x[i] = x[j]; x[j] = tmp;
  20. }
  21.  
  22. // swap(l, j)
  23. tmp = x[l]; x[l] = x[j]; x[j] = tmp;
  24.  
  25. QSort3(x, l, j-1);
  26. QSort3(x, j+1, u);
  27. }
Быстрая сортировка с двусторонним алгоритмом разбиения.
Индексы i и j инициализируются граничными индексами разбиваемого массива. Главный цикл содержит два вложенных цикла. Первый вложенный цикл сдвигает i вверх, пропуская меньшие элементы, а второй увеличивает j, пропуская большие элементы и останавливаясь на меньшем. Главный цикл проверяет, не пересекаются ли эти индексы, и переставляет соответствующие элементы.
Избавляясь от квадратичного поведения в худшем случае, этот код и в среднем делает меньше обменов, чем qsort1

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

Глубина рекурсии в среднем - (log n)
Производительность, в среднем: ~ O(n*log n), крайний случай: ~ O(n2)
Расход памяти: ~ O(log n)

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