<< | к задаче | главная | печатать | обсудить(0 сообщений) >>
Задача: Простая быстрая сортировка
Исходник: Быстрая сортировка. Опорный элемент - середина. Неоптимизированная версия [C++, code #13, hits: 11943, рейтинг: 3/5,4.89(2974)] +
автор: - [добавлен: 24.01.2006] управление:
  1. template<class T>
  2. void QuickSortCenter(T* x, long N) {
  3. long i = 0, j = N; // начальные значения
  4. T temp, p;
  5.  
  6. p = x[ N>>1 ]; // выбираем середину
  7.  
  8. // процедура разделения
  9. do {
  10. while (x[i] < p) i++;
  11. while (x[j] > p) j--;
  12.  
  13. if (i <= j) {
  14. temp = x[i]; x[i] = x[j]; x[j] = temp;
  15. i++; j--;
  16. }
  17. } while (i <= j);
  18.  
  19.  
  20. // рекурсивные вызовы, если есть, что сортировать
  21. if ( j > 0 ) QuickSortCenter(x, j);
  22. if ( N > i ) QuickSortCenter(x+i, N-i);
  23. }
Перед каждым перераспределением выбирается элемент, находящийся в центре последовательности.
Обратите внимание на рекурсивный вызов в строке 22:

QuickSortCenter(<b>x+i</b>, N-i);

Это означает сдвинутый указатель на массив. Т.е. получим указатель на массив, который начинается с i-го элемента первоначального массива x. То, что и требуется.

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

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

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