¿Debería usar la función de clasificación () incorporada de C ++ para problemas en la programación competitiva, o debería implementar el algoritmo por mi cuenta?

Depende de la etapa en la que te encuentres. Si acaba de comenzar, mientras practica, definitivamente debe implementar sus propias funciones de clasificación, de hecho, la mayoría de las funciones disponibles como montón, cola, pila, conjunto, etc. (Me mantendría alejado de los mapas, ya que son bastante tediosos para codificar , pero si quieres probar, entonces bien y bien.)

Ahora, en el momento de los concursos, tiene limitaciones de tiempo, por lo que sería mejor que use la función de clasificación incorporada, ya que están libres de errores y son genéricos. También recomendaría practicar preguntas con funciones incorporadas. Por qué ? Suponga que tiene un contenedor con un número entero, un carácter o incluso un vector y tiene un pedido personalizado para el contenedor, luego implementar la función de clasificación usted mismo consumiría mucho tiempo. El uso de std :: sort () le ahorraría mucho tiempo. Entonces, el motivo principal de los concursos de duración determinada es implementar la solución lo más rápido posible.

TL; DR: Sugeriría leer e implementar varios conceptos y no solo los de clasificación e intentar implementarlos usted mismo para obtener conocimiento y comprensión profunda, pero no en concursos, use funciones incorporadas siempre que sea posible.

Nota: Hay casos raros en los que las funciones de biblioteca incorporadas y las estructuras de datos fallarían en el límite de tiempo (ya que son genéricas y requieren muchas comprobaciones de restricciones), en ese caso debe saber cómo implementarlas.

Gracias por A2A.

Aquí hay algunas cosas que se supone que son muy buenas lo suficientemente rápido en programación competitiva:

(i) Velocidad de ejecución:

Según yo, es muy difícil escribir un código de sort () más rápido que el incorporado. (En caso de que pueda, y sea lo suficientemente genérico, vaya y envíe su parche a la comunidad C ++.) Entonces, creo que el tipo incorporado () es una mejor opción en términos de velocidad de ejecución.

(ii) Velocidad de desarrollo del código:

Bueno, creo que también va +1 a build-in sort () ya que no necesitas escribir nada aparte de la función de comparación. (Para los tipos integrados, eso también es opcional).

(iii) Fiabilidad:

El código incorporado es mucho más confiable ya que es probado por la comunidad y tiene menos errores.

(iv) Genérico:

Debe escribir un algoritmo común para todos los tipos de datos, básicamente plantilla. Aunque eso no es un problema importante. Entonces, es lo mismo para ambos lados.

Por lo tanto, creo que el código incorporado parece ser una mejor opción en este momento, ya que requiere menos tiempo para ejecutarse, menos tiempo para escribir, lo suficientemente confiable y genérico como para usarse con cualquier tipo.

Si cree, puede optimizarlo, siempre puede contribuir a su código fuente, ya que es de código abierto. El algoritmo de clasificación utilizado en STL sort es intro-sort. Puede leer más sobre esto aquí: Introsort y http://www.cplusplus.com/referen… .

Durante los concursos, rara vez hay alguna razón para implementarlo por su cuenta. Pero aún debe conocer el algoritmo y poder implementarlo; no solo conocer más algoritmos le brinda una mejor capacidad para pensar en nuevas soluciones a los problemas, sino que en algunos casos no es posible usar sort ().

La programación competitiva se centra principalmente en la fiabilidad de precisión de velocidad. Entonces uno puede usar la función incorporada para obtener la mejor puntuación en la tabla de clasificación.

Nunca implementé mi propia función de clasificación. Siempre uso las funciones de clasificación incorporadas en C ++ y Java.