Задача: Простая быстрая сортировка
Исходник: Быстрая сортировка, опорный элемент - первый., язык: C++ [code #14, hits: 17871]
автор: 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)
Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

+добавить реализацию