Ordenando por el placer - Quicksort

Question

Tenemos que hacer un quicksort optimizado para nuestra propia clase base Comparable. Por mi vida no puedo hacer que funcione. El algoritmo parece sencillo, sin embargo, no puedo ver que mi código funcione. Tengo una clase DateTime que amplía Comparable que estoy usando para probar y parece que el orden funciona, pero una de cada 20 ejecuciones un solo valor está fuera de lugar y cuando uso la ordenación de inserción en trozos de la matriz que son menos de 8 todo el género queda fuera de sintonía.

En mi método de partición, funciona cuando muevo el pivote hasta el final y comienzo mis punteros al principio y al final - 1. Quiero mover el pivote al final - 1 porque el primero y el último ya están clasificados e inicie los punteros al principio + 1 y al final -2 pero todo se derrumba si intento eso y no entiendo por qué.

Así que tengo algo que funciona ahora. Se pone un poco espástico cuando no utilizo la ordenación de inserción en matrices secundarias más pequeñas, lo que me molesta, pero estoy enfermo. Gracias a ben j por señalar la caída del array ... que estaba causando el problema de inserción. :)

Mi código actual está por debajo

Comparable** partition(Comparable** from, Comparable** to) 
{ 
    Comparable** pivot = from + (to - from)/2; 
    SortFirstMiddleLast(from, pivot, to - 1); 
    swap(*pivot, *to); 
    pivot = to; 
    ++from; to -= 2; 
    while (from <= to) 
    { 
     while (**from <= **pivot && from <= to) ++from; 
     while (**to >= **pivot && from <= to) --to; 
     if (from < to) 
     { 
      swap(*from, *to); 
      ++from; --to; 
     } 
    } 
    swap(*from, *pivot); 
    return from; 
} 

Answer 1

Desde el código que nosotros y su comentario acerca de lo que va mal mi única suposición es que from y to no quieren decir lo que piensa has mostrado. Su código tiene to - from como la longitud del segmento para ordenar. Si eso es exacto (y no solo aproximado para la selección del pivote) eso significaría que to apuntaba a un elemento que estaba más allá de la región para ordenar. Eso es razonable, pero luego swap<Comparable*>(*pivot, *(to)) estaría intercambiando el pivote del final de la lista.