Hoy vamos a ver 6 algoritmos de clasificación que todo programador debería conocer.
Entonces, sin más preámbulos, comencemos.
Te puede interesar también:
- Cupón Udemy con 100% de descuento en el curso de AWS de nivel principiante a intermedio: EC2, IAM, ELB, ASG, Route 53
- Cupón de Udemy con 100% de descuento en el curso completo de SAP Analytics Cloud
- Cupón Udemy con 100% de descuento en el Curso combinado de Adobe Creative Suite: Photoshop, Illustrator, InDesign y Lightroom
Insertion Sort
La ordenación por inserción itera, consume un elemento de entrada en cada repetición y genera una lista de salida ordenada. En cada iteración, la ordenación por inserción elimina un elemento de los datos de entrada, encuentra la ubicación a la que pertenece dentro de la lista ordenada y lo inserta allí. Se repite hasta que no quedan elementos de entrada.
Toma una entrada a la vez y la compara con el elemento anterior en la lista para colocar el elemento seleccionado en el lugar correcto. Para el primer elemento, se compara con el siguiente elemento. Se repitió una y otra vez hasta que el último elemento de la lista se colocó en el lugar correcto. Después del último elemento, la lista se ordena.
Cuándo se puede usar
- Cuando la lista es pequeña
- Cuando la lista está casi ordenada, solo se necesitan unos pocos elementos para ordenar
Selection Sort
El algoritmo divide la lista de entrada en dos partes: una sublista ordenada de elementos que se construye de izquierda a derecha en el frente (izquierda) de la lista y una sublista de los elementos restantes sin ordenar que ocupan el resto de la lista. Inicialmente, la sublista ordenada está vacía y la sublista no ordenada es la lista de entrada completa. El algoritmo procede encontrando el elemento más pequeño (o el más grande, según el orden de clasificación) en la sublista sin clasificar, intercambiándolo con el elemento sin clasificar más a la izquierda (poniéndolo en orden) y moviendo los límites de la sublista un elemento a la derecha. .
Inicialmente, la lista se divide en dos partes. Una ordenada que está en el extremo izquierdo y otra lista sin clasificar que está en el extremo derecho. También al principio, la lista ordenada está vacía y todo el elemento está en la lista sin ordenar. Luego elegimos el elemento más pequeño de la lista desordenada y lo colocamos en la lista ordenada. Luego, la longitud de la lista ordenada aumenta y la lista sin ordenar disminuye. El proceso continúa hasta que la lista desordenada está vacía.
Cuándo usar
- Para verificar si la lista dada ya está ordenada o no
- Cuando la memoria es pequeña, ya que usa menos intercambio
Heap Sort
Heapsort divide su entrada en una región ordenada y otra no ordenada, y reduce iterativamente la región no ordenada extrayendo el elemento más grande de ella e insertándolo en la región ordenada. A diferencia de la ordenación por selección, la ordenación heapsort no pierde el tiempo con un escaneo de tiempo lineal de la región no ordenada; más bien, la ordenación en montón mantiene la región no ordenada en una estructura de datos en montón para encontrar más rápidamente el elemento más grande en cada paso.
En la ordenación de montón, el valor de entrada se almacena en una memoria de montón con la raíz del valor más grande del árbol. Luego, los valores más grandes se almacenan en una matriz de la lista. El proceso continúa hasta que la memoria del montón está vacía y la salida es la matriz ordenada.
Cuándo usar
- Cuando la lista es enorme
- Cuándo encontrar el elemento más pequeño o más grande en la lista
Merge Sort
Conceptualmente, una ordenación por fusión funciona de la siguiente manera:
- Divida la lista desordenada en n sublistas, cada una de las cuales contiene un elemento (una lista de un elemento se considera ordenada).
- Combine sublistas repetidamente para producir nuevas sublistas ordenadas hasta que solo quede una sublista. Esta será la lista ordenada.
La lista se divide en sublistas, cada lista contiene un elemento. Luego, cada elemento se compara con su elemento vecino y se fusiona en otra sublista según el orden.
Este proceso continúa con cada sublista. Ahora cada sublista tiene 2 elementos, ahora cada sublista se compara con la sublista del vecino. Cada sublista tiene 2 elementos. La lista se fusiona con otra sublista según el orden. Ahora cada sublista tendrá 4 elementos. Este proceso continúa hasta que solo queda una sublista. esta sublista estará ordenada.
Cuándo se puede usar
- Cuando la lista es lista enlazada
- Cuando la lista es enorme
Quick Sort
Quicksort es un algoritmo de divide y vencerás. Funciona seleccionando un elemento ‘pivote’ de la matriz y dividiendo los otros elementos en dos sub-matrices, según sean menores o mayores que el pivote. Por esta razón, a veces se le llama clasificación de intercambio de partición.[
En ordenación rápida, elegimos un elemento de la lista llamado pivote (principalmente es el primero o el último elemento de la lista). Luego, reordenamos la matriz de tal manera que todos los elementos que son menores que el pivote se colocan antes del pivote y los elementos mayores que los valores de pivote se colocan después del valor de pivote.
Repetimos este paso en ambas sublistas, es decir, antes y después del valor pivote. Esto continúa hasta que se ordena la lista.
Cuándo usar
- Cuando la lista es pequeña
- Se prefiere para la matriz
Counting Sort
En informática, la clasificación por conteo es un algoritmo para clasificar una colección de objetos de acuerdo con claves que son números enteros pequeños; es decir, es un algoritmo de clasificación de enteros. Funciona contando el número de objetos que tienen cada valor clave distinto y usando aritmética en esos recuentos para determinar las posiciones de cada valor clave en la secuencia de salida.
Después de tomar la entrada, contar el número de veces que el elemento se repite en la lista. Por lo tanto, tiene 2 valores distintos, uno para el elemento y el otro para el conteo. Luego haciendo el cálculo aritmético sobre él y decidiendo la posición de cada elemento en la lista.
Para el cálculo aritmético, lea el artículo de GeeksforGeeks sobre clasificación por conteo
Cuándo usar
- Cuando el rango de valores de entrada no es mayor que el número de valores que se ordenarán.
- Para una pequeña lista de arreglos
Deja tus comentarios y sugerencias
Sobre Facialix
Facialix es un sitio web que tiene como objetivo apoyar en el aprendizaje y educación de jóvenes y grandes. Buscando y categorizando recursos educativos gratuitos de internet, de esta manera Facialix ayuda en el constante aprendizaje de todos.
