¿Qué es el ordenamiento binario?

Los ordenamientos binarios son una clase de algoritmo en el que el contenido de una estructura de datos (matriz, lista, árbol …) se clasifica por mitades progresivas (o al menos 2 divisiones de la etapa anterior que no son necesariamente de igual tamaño). Con cada comparación sucesiva del elemento que se mueve, una mitad adicional de la mitad actual se elimina de otras comparaciones, hasta que se encuentre la nueva posición para el elemento que se está ordenando.

Como puede imaginar, con una mitad completa (o al menos una división) de la división actual que se descarta en cada comparación, el orden puede ir muy rápidamente.

Esta descripción asume que la estructura a ordenar ya existe, con su contenido aún sin clasificar. También se puede realizar una búsqueda binaria agregando elementos sucesivos en un árbol binario ordenado, donde en cada comparación se agrega el elemento como una nueva hoja o se limita la búsqueda de dónde pertenece al subárbol izquierdo o derecho del subárbol actual comparación. Con el árbol comenzando vacío, nuevamente, esto obviamente puede ir muy rápido.

(Un “tipo de montón” es un caso refinado de esto, donde un montón no es una herramienta de asignación de memoria, sino un árbol binario que cumple condiciones muy particulares).

Digo que puede ir en cada caso porque cada tipo y búsqueda tiene sus peores condiciones. Por ejemplo, si sucede que la secuencia de elementos que se ordenan (o agregan) ya está bastante bien en el orden ordenado, la secuencia de divisiones se inclinará fuertemente a un extremo de la estructura (o al lado del árbol) y la clasificación se se vuelve bastante lineal.

No recuerdo si “clasificación rápida” y “clasificación de torneo” se consideran generalmente tipos binarios. Quicksort va por divisiones binarias de la estructura de datos (es decir, dividiéndola en dos) pero no vuelve a insertar elementos individuales, sino que simplemente cambia los elementos en la división actual para asegurarse de que cada elemento que comienza desde su extremo izquierdo menos que cada elemento comenzando desde su extremo derecho (quicksort lo llama “partición”) luego divide donde se encuentran las particiones y da cada una de las divisiones recursivamente a quicksort Esto resulta para eliminar cargas de comparaciones redundantes, y en todo, pero en el peor de los casos, va increíblemente rápido.

(Pido disculpas a los algoritmos de las personas por usar “muy rápido” y “increíblemente rápido” en lugar de la notación O, pero mi impresión es que la pregunta está en un nivel más general que eso).