¿Qué otros algoritmos de clasificación utilizan la estrategia ‘Divide y vencerás’ además de la clasificación rápida y la combinación?

La ordenación bitónica es un buen ejemplo. Su enfoque es similar al de Merge en el sentido de que divide la lista en sublistas progresivamente más pequeñas, pero es lo suficientemente diferente como para que califique: en lugar de fusionar al comparar los “encabezados” de las sublistas, un clasificador bitónico compara elementos según un patrón fijo

También mencionaré que Timsort e Introsort usan divide y vencerás, pero son tipos híbridos basados ​​en la combinación de clasificación y clasificación rápida, respectivamente.

Cualquier método de clasificación [math] O (n {\ rm lg} n) [/ math] se dividirá para conquistar de alguna manera. La diferencia está en cómo se divide el conjunto de trabajo y el momento del paso “conquistar”.

– dividir primero en conjuntos de trabajo independientes, luego conquistar: combinar fusión

– dividir por particionamiento basado en la comparación con un elemento establecido: clasificación rápida (no es necesario fusionar al final; muy rápido siempre que el intercambio de elementos sea confiablemente rápido)

– dividir mediante particiones usando algunos límites exógenos: clasificación de radix

– dividir de acuerdo con los dígitos iniciales de (la representación binaria de) el índice: clasificación de montón

Dos variaciones de clasificación de fusión y clasificación rápida también utilizan la estrategia de D&C:

Tipo de fusión externa

QuickSort híbrido