EVAP7

ORDENAMIENTOS EN LENGUAJE 

Y PROGRAMACIÓN

Es la clasificación de datos que consiste en la disposición de los mismos de acuerdo con algún valor o característica.

Por ejemplo, cada elemento de una agenda telefónica tiene un campo nombre y por esto se encuentran organizados en un orden de la A la Z.

 De la misma forma un lista o vector de datos se dice que esta ordenado de manera ascendente, si X [ i ] <= X [ i +1].

En C++ se encuentran dos tipos de ordenamientos: Ordenamientos Internos y Ordenamientos Externos.

Nosotros estudiaremos únicamente Ordenamientos Internos.

• Ordenamientos Internos:

Se clasifican en dos grandes grupos:

1. Directos (burbuja, selección e inserción).
2. Logarítmicos (Shell sort, Merge sort, Heap sort, Quick sort, Radix).

a) .Ordenación por Intercambio (burbuja):

Es uno de los métodos relativamente más sencillo e intuitivo, pero también resulta ser muy ineficiente.

Se basa en la ordenación por cambio, y recibe su nombre de la semejanza con las burbujas de un depósito de agua donde cada burbuja busca su propio nivel.

Para realizar este tipo de ordenamientos:

1.  Comparar el primer y segundo elemento, intercambiarlos si el primero es mayor que el segundo; luego se compara el primero con el tercero, y el proceso se repite sucesivamente.

2.  Se repite el paso anterior, pero ahora con el segundo y tercero, en caso de ser necesario 

Intercambian, y así hasta llegar a comparar el segundo con el último.

Ejemplo de Ordenamiento por Intercambio (Burbuja) en C++ :

b) .Ordenamiento por Método de Selección:

La idea básica es encontrar el elemento más pequeño (grande), en orden ascendente de la lista, e intercambiarlo con el elemento que ocupa la primera posición en la lista, a continuación se busca el siguiente elemento más pequeño y se transfiere a la segunda posición.

Se repite el proceso hasta que el último elemento ha sido transferido a su posición

 correcta.

El algoritmo de ordenación depende a su vez del algoritmo necesario para localizar el componente mayor (menor) de un array. 

Es un proceso muy similar al método de la burbuja pero haciendo más eficiente la búsqueda y evitando intercambios innecesarios.

Ejemplo de Ordenamiento por Método de Selección:

c) .Ordenamiento por Método de Inserción:

El algoritmo ordena los dos primeros elementos de la lista, a continuación el tercer elemento se inserta en la posición que corresponda, el cuarto se inserta en la lista de tres elementos, y así sucesivamente.

Este proceso continua hasta que la lista este totalmente ordenada.

Sea una lista A[1], A[2], ... A[n]. Los pasos a dar para una ordenación por Metodo de Inserción son:

1.  Ordenar A[1] y A[2].

2.  Comparar A[3] con A[2], si A[3] es mayor o igual a que A[2], sigue con el siguiente elemento si no se compara A[3] con A[1]; si A[3] es mayor o igual que A[1], insertar A[3] entre A[1] yA[2].

si A[3] es menor que A[1], entonces transferir A[3] a A[1], A[1] a A[2] y A[2] a A[3].

3.  Se suponen ordenados los n-1 primeros elementos y corresponde insertar el n-ésimo

elemento. Si A[m] es mayor que A[k] (con K = 1, 2, ..., m-1), se debe correr una posición

A[k+1], ... A[m-1] y almacenar A[m] en la posición k+1.

d) .Ordenamiento por Método de Shell:

La idea básica de este método es distribuir el arreglo de manera que se genere una matriz de valores donde cada elemento es comparado de manera adyacente empleando un mecanismo de inserción directa simple, dicho rango que genera grupos de manera matricial que es reducido gradualmente hasta estabilizarse en un valor uniforme de 1.

Shell propone que las comparaciones entre elementos se efectúen con saltos de mayor tamaño, pero con incrementos decrecientes; así, los elementos quedaran ordenados más rápidamente. 

Ejemplo de Ordenamiento por Método de Shell:

e) .Ordenación por partición e intercambio (Quick Sort):

Es un algoritmo relativamente eficiente y representa una mejora sustancial al método de intercambio directo.
Se siguen los siguientes pasos para realaizar el algoritmo :

1.  Elegir un elemento de la lista de elementos a ordenar (pivote).

2.  Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado
queden todos los menores que él, y al otro los mayores.
 Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. 
En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.

3.  La lista queda separada en dos sub-listas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.

4. Repetir este proceso de forma recursiva para cada sub-lista mientras éstas contengan más

de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Ejemplo de Ordenamiento por  partición e intercambio (Quick Sort):

f) .Ordenación basado en comparaciones (Heap Sort):

Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado.

g) . Ordenación por Mezcla (Merge Sort):

Para realizar el algoritmo se realizan los siguientes pasos:

1. Si la longitud de la lista es 0 ó 1, entonces ya está ordenada. En otro caso:

2. Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del tamaño.
3. Ordenar cada sublista recursivamente aplicando el ordenamiento por mezcla.

4. Mezclar las dos sublistas en una sola lista ordenada.