<< | к задаче | главная | печатать | обсудить(0 сообщений) >>
Задача: Простая быстрая сортировка
Исходник: Быстрая сортировка. Опорный элемент - первый элемент. [C++, code #14, hits: 11415, рейтинг: 3/7,4.87(2768)] +
автор: this [добавлен: 24.01.2006] управление:
  1. template<class T>
  2. void QuickSortLeft(T* x, int l, int u) {
  3. // Отбрасываем пустые и
  4. // одноэлементные массивы
  5. if (l >= u) {
  6. return;
  7. }
  8.  
  9. T tmp;
  10. int m = l;
  11. for (int i = l+1; i <= u; i++) {
  12. if (x[i] < x[l]) {
  13. // делаем swap(++m, i)
  14. tmp = x[++m]; x[m] = x[i]; x[i] = tmp;
  15. }
  16. }
  17.  
  18. // Делаем swap(l, m):
  19. // Без этого - алгоритм может войти
  20. // в бесконечную рекурсию
  21. tmp = x[l]; x[l] = x[m]; x[m] = tmp;
  22.  
  23. // вызываем реккурсивно
  24. // для 2-х полученных областей
  25. QuickSortLeft(x, l, m-1);
  26. QuickSortLeft(x, m+1, u);
  27. }
Перед каждым перераспределением выбирается первый элемент представленной последовательности. В результате чего не тратится время на поиск середины отрезка либо на случайный выбор и проч.
Функцию следует вызвать как QuickSortLeft(arr, 0, n-1).

Глубина рекурсии в среднем - (log n).

Производительность, в среднем: ~ O(n*log n)
Расход памяти: ~ O(log n)

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