Algoritmos de selección, definición y ejemplos.

Grupo 9: 
Thayris Navarro C. I.: 26.938.872; Ruben Farías C. I.: 27.719.360; Analis Caldera C. I.: 27.917.093

Definición:

En informática, es un algoritmo para encontrar el k-ésimo número más pequeño en una lista o un vector, este número se llama estadística de orden k. Esto incluye los casos de búsqueda de mínimo, máximo y mediana. El caso más simple de un algoritmo de selección consiste en encontrar el elemento mínimo (o máximo) por iteración en la lista, manteniendo un registro del mínimo (o máximo) en cada etapa de la iteración. 

Estos algoritmos sirven para ordenar  elementos de manera creciente o decreciente  en una lista de n elementos. Si hay n elementos que requieren ordenarse, se repetirá el proceso n-1 veces para conseguir el resultado deseado.  La mayoria de ellos, consisten en comparar los dos primeros elementos de una matriz e intercambiarlos si es necesario; luego se realiza la comparación con el primer y tercer término, se intercambian si se es requerido, y asi sucesivamente hasta comparar el primer y último término. Después se repite el mismo procedimiento con el segundo elemento, se compara este con cada uno de la matriz, y así con el resto de los elementos de la matriz dada.

Algoritmos de selección más usados:

- Selection sort: Este algoritmo de selección es el más fácil de implementar y recordar, pues es muy sencillo. Consiste en ordenar una matriz al encontrar repetidamente el elemento mínimo o maximo de la parte sin clasificar y colocarlo en su posición correcta en una matriz ordenada. Este algoritmo se basa en realizar comparaciones, y para que pueda hacer su trabajo, mantiene dos subarreglos en una matriz dada.

1) El sub-array que ya está ordenado.

2) Sub-array restante sin clasificar.

-Insertion sort: El orden de inserción funciona de una manera ligeramente diferente. Siempre mantiene una lista secundaria ordenada en las posiciones más bajas de la lista. Cada nuevo elemento se "inserta" de nuevo en la lista secundaria anterior, de modo que la lista secundaria ordenada es un elemento más grande. 

-Bubble sort: Es un algoritmo basado en la relación, en el que cada par de elementos adyacentes se compara y los elementos se intercambian si no están en orden.

 

-Shell sort: Este algoritmo utiliza la ordenación por inserción en elementos muy extendidos, primero para ordenarlos y luego clasifica los elementos menos espaciados. Este espaciado se denomina intervalo.

-Heapsort: implica construir una estructura de datos del montón a partir de la matriz dada y luego utilizar el montón para ordenar la matriz. Heapsort es una estructura de datos basada en árbol especial, que satisface las siguientes propiedades especiales del montón:

1. Propiedad de la forma: la estructura de los datos del montón es siempre un árbol binario completo, lo que significa que todos los niveles del árbol están completamente llenos.

2. Propiedad del montón: todos los nodos son mayores, iguales o menores que cada uno de sus hijos. Si los nodos principales son mayores que sus nodos secundarios, el montón se llama Max-Heap, y si los nodos principales son más pequeños que sus nodos secundarios, el montón se llama Min-Heap.

-Quicksort: es un algoritmo de dividir y conquistar. Selecciona un elemento como pivote y divide la matriz dada alrededor del pivote seleccionado. Hay muchas versiones diferentes de Quicksort que seleccionan pivote de diferentes maneras.

Ventajas y desventajas de los algoritmos de selección más usados:

	Ventajas	Desventajas
Selection sort	Es fácil su implementación No requiere memoria adicional Realiza pocos intercambios Su rendimiento es constante	Es lento Es poco eficiente cuando se usa en listas grandes o medianas Realiza numerosa comparaciones
Insertion sort	Simple Fácil de usar Requerimiento mínimo de memoria Eficiente en listas pequeñas	Presenta deficiencia en listas grandes En algunos casos es lento Realiza numerosas comparaciones  No tiene buen  funcionamiento en comparación con otros algoritmos  de ordenamiento
Bubble sort	Es bastante sencillo Es eficaz	Consumen  bastante tiempo en la computadora Requiere muchas escrituras de memoria
Shell sort	No requiere memoria adicional Mejor rendimiento que el método de Inserción clásico 5 veces más rápido que Bubble sort 2 veces más rápido que Insertion sort	Implementación algo confusa Realiza numerosas comparaciones e intercambios Es significativamente más lento  que Heapsort y Quicksort
Quick sort	Requiere pocos recursos en comparación a otros algoritmos de ordenamientos No se requiere de espacio adicional durante ejecución	Un simple error en la implementación puede pasar sin detección , lo que provocaría un rendimiento pésimo No es útil para las aplicaciones de entrada dinámica, donde se requiere reordenar una lista de elementos con nuevos valores
Heap sort	Funciona mejor con datos desordenados Se desempeña tan bien como el Quicksort  y se comporta mejor que este último en los peores casos No utiliza memoria adicional	No es estable ,ya que se comporta de manera ineficaz con datos del mismo valor Método complejo