STL __merge_without_buffer algoritmo?

Question

¿Dónde puedo obtener una descripción decente de alto nivel del algoritmo utilizado en __merge_without_buffer () en C ++ STL? Estoy tratando de volver a implementar este código en el lenguaje de programación D, con algunas mejoras. Parece que no puedo entender lo que está haciendo a nivel algorítmico con solo leer el código fuente STL porque hay demasiados detalles de bajo nivel que lo ocultan. Además, no quiero traducir el código a ciegas porque, si no funcionara, no sabría por qué y no podría agregar mis mejoras.

Answer 1

__merge_without_buffer () está realizando una fusión in situ , como el paso de fusión de una ordenación de fusión in situ. Toma como entrada dos rangos de datos [first, middle) y [middle, last) que se supone que ya están ordenados. Los parámetros len1 y len2 son iguales a las longitudes de los dos rangos de entrada, a saber, (medio - primero) y (último - medio) respectivamente.

Primero, selecciona un elemento pivot . Luego, reorganiza los datos en el orden A1 B1 A2 B2 , donde A1 es el conjunto de elementos en [first, middle) que son menor que el pivote, A2 es el conjunto de elementos en [first, middle) mayor o igual que el pivote, B1 es el conjunto de elementos en [middle, last) menos que el pivote, y B2 es el conjunto de elementos en [middle, last) mayor que o igual al pivote. Tenga en cuenta que los datos están originalmente en el orden A1 A2 B1 B2 , por lo que todo lo que tenemos que hacer es convertir A2 B1 en B1 A2 . Esto es con una llamada a std :: rotate () , que hace exactamente eso.

Ahora hemos separado los elementos que son menores que el pivote ( A1 y B1 ) de aquellos que son mayores o iguales al pivote ( A2 y B2 ), por lo que ahora podemos fusionar recursivamente los dos subranges A1 A2 y B1 B2 .

¿Cómo elegimos un pivote? En la implementación que estoy viendo, elige el elemento mediano del subrango más grande (es decir, si [first, middle) tiene más elementos que [middle, last) , elige la mediana de [first, middle) ; de lo contrario, elige la mediana de [middle, last) ). Como las subranjas ya están ordenadas, elegir la mediana es trivial. Esta opción de pivote asegura que al fusionar recursivamente los dos subrangos, cada subproblema no tenga más de 3/4 del tamaño del problema actual, porque en el peor de los casos, al menos 1/4 de los elementos son más grandes o más pequeños que el pivote. .

¿Cuál es el tiempo de ejecución de esto? La llamada std :: rotate () toma tiempo O (N), y hacemos dos llamadas recursivas para nosotros. Esto equivale a un tiempo de ejecución de O (N log N). Sin embargo, tenga en cuenta que este es solo un paso en mergesort: recuerde que en mergesort primero ordena recursivamente ambas mitades y luego combina. Por lo tanto, la relación de recurrencia para el tiempo de ejecución de mergesort es ahora:

T (N) = 2T (N / 2) + O (N log N)

Conecte esto al Teorema maestro , y obtendrá ese mergesort ahora se ejecuta en O (N log ² N) time!

Como un punto final interesante, considere las siguientes tres cualidades de un algoritmo de clasificación basado en comparación:

1. en el lugar
2. Estable
3. Se ejecuta en tiempo O (N log N)

Por lo general, solo puede obtener 2 de estos a la vez: quicksort obtiene (1) y (3), mergesort obtiene (2) y (3), y un mergesort en el lugar obtiene (1) y (2) ) Las clasificaciones no basadas en la comparación, como la clasificación por conteo, pueden alcanzar los 3, pero esas clasificaciones solo pueden clasificar ciertos tipos de datos. Es posible que exista un tipo basado en la comparación que logre los 3, pero si lo hay, no estoy al tanto de su existencia, y es casi seguro que sea mucho más complicado.