¿Cuáles son los ejemplos prácticos de algoritmos de clasificación? He oído hablar de la clasificación de burbujas, la clasificación rápida y la clasificación por inserción. ¿Cuáles son los ejemplos prácticos de estos algoritmos? ¿Para qué se usan y dónde son necesarios en los sistemas de software?

Soy un programador de gráficos / juegos. Te diré cómo la clasificación es útil para mí.

Digamos que está haciendo un motor gráfico para mostrar algo como esto:

Cosas como el terreno, las rocas y las personas son mallas poligonales en 3D, mientras que los grupos de césped se representan como vallas publicitarias, es decir, solo un cuadrado que siempre está frente a la cámara con una textura de vegetación aplicada. Tienen un canal alfa que controla la transparencia de la textura.

Ahora, la geometría opaca, como las personas y las rocas, debe dibujarse de adelante hacia atrás. La razón de esto es que cada píxel que debe dibujarse puede requerir muchos cálculos y búsquedas de textura. Necesita buscar de qué color (es) es la superficie, quizás cuán irregular es, cuán especular es u otra información sobre cómo la superficie interactúa con la luz. Luego, necesita muchos cálculos de cómo la luz rebota para obtener el color final de ese píxel. Sin embargo, si la cámara está mirando una roca grande, no tiene sentido renderizar todos los píxeles de todas las cosas detrás de la roca y luego oscurecerla pintando sobre ella con la roca. Las GPU están diseñadas para pintar píxeles muy rápidamente, pero no tienen una velocidad infinita. Es mucho mejor omitir todo ese largo cálculo de píxeles si nunca se van a ver. En ese caso, sería mejor dibujar la roca primero y luego omitir cualquier píxel que esté más alejado (que es exactamente lo que el zbuffer ya está haciendo). Por lo tanto, las mallas opacas siempre deben clasificarse de adelante hacia atrás según la distancia a la cámara (y eso incluye el cielo, que generalmente es solo una gran caja con textura).

Sin embargo, para las cosas que usan transparencia, como la hierba, usa la mezcla, que combina el color que se escribirá con lo que ya se haya pintado en ese píxel. Para evitar el alias que es muy feo, las texturas de hierba tienen bordes suaves y agradables que utilizan diferentes niveles de transparencia. Por lo tanto, todas estas vallas publicitarias deben dibujarse de atrás hacia adelante después de dibujar todo el material opaco.

Espero que tenga un poco de sentido. Por lo tanto, toda la geometría en un pase de renderizado debe colocarse en una lista, y la lista debe clasificarse de una forma u otra utilizando la distancia a la cámara como métrica. Esto se hace para que puedan renderizarse en el orden correcto según la necesidad particular.

Este es solo un ejemplo de cómo la clasificación es útil para escribir aplicaciones.

Voy a tomar “práctico” en el sentido de “vida real”, porque eso hará que esto sea mucho más divertido.

Ordenamiento de burbuja:

Imagine por alguna razón que tiene como 8 muñecas rusas de anidación, todo en una fila. Están fuera de servicio (es decir, el más grande está en algún punto intermedio, etc.).

En este mundo, aunque puede cumplir con una tarea, tiene una discapacidad mental limitada y tiene el recuerdo de un pez dorado. * Como resultado, solo puede pensar en 2 muñecas a la vez.

Entonces … ¿cómo se ordenan las muñecas? Empiezas desde la izquierda y miras cada par (incluidos los pares superpuestos, es decir, 1 y 2 son un par, luego 2 y 3 son un par, etc.). Estás tratando de organizar las muñecas de la más pequeña a la más grande, por lo que si una muñeca más grande está a la izquierda, la cambias por la más pequeña a la derecha.

Repite esto hasta llegar al final de la línea.

Luego regresa al comienzo de la línea y hace lo mismo una y otra vez, hasta que pasa la línea y no tiene que hacer ningún cambio.

Luego, las muñecas se ordenan, y puedes apilarlas todas o hacer cualquier cosa espeluznante que la gente suele hacer con las muñecas rusas.

Tada … así es como funciona una burbuja.

Ordenación rápida:

Suponga que es un sabio que tiene la capacidad de dividir su memoria de trabajo y (idealmente) sus procesos de pensamiento a la mitad a voluntad.

Suponga que tiene una lista de 1000 números en orden aleatorio que desea ordenar.

Elija un número aleatorio y llame a esto el pivote.

