Estructura de datos

Unidad: 2. Ordenacin y bsquedaActividad: Actividad 1. Mtodos de ordenacin Nombre: Luis Manuel Celis RuizDocente: Folio: Carrera: Ingeniera en Desarrollo de Software Grupo: Fecha: Correo Institucional:

Mtodos de ordenacinSeleccinEl mtodo de ordenacin por seleccin (Selection Sort) consiste en comparar el primer elemento del array con el segundo, el segundo con el tercero y as sucesivamente hasta encontrar el elemento ms pequeo e intercambiarlo por el que est en la primera posicin, luego se vuelve a buscar el siguiente ms pequeo y se intercambia con la segunda posicin hasta que la lista quede ordenada.Ejemplo:A0A1A2A3A4A5

642135

Se compara el 6 con el 4, 4 es menor, se compara 4 con 2, 2 es menor, se compara 2 con 1, 1 es menor, se compara 1 y 3, 1 sigue siendo menor, se compara 1 y 5, 1 sigue siendo menor, 1 (A3) se intercambia con 6 (A0) y quedara:A0A1A2A3A4A5

142635

Siguiendo el mismo proceso se intercambia 2 y 4 (A2 y A1)A0A1A2A3A4A5

124635

Luego 3 con 4 (A4 y A2)A0A1A2A3A4A5

123645

Luego 4 con 6 (A4 y A3)A0A1A2A3A4A5

123465

Por ltimo 5 y 6 (A5 y A4)A0A1A2A3A4A5

123456

Dado que en cada posicin solo puede haber un valor, se necesita de una memoria temporal que permita respaldar el valor de una posicin antes de sobrescribirla. Ejemplo:

A0A1

21

2

Aqu el valor de A0 es respaldado en la memoria temporal y el valor de A1 reemplaza al de A0 y el de A0 en la memoria temporal reemplaza al de A1.Ventajas: Funciona bien con listas pequeas No requiere memoria adicional ms que la que se necesita para hacer el intercambio entre posicionesDesventajas: Es lento Realiza numerosas comparaciones y resulta nada factible para listas enormesInsercinEl mtodo de ordenamiento por insercin consiste en comprobar que si el elemento a la izquierda es mayor se intercambia la posicin, hasta encontrarse con un valor menor que l o hasta llegar al inicio.Ejemplo:642135

El elemento 6 al estar al inicio se puede considerar que est ordenado y por ello se pasa al elemento 4 y aplicamos la regla: cuando el elemento a la izquierda sea mayor se intercambia la posicin, en este caso se intercambian los elementos 4 y 6. Quedara como:462135

Como se entiende que 4 y 6 estn ordenados pasamos al elemento 2 y como 4 es mayor intercambiamos posicin hasta que se encuentre con un valor menor a su izquierda o hasta el inicio. El resultado sera el siguiente:

A0A1A2A3A4A5

462135

426135

246135

Podemos ver como el 2 se ha movido a la posicin 1 y luego a la posicin 0. Ahora desde el elemento 1 (A3) intercambiamos posicin hasta que a su izquierda encuentre un elemento menor o hasta el inicio. El resultado es el siguiente:124635

Desde el elemento 3 intercambiamos posiciones aplicando la regla:123465

En este caso el elemento 3 se encontr con un elemento menor a l, en este caso el 2. Por ltimo tenemos al elemento 5 que a su izquierda hay un elemento mayor y por ello se intercambia con este.123456

Ventajas: Al igual que el mtodo de seleccin funciona muy bien en listas pequeas No requiere memoria adicional ms que la que se necesita para hacer el intercambio entre posicionesDesventajas: Realiza demasiadas comparaciones y se vuelve lento en listas grandesBurbuja o burbujeoEste mtodo es el ms popular para aprender el concepto de ordenacin, pero es el menos eficiente y por ello no se recomienda su uso en ningn caso excepto como tema de aprendizaje. El mtodo consiste en hacer comparaciones de dos elementos e ir ordenndolos en forma ascendiente intercambindolos, esta comparacin de elementos debe realizarse sobre todo el array aun si no hace los intercambios por tener elementos ordenados. Por ejemplo:642531

Aqu el 6 se compara con el 4 y se intercambian, se compara con el 2 y se intercambian, se compara con el 5 y se intercambian, se compara con el 3 y se intercambian, se compara con el 1 y se intercambian, quedara de la siguiente manera:462531

426531

425631

425361

425316

Como podemos ver el 6 hizo comparaciones y avanz a la ltima posicin debido a que no encontr un nmero mayor que l. Ahora el segundo recorrido:245316

243516

243156

Como podemos ver, en la comparacin el 4 y 5 no se intercambiaron debido a que el 5 es mayor y est a la derecha, finalmente l se compar el 5 y el 6 pero estos estaban ordenados de ah la falta de eficiencia de este mtodo de ordenamiento. Ahora el tercer recorrido:234156

231456

Aqu sucede lo mismo, algunos intercambios se realizan y otros no, pero aun as todo el recorrido debe hacerse. El 4 y 5 se compraran pero no se intercambian, al igual que el 5 y 6. El cuarto recorrido:213456

123456

Nuevamente el algoritmo hace otro recorrido ya que, aunque aparentemente ya est ordenado el array, no hay forma de guardar cada intercambio. El algoritmo debe asegurar que el array est ordenado.123456

Ventajas: Fcil de implementarDesventajas: Es el mtodo ms ineficiente de todos.

QuicksortEl Mtodo de ordenamiento quicksort es el ms complejo y tal vez el ms difcil de comprender, sin embargo es el ms eficiente. Este mtodo consiste en dividir en dos partes el array y separar un nmero cualquiera que funcione de pivote, este nmero nos servir para hacer las comparaciones, lo que se busca que es que los nmeros menores pasen al lado izquierdo y los mayores al derecho. Si en la comparacin el pivote resulta ser mayor o menor al valor comparado se intercambia el derecho con el izquierdo. Ejemplo:5376214

De este array tomamos el valor pivote, que puede ser cualquier nmero, aunque en la tcnica resulta mejor elegir elementos del inicio, centro o fin de array as como sacar la media o promedio de la lista sumando los valores y dividindolos entre la cantidad de ellos. En este caso tomamos el 4.5376214

Hacemos la comparacin hasta que el resultado de ambos lados sea verdadero4=1= verdadero

Al ser verdaderas las comparaciones, se intercambian los valores de posicin y continuamos.

1376254

4