Ordenaciones en arreglos
La importancia de mantener nuestros arreglos ordenados radica en que es mucho más rápido tener acceso a un dato en un arreglo ordenado que en uno desordenado.
Existen muchos algoritmos para la ordenación de elementos en arreglos, enseguida veremos algunos de ellos.
a) Selección directa
Este método consiste en seleccionar el elemento más pequeño de nuestra lista para colocarlo al inicio y así excluirlo de la lista.
Para ahorrar espacio, siempre que vayamos a colocar un elemento en su posición correcta lo intercambiaremos por aquel que la esté ocupando en ese momento.
El algoritmo de selección directa es el siguiente:
i <- 1 mientras i<= N haz min <-i j <- i + 1 mientras j <= N haz si arreglo[j] < [min] entonces min <-j j <- j + 1 intercambia(arreglo[min],arreglo[i]) i <- i +1
b) Ordenación por Burbuja
Es el método de ordenación más utilizado por su fácil comprensión y programación, pero es importante señalar que es el más ineficiente de todos los métodos .
Este método consiste en llevar los elementos menores a la izquierda del arreglo ó los mayores a la derecha del mismo. La idea básica del algoritmo es comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados.
i <- 1 mientras i < N haz j <- N mientras j > i haz si arreglo[j] < arreglo[j-1] entonces intercambia(arreglo[j],arreglo[j-1]) j < j - 1 i <- i +1
c) Ordenación por Mezcla
Este algoritmo consiste en partir el arreglo por la mitad, ordenar la mitad izquierda, ordenar la mitad derecha y mezclar las dos mitades ordenadas en un array ordenado. Este último paso consiste en ir comparando pares sucesivos de elementos (uno de cada mitad) y poniendo el valor más pequeño en el siguiente hueco.
procedimiento mezclar(dat,izqp,izqu,derp,deru) inicio izqa <- izqp dera <- derp ind <- izqp mientras (izqa <= izqu) y (dera <= deru) haz si arreglo[izqa] < dat[dera] entonces temporal[ind] <- arreglo[izqa] izqa <- izqa + 1 en caso contrario temporal[ind] <- arreglo[dera] dera <- dera + 1 ind <- ind +1 mientras izqa <= izqu haz temporal[ind] <- arreglo[izqa] izqa <- izqa + 1 ind <- ind +1 mientras dera <= deru haz temporal[ind] <=dat[dera] dera <- dera + 1 ind <- ind + 1 para ind <- izqp hasta deru haz arreglo[ind] <- temporal[ind] fin
Fuente: Apunte de Estructura de Datos del Instituto tecnológico de la Paz