Usa tus poderes de brujo para poner mentalmente todos los números más pequeños que el pivote a la izquierda y todos los más grandes al pivote a la derecha.

Ahora use sus poderes de división del cerebro para repetir exactamente este proceso con cada mitad (seleccionando nuevos pivotes de las mitades izquierda y derecha, y clasificando las mitades izquierda y derecha de las mitades izquierda y derecha en sus lados apropiados).

Ahora continúa dividiendo y repitiendo esto hasta que te quede solo un elemento para cada mini cerebro.

Luego, de izquierda a derecha, pídales a todos los mini cerebros que tosen el número que les queda y anótelos uno por uno.

Tada … así es como funciona una clasificación rápida. Es mucho más eficiente (para la mayoría de los casos de uso) que el tipo burbuja, mucho más rápido y es capaz de paralelizar.

Ahora ves por qué usamos computadoras para estas cosas.

* En serio, no me importa una mierda la memoria de un pez dorado real. No publique un “en realidad” en los comentarios.

Tome cualquier ejemplo como el mapa de Google.

Encontrará el algoritmo de búsqueda y clasificación en su núcleo. Cualquier aplicación de base de datos relacionada con ordenar, contar y buscar, verificar la base de datos interna o la base de datos como Oracle. Cualquier aplicación de redes sociales como twitter.

Si desea conocer el proceso superior que se ejecuta en la máquina Linux, mostrará el proceso superior en función de sus usos de recursos utilizando este método de clasificación y búsqueda. Comando grep de Linux basado en el algoritmo de búsqueda.

Este algoritmo se utiliza en procesamiento de texto o minería de datos o en el campo de la ciencia de datos.

En caso de que realmente soy el único ingeniero de software o informático aquí que entendió la intención de esta pregunta, doy una respuesta rápida. Eso sería sorprendente, lo sé, y podría estar equivocado, pero aquí está lo mejor que respondo que puedo explicar rápidamente.

Los algoritmos de clasificación son muy útiles para crear índices, por ejemplo, los índices en los sistemas de bases de datos. Un sistema de base de datos utilizará un índice para encontrar rápidamente un dato en particular. Esto es análogo a esas guías telefónicas anticuadas que ya no usamos porque Internet nos indexa todo.

Para comprender la indexación de la base de datos y cómo integran los algoritmos de clasificación en toda la solución, alguien puede publicar más preguntas.

Para elegir un algoritmo de clasificación, no dude en leer otras respuestas a esta pregunta.

Lo más importante que necesita saber sobre los algoritmos de clasificación es que no necesita conocerlos. Hace 30 años, en el mundo de la informática, es posible que haya tenido que escribir un algoritmo de clasificación. Hoy vienen como parte de su entorno en un lenguaje como Java y C #. Incluso C y C ++ generalmente tienen el algoritmo Quicksort ya implementado, y en un nivel mucho más optimizado que el que un programador promedio podría implementar. Quicksort es un algoritmo decente y generalmente superior en la mayoría de las necesidades.

No digo que no debas aprender los otros algoritmos. A veces, para ciertos conjuntos de datos, algunos de los más esotéricos son mejores. Son útiles para los conceptos que enseñan. Pero en los últimos 50 años, la mayoría de los conceptos básicos han sido cubiertos durante mucho tiempo y es mejor que se apoye en los hombros de sus predecesores, use su código y bibliotecas y avance con los conceptos de nivel superior de su código en lugar de aprender a escribir nuevos algoritmos de clasificación que alguien más inventó hace 40 años.

• Ordenación rápida

• El mejor algoritmo promedio de clasificación de casos
• qsort en C
• std :: sort en la mayoría de los casos para C ++

• Una clasificación híbrida estable que consiste en clasificación de inserción, clasificación de fusión y clasificación de selección.
• Se rumorea que es mejor que qsort
• Algoritmo de clasificación predeterminado de Python

• El mejor tipo estable
• (Oracle) algoritmo de ordenación predeterminado de Java

• El tipo más lento (sin contar bogosort y stooge) estable de O (n ^ 2)
• Tipo esencial para principiantes de algoritmos por su simple simplicidad

Mergesort: O (n log n), especialmente útil para ordenar las listas vinculadas.

Heapsort: O (n log n), útil para ordenar matrices y una ordenación común en memoria para motores de bases de datos.

Sort-merge o polyphase merge sort: necesario para conjuntos de clasificación muy grandes que son demasiado grandes para caber en la memoria. Los motores de base de datos ordenarán los grupos en la memoria (con algo así como el montón), escribirán los grupos en los archivos del disco y leerán los registros de forma iterativa para fusionarlos en una secuencia ordenada cuando el conjunto ordenado se transmita a la aplicación (o el resto del consulta).

Bubble-sort: tiene algunos usos para conjuntos de clasificación muy pequeños donde su rendimiento O (n ^ 2) no es un gran obstáculo, tiene muy poco código, por lo que puede ser útil para entornos restringidos como dispositivos pequeños, de lo contrario, a menudo se abusa de ellos. es “fácil de codificar”.

Quicksort: el tipo de caballo de batalla para la mayoría de las bibliotecas de clasificación. Un O “rápido” (n log n) en el caso promedio, pero O (n ^ 2) en el peor de los casos. (El peor comportamiento en el peor de los casos es por qué los motores DB lo evitan).

¿Cuáles son los usos prácticos del algoritmo de ordenación rápida?

Sin interés, el uso real y práctico de cualquier algoritmo de clasificación es ordenar cosas. Eso podría significar ordenar un grupo de usuarios por nombre de usuario o ID de usuario, mostrar su música en orden alfabético por nombre de pista, nombre de artista, etc., o mostrar su correo electrónico ordenado por remitente o fecha de envío.

Esta es una pregunta que las personas pueden tener cuando toman una clase de algoritmos. Si aciertas esto, podrías estar pensando en algo incorrecto.

A menudo, las clases de algoritmos cubrirán la clasificación ampliamente. Así es como puede ordenar los datos. Aquí hay otra forma. Aquí hay otra forma.

Muchos estudiantes ven esto y tienen una conclusión clave: la clasificación debe ser muy importante.

Y no están equivocados: puede ser muy importante, aunque más del 90% del tiempo que necesito para ordenar cosas, solo llamo un método Sort (). Pero esa no es la verdadera lección que la clase de algoritmos está tratando de enseñarte.

Creo que la verdadera lección es: a menudo hay más de una forma de hacer las cosas. Cuando se enfrenta a un problema, es posible que pueda escribir un código que resuelva ese problema. Quizás eso sea lo suficientemente bueno. O tal vez, dependiendo de lo que esté haciendo, debería mirar nuevamente y ver si hay una manera mejor y más eficiente de hacer las cosas.

Otra conclusión importante es que a menudo el problema que está tratando de resolver ya ha sido resuelto, a menudo por personas más inteligentes que usted o yo que pasamos mucho tiempo tratando de encontrar una forma eficiente de hacerlo. Si eso es cierto, generalmente desea comprender su solución, ver si tiene puntos débiles y, normalmente, solo usar su solución.

El tipo que falta en otras respuestas … introsort … es el estándar ahora para aplicaciones en memoria que no son GPU (en algunos casos, uno puede usar hardware de GPU para realizar un tipo de fusión de Batcher par-impar … Menciono esto para completarlo).

La complejidad en el peor momento de Quicksort siempre ha sido O (n ^ 2). Probar tres posibles valores de pivote para cada partición y usar la mediana ayuda, pero a veces no ayuda lo suficiente. En 1997, a David Musser se le ocurrió un híbrido de clasificación rápida, ordenada y de inserción llamada introsort que es O (n lg n) incluso para el peor de los casos, pero, a diferencia de la combinación, tiene un rendimiento promedio rápido.

El truco consiste en realizar un seguimiento de la profundidad de la pila de quicksort y, si el número de particiones en la pila ha alcanzado un múltiplo sintonizable de log (base 2) de n, ordenar la partición actual de forma no recursiva utilizando heapsort. En cada caso, si una partición tiene menos de 16 elementos, se clasifica utilizando una clasificación de inserción en lugar de una clasificación rápida o ordenada.

No estoy realmente seguro de lo que estás preguntando aquí. El uso práctico de cualquier algoritmo de clasificación es ordenar cosas. Eso es lo que hacen.

Ahora, si se pregunta por qué elegir la clasificación rápida sobre otros tipos, bueno, de eso realmente podemos hablar. La ordenación rápida es fácil de implementar. Y es muy rápido en el caso general. Esas son realmente buenas razones para elegirlo. Si desea un análisis más profundo, Quicksort es una buena descripción general fácil de entender.

La clasificación de burbujas también es uno de un buen ejemplo, pero encontré otro dispositivo de clasificación que hará que su trabajo sea más fácil y sin complicaciones. Haga clic en el enlace para saber más. Escanear, ordenar y guardar