Estoy tratando de convertir mi implementación de quicksort en una plantilla que se puede usar con otros contenedores además de un vector.¿Cómo se encuentra el iterador en el medio de dos iteradores?
Originalmente usé índices para encontrar el índice medio, p. (first + last)/2. ¿Cómo puedo encontrar el medio de dos iteradores?
std::distance puede medir la distancia entre dos iteradores de la manera más eficiente posible.
std::advance puede incrementar un iterador de la manera más eficiente posible.
Todavía no me gustaría QuickSort una lista enlazada, aunque el uso :)
¿Por qué no quicksort una lista vinculada? No es necesario encontrar el medio para quicksort ... –
@DietrichEpp: Es cierto, pero hay un motivo por el que 'std :: sort' requiere específicamente iteradores de acceso aleatorio. –
Estoy seguro de que hay una razón técnica, pero no tiene nada que ver con el algoritmo. Es fácil ordenar una lista vinculada. –
¿Qué tal algo como esto?
bool isMovingFirst = true;
while(first != last) {
if(isMovingFirst) {
++first;
} else {
--last;
}
isMovingFirst = !isMovingFirst;
}
En general, se considera mala forma de volver a implementar las cosas que están en las bibliotecas estándar. No te repitas y todo. – StilesCrisis
Oh, estoy de acuerdo con eso por completo. Solo lo escribí porque funciona en la misma cantidad de pasos que la distancia (sin avance de llamada). * Pero * entonces la distancia + avance sigue siendo de bajo costo en relación con la complejidad de tiempo de O (n log n) de quicksort, por lo que definitivamente veo su punto como válido en este caso. –
Bueno, si vamos por eficiencia, tienes un bool extra que no necesitas ... prueba esto en su lugar: para (;;) { if (first == last) descanso; ++ primero; if (first == last) break; --último; } – StilesCrisis
Para encontrar iterador medio se debe utilizar:
first + (last - first)/2
Esto no es correcto. Su solución requiere iteradores de acceso aleatorio. OP pidió una solución que sería independiente del contenedor. –
Por cierto, ¿por qué poner en práctica su propia clasificación rápida? std :: sort debe cubrir el quicksorting, y también hay stable_sort, partial_sort_copy, etc. – StilesCrisis
Estoy haciendo el proyecto Euler y quería investigar algunos algoritmos de clasificación, aunque si planeo volver a usarlo en el futuro, tienes razón-- También podría usar std :: sort. – Louis