Templated Quick/Merge Sort

Question

Я пытаюсь написать шаблонную функцию на C++, которая может принимать массив любого типа и сортировать его. Используемая сортировка должна быть быстрой сортировкой или сортировкой слияния, но у меня возникли проблемы с реализацией любого из них, так как быстрый заголовок сортировки обычно имеет верхний и нижний параметр, а сортировка слияния - с первый и последний параметр. Мой заголовок функции выглядит следующим образом: недействительный mySort (T * массив, Int N)

До сих пор у меня есть это:

template <typename T> 
void sort(T *a, int n) 
{ 
    int i = 0; 
    int j = n-1; 
    int tmp; 
    int pivot = a[(n-1)/2]; 
    while (i <= j){ 
    while (a[i] < pivot) 
     i++; 
    while (a[j] > pivot) 
     j--; 
    if (i<=j){ 
     tmp = a[i]; 
     a[i] = a[j]; 
     a[j] = a[i]; 
     i++; 
     j--; 
    } 
    } 

    if(0<j) 
    sort(a, j); 
    /* 
    if(i<right) 
    sort(
    */ 
} 

Я пытался использовать рекурсивный вызов для сортировки, но я не мог выяснить, как вызвать рекурсивный для созданного правого раздела, без другого списка параметров.

Answer 1

Прежде чем отвечать на реальный вопрос: ваш код выиграет от факторинга кода раздела из тела функции! Таким образом, вы бы по существу назвать раздел, чтобы определить среднюю точку между двумя массивами можно назвать, например, вы бы что-то вроде этого:

template <typename T> 
void sort(T* a, int n) { 
    T* mid = partition(a, n); 
    // ... 
} 

Идея заключается в том, что [a, mid) содержит все элементы сортировки меньше чем точка поворота, а [mid, a + n) содержит все элементы, которые сортируются равными или большими, чем точка поворота. Все, что остается

1. Вызов sort() рекурсивно с двумя массива, т.е.

   sort(a, mid - a); 
   sort(mid, (a + n) - mid); 
   

2. Убедитесь sort() заканчивается, если массив получается мало чем 2.

Of Конечно, если вы хотите, чтобы ваш Быстрый Сортировка был быстро, вам также понадобится вытащить полдюжины или около того трюков. Как:

1. Используйте Introsort, чтобы гарантировать сложность является O(n lg n) (например, вместе с Merge Sort).
2. Использование Вставка Сортировка по небольшим диапазонам.
3. Используйте реализацию разделения разделов и вставок, используя подходящие стражи.
4. Сортировать действительно сортировать диапазоны напрямую.

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

Answer 2

Отдельные вызываемая функция из рекурсивной функции:

// recursive function 
template <typename T> 
void quicksort(T *a, int lo, int hi) 
{ 
    // ... 
} 

// called function  
template <typename T> 
void sort(T *a, int n) 
{ 
    if(n < 2)return; 
    quicksort(a, 0, n-1); 
}