Algoritmos de Ordenación Básica
Enviado por Michael Davis • 11 de Marzo de 2017 • Resúmenes • 1.871 Palabras (8 Páginas) • 304 Visitas
Algoritmos de Ordenación Básica
- Introducción a Ordenación
- Ordenación por Selección
Introducción a Ordenación
Existen muchos algoritmos de ordenación básica diferentes. Cada uno de estos algoritmos tiene características, comportamiento y requerimientos únicos. Por ejemplo, para el mismo conjunto de datos, un algoritmo puede desarrollar menos comparaciones que otro algoritmo. De forma similar, durante la ejecución otro algoritmo puede intercambiar las posiciones de los elementos de los datos con menos frecuencia que otro algoritmo. El comportamiento de algunos algoritmos difiere cuando se les presentan datos que están casi ordenados, a cuando se les presentan datos que están completamente desordenados. Son estas diferencias entre el conjunto de estas propiedades las que hacen a cada algoritmo de ordenación único. Estas características también hacen un algoritmo más o menos aplicable en ciertas situaciones.
Ordenación por Selección
Ordenación por selección (selection sort) es un algoritmo de ordenación básica que trabaja haciendo iteraciones, o pasos (movimientos), entre los datos que están siendo ordenados. Cada paso resulta en la colocación de un elemento en el lugar correcto. Como resultado, cada paso subsiguiente tiene que inspeccionar un elemento menos que el paso anterior.
[pic 1]
Figura 1 Un arreglo desordenado
La Figura 1 contiene un arreglo desordenado. Debido a que este arreglo contiene ocho elementos, la ordenación por selección tomará siete pasos para ordenar los datos. Cada paso coloca un elemento en la posición que dejará un arreglo ordenado. Las siguientes dos figuras representan respectivamente los primeros dos pasos. En cada figura, la flecha rellena indica la posición que el paso está buscando llenar. Durante cada paso, el algoritmo busca el elemento más pequeño restante. El paso termina con el algoritmo intercambiando el elemento más pequeño en la posición bajo consideración.
[pic 2]
Figura 2 El primer paso
Después del primer paso, el elemento más bajo es colocado en la primera posición del arreglo. El siguiente paso, ilustrado en la Figura 3, coloca el segundo elemento más bajo en la segunda posición del arreglo.
[pic 3]
Figura 3 El segundo paso
El algoritmo de ordenación por selección siempre hace un paso menos, que el número de elementos en el arreglo. Esto sucede aún si el arreglo original ya se encuentra ordenado. El algoritmo no tiene un mecanismo para detectar cuando el arreglo está ordenado, por lo que debe realizar todos los pasos requeridos. Una implantación en C++ de la ordenación por selección se muestra en el Listado 1.
1: | // Sorting using selection sort template <typename T> void selection_sort(vector for (unsigned int i = 0; i < v.size() - 1; i++) { unsigned int best = i; for (unsigned int j = i + 1; j < v.size(); j++) { if (v[j] < v[best]) { best = j; } } if (best != i) { T temp = v[i]; v[i] = v[best]; v[best] = temp; } } } |
Listado 1 Ordenación por Selección |
Algoritmos de Ordenación Rápida
- Algoritmos de Ordenación Básica y Rápida
Ordenación Rápida (Quicksort)
El Algoritmo
Ordenación rápida o "quicksort" es un algoritmo de ordenación rápida que usa un enfoque divide-y-vencerás para la solución de problemas. A diferencia de los algoritmos de ordenación básica que ya hemos revisado, la ordenación rápida usa recursión. Dado un arreglo de elementos a ordenar, el algoritmo divide recursivamente el arreglo en arreglos más y más pequeños. Luego el algoritmo ordenación rápida ordena estos arreglos pequeños y combina los resultados para crear una versión ordenada del arreglo original. Debido a su naturaleza recursiva, la implantación del algoritmo ordenación rápida puede ser difícil de entender. Antes de examinar una implantación, consideramos la idea detrás del algoritmo.
...