AlgoritmosOrdenamiento

ALGORITMOS DE
ORDENAMIENTO
Compilado del texto de:
Fernando Lagos B. por Corina Flores

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

1.Introducción
• Los algoritmos de ordenamiento nos permite, como su nombre lo
dice, ordenar. Por ejemplo elementos dispuestos ya sea en
arreglos, matrices o listas 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 el código, escrito en Java, de cada algoritmo. Este
material 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 Algoritmos
• Para poder ordenar una cantidad determinada de
numeros almacenados en un arreglo o matriz, existen
distintos métodos (algoritmos) con distintas
característicasy complejidad.
• Existe desde el método 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 recursión, su tiempo de ejecucion es menor y es
más efectivo.

• Estos métodos son simples de entender y de programar ya
que son iterativos, simples ciclos y sentencias que hacen que
el arreglo pueda serordenado. Dentro de los Algoritmos
iterativos encontramos:
•
•
•
•

Burbuja
Inserción
Selección
Shellsort

Métodos Recursivos
• Estos métodos 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)

Método de la Burbuja
• El método de la burbuja es uno de los mas simples, es tan fácil como
comparar todos los elementos de una lista contra todos, si se cumple
que uno esmayor o menor a otro, entonces los intercambia de posición.
• Por ejemplo, imaginemos que tenemos los siguientes valores:
56103
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 el 3, si es mayor o menor (dependiendo si el orden es
ascendiente o descendiente) se intercambian de posición.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
condición que con el primer elemento. Asi, sucesivamente, hasta el
ultimo elemento de la lista.

Burbuja Simple
• Como lo describimos en el item anterior, la burbuja mas
simple de todas es la que compara todos con todos,
generando comparaciones extras, por ejemplo, notiene
sentido que se compare consigo mismo o que se compare con
los valores anteriores a él, ya que supuestamente, ya estan
ordenados.

for (i=1; i for j=0 ; j if (vector[j] > vector[j+1])
temp = vector[j];
vector[j] = vector[j+1];
vector[j+1] = temp;

Burbuja Mejorada
• Una nueva version del método de la burbuja seria
limitando el número de comparaciones, dijimosque era
inutil que se compare consigo misma.
• Si tenemos una lista de 10.000 elementos, entonces son
10.000 comparaciones que estan sobrando.
• Imaginemos si tenemos 1.000.000 de elementos. El
metodo seria mucho mas optimo con “n”
comparaciones menos (n = total de elementos).

Actividad
• ¿Cuáles serían los cambios a efectuar sobre el
algoritmo anterior, para lograr una Burbuja
mejorada?.
• Se...

Leer documento completo

Regístrate para leer el documento completo.