“Hay dos formas de construir un diseño de software: una es hacerla tan simple que obviamente no haya deficiencias, y la otra es hacerla tan complicada que no haya deficiencias obvias “.
– Tony Hoare (Sir Charles Antony Richard Hoare) , científico informático británico que recibió el Premio ACM Turing por “sus contribuciones fundamentales a la definición y diseño de lenguajes de programación” y conocido por los estudiantes de informática como el inventor de “Quicksort” , un mecanismo de clasificación eficiente.
Bueno, aquí tienes dos respuestas: una, qué hace el software, y la otra, una de las personalidades verdaderamente icónicas del desarrollo de software.
- ¿Qué características tendría una ciudad digital dentro de cinco años?
- La industria automotriz actual ha sido tecnológicamente revolucionada. ¿Por qué los sistemas de audio en el automóvil están desactualizados (en existencia) o son exorbitantemente caros?
- ¿Cuál es la dificultad de utilizar tecnológicamente el CO2 en nuestro aire para uso práctico?
- Cómo usar Internet sabiamente
- ¿Por qué la tecnología se centraliza en ciudades caras?
Ordenación rápida
Historia
Mientras estudiaba en la Universidad Estatal de Moscú, Tony Hoare recibió una oferta de empleo del Laboratorio Nacional de Física (NPL) para trabajar en un nuevo proyecto de traducción automática del ruso al inglés. Sin embargo, debido a que los diccionarios se almacenaron en una cinta magnética, habría tenido que ordenar las palabras de una oración en orden alfabético antes de la traducción.
Hoare pensó en dos métodos para resolver este problema. El primer método habría tomado una cantidad de tiempo proporcional al cuadrado de la longitud de la oración. El segundo método se manifestaría más tarde como clasificación rápida. En ese momento, él solo sabía un idioma, Mercury Autocode. Desafortunadamente, no pudo codificar con éxito QuickSort utilizando Mercury Autocode.
En 1961, Hoare asistió a una clase Algol 60 en Brighton. Algol 60 permitió la recursividad (la capacidad de un procedimiento para llamarse a sí mismo). Durante este curso, Hoare programó un algoritmo de clasificación ultrarrápido ahora conocido como quicksort . Su primer artículo sobre quicksort también se publicó en 1961, con otro siguiente en 1962.
El algoritmo
Se han realizado algunas modificaciones a quicksort desde su desarrollo. Sin embargo, el algoritmo básico funciona de la siguiente manera:
- Elija un elemento en la lista: este elemento sirve como pivote. Déjalo a un lado (por ejemplo, muévelo al principio o al final).
- Particione la matriz de elementos en dos conjuntos: aquellos menores que el pivote y aquellos mayores que el pivote (nota: menor que y mayor se refiere a enteros, pero quicksort también se puede usar para ordenar otros tipos de elementos como cadenas).
- Repita los pasos 1 y 2 en cada una de las dos particiones resultantes hasta que cada conjunto tenga uno o menos elementos.
Clasificación
Quicksort es un algoritmo de clasificación de divide y vencerás , es decir, toma un problema de clasificación y lo divide en subproblemas, que a su vez se dividen en más subproblemas. Esto se logra mediante la programación recursiva , donde un procedimiento se llama a sí mismo.
Usos ideales
Cuando un conjunto de datos ya está ordenado y se selecciona el primer o el último elemento como pivote, ocurre el peor de los casos de O (n ^ 2). Por lo tanto, si uno necesita un rendimiento garantizado, la selección rápida puede no ser la mejor opción. Sin embargo, la probabilidad de que ocurra O (n ^ 2) es muy rara. El caso del tiempo cuadrático generalmente resulta de una mala elección de pivote.
Sin embargo, debido a esta limitación, quicksort no debe usarse en aplicaciones que requieren un tiempo de respuesta garantizado, como en situaciones críticas para la vida y la misión.
Quicksort es ideal para usar con grandes conjuntos de datos y / o cuando la memoria está limitada. En general, las aplicaciones comerciales usan QuickSort porque es rápido y no requiere mucha memoria adicional.
