Ordenamiento c++

Algoritmos de Ordenamiento

Fernando A. Lagos B.
Copyleft 2007

INDICE

1 Introducción 2 Tipos de Algoritmos 2.1 Algoritmos iterativos 2.2 Algoritmos recursivos 3 Método de la Burbúja 3.1 Burbúja Símple 3.2 Burbúja Mejorada 3.3 Burbúja Óptimizada 4 Insercion y selección 5 Ordenamiento por Mezcla 6 Método Shellsort 7 Método Rápido (quicksort) 8 Complejidad

Pág. 3 Pág. 4 Pág. 5 Pág. 6Pág. 7 Pág. 8 Pág. 9 Pág. 10 Pág. 11 Pág. 12 Pág. 14 Pág. 15 Pág. 17

1 - INTRODUCCION
Los algoritmos de ordenamiento nos permite, como su nombre lo dice, ordenar. En este caso, nos serviran para ordenar vectores o matrices con valores asignados aleatoriamente. Nos centraremos en los métodos más populares, analizando la cantidad de comparaciones que suceden, el tiempo que demora y revisando elcódigo, escrito en Java, de cada algoritmo. Este informe nos permitirá conocer mas a fondo cada metodo distinto de ordenamiento, desde uno simple hasta el mas complejo. Se realizaran comparaciones en tiempo de ejecucion, pre-requisitos de cada algoritmo, funcionalidad, alcance, etc.

2 – TIPOS DE ALROGITMOS
Para poder ordenar una cantidad determinada de numeros almacenadas en un vector o matriz,existen distintos metodos (algoritmos) con distintas caracteristicas y complejidad. Existe desde el metodo mas simple, como el Bubblesort (o Método Burbúja), que son simples iteraciones, hasta el Quicksort (Método Rápido), que al estar optimizado usando recursion, su tiempo de ejecucion es menor y es más efectivo.

2.1 – METODOS ITERATIVOS
Estos metodos son simples de entender y de programarya que son iterativos, simples ciclos y sentencias que hacen que el vector pueda ser ordenado. Dentro de los Algoritmos iterativos encontramos: Burbuja Inserción Selección Shellsort

– – – –

2.2 - METODOS RECURSIVOS
Estos metodos son aún mas complejos, requieren de mayor atención y conocimiento para ser entendidos. Son rápidos y efectivos, utilizan generalmente la técnica Divide y vencerás,que consiste en dividir un problema grande en varios pequeños para que sea más fácil resolverlos. Mediante llamadas recursivas a si mismos, es posible que el tiempo de ejecución y de ordenación sea más optimo. Dento de los algoritmos recursivos encontramos: Ordenamiento por Mezclas (merge) Ordenamiento Rápido (quick)

– –

3 – METODO DE LA BURBUJA
El metodo de la burbuja es uno de los massimples, es tan facil como comparar todos los elementos de una lista contra todos, si se cumple que uno es mayor o menor a otro, entonces los intercambia de posición. Por ejemeplo, imaginemos que tenemos los siguientes valores: 5 6 1 0 3

Lo que haria una burbuja simple, seria comenzar recorriendo los valores de izq. a derecha, comenzando por el 5. Lo compara con el 6, con el 1, con el 0 y con el3, si es mayor o menor (dependiendo si el orden es ascendiente o descendiente) se intercambian de posicion. Luego continua con el siguiente, con el 6, y lo compara con todos los elementos de la lista, esperando ver si se cumple o no la misma condicion que con el primer elemento. Asi, sucesivamente, hasta el ultimo elemento de la lista.

3. 1 – BURBUJA SIMPLE
Como lo describimos en el itemanterior, la burbuja mas simple de todas es la que compara todos con todos, generando comparaciones extras, por ejemplo, no tiene sentido que se compare con sigo mismo o que se compare con los valores anteriores a el, ya que supuestamente, ya estan ordenados.

for (i=1; i temp) && (j >= 0) ) { matrix[j + 1] = matrix[j]; j--; } matrix[j + 1] = temp; } } Seleccion(int[]matrix) { int i, j, k, p,buffer, limit = matrix.length-1; for(k = 0; k < limit; k++) { p = k; for(i = k+1; i 1) { n1 = n / 2; n2 = n - n1; mergesort(matrix, init, n1); mergesort(matrix, init + n1, n2); merge(matrix, init, n1, n2); } }

Y el algoritmo que nos permite mezclar los elementos según corresponda:
private static void merge(int[ ] matrix, int init, int n1, int n2) { int[ ] buffer = new int[n1+n2]; int temp = 0;...