Quicksort y no te molestes?

Especialmente al escribir aplicaciones 'estándar' (que no son HPC), ¿considera qué algoritmo de clasificación elegir, o simplemente se conforma con la clasificación rápida (que es lo que la mayoría de las bibliotecas llaman clasificación)? Hasta cierto punto, puede ser rentable en situaciones específicas, pero, por otro lado, la optimización adecuada requiere algo de tiempo para analizar el problema y hacer puntos de referencia.

En general, el uso de los métodos predeterminados a menos que haya una necesidad específica de hacer algo más exótico hace que todo sea mucho más legible / comprensible en el futuro en mi humilde opinión.

Si experimenta (o en algunos casos, sospecha mucho) que tiene un problema de rendimiento, es el momento de agregar complejidad.

Por otro lado, si está utilizando un lenguaje lo suficientemente bajo como para que no haya una clasificación incorporada para el tipo de objetos que necesita clasificar, intente elegir uno o dos que cubran todas sus bases e implemente esas.

Siempre llame a las rutinas de la biblioteca proporcionadas, a menos que tenga muy, muy buenas razones para no hacerlo (y necesita documentar por qué es así).

Esto se debe a que los algoritmos de clasificación son difíciles de acertar. Hubo un error en el ordenamiento rápido de Java con conjuntos de datos muy grandes, que Sun identificó, solucionó y entregó a los clientes, por lo que no tuvo que hacerlo.

Además, la ordenación predeterminada en Java 7 se ha actualizado a una ordenación más nueva y mejor. También gratis.

A menos que el tipo predeterminado no sea lo suficientemente bueno para usted, quédese con él.

En una conferencia una vez escuché una bonita historia sobre esto.

En Microsoft, alguien estaba escribiendo una aplicación VB (c. VB 3) y envió un correo a un grupo de personas diciendo que tenía una gran cantidad de valores y que quería que aparecieran en el cuadro combinado en orden, cómo debería hacerlo.

Todos se lanzaron a buscar sus viejos libros de texto de ciencias de la computación, buscaron rutinas altamente eficientes y las transfirieron a Visual Basic y se las enviaron por correo. Uno de ustedes acaba de enviar "¿cuántos valores en el cuadro combinado?".

"Alrededor de 50" fue la respuesta.

"Simplemente establezca la propiedad ordenada en VERDADERO".

En el 99.9999% de las instancias, la ordenación se realiza mejor usando una biblioteca, control o en la selección SQL, ya que la diferencia de rendimiento entre la rutina de la biblioteca y cualquier cosa que escriba será insignificante y el esfuerzo y la sobrecarga de mantenimiento superarán enormemente las consecuencias.

Este es el momento de sacar la cita clásica sobre la optimización prematura. En la mayoría de los casos, realmente no importa. Demonios, con la velocidad de las CPU en estos días, probablemente podría ordenar en burbuja la mayoría de los conjuntos de datos y realmente no notar mucho. Pero cuando está clasificando conjuntos de datos realmente grandes y el rendimiento de clasificación comienza a convertirse en un problema, entonces definitivamente debería considerar otras opciones.

Aunque, obviamente, no importa a los bits y los segmentos de tiempo. Encuentro que el tipo de fusión es más fácil de escribir y comprender que el de clasificación rápida. Entonces, si voy a escribir mi propio algoritmo de clasificación, lo usaría.

Al menos en una biblioteca escrita de manera competente, esperaría que el incorporado sortse implemente como un Introsort en lugar de solo un Quicksort. La diferencia rara vez importa mucho, pero Introsort elimina el mal desempeño en el peor de los casos de Quicksort con un efecto mínimo en los casos más comunes.

Sin embargo, para responder a su pregunta: sí, eso es con lo que generalmente debe comenzar, y hasta / a menos que tenga resultados de perfil que indiquen que es un problema, ahí es donde debe permanecer.