UNIDAD IV METODOS DE ORDENAMIENTO

Ordenación interna.

Ordenar significa reagrupar o reorganizar un conjunto de datos u objetos en una secuencia especifica, la cual puede ser de dos formas distintas:

1. -       Ascendente (menor a mayor) o
2. -       Descendente (mayor a menor).

 Los métodos de ordenación se clasifican en dos categorías:

1. -       Ordenación interna (de arreglos) y
2.  Ordenación externa (de archivos). 
3. La ordenación interna o de arreglos, recibe este nombre ya que los elementos o componentes del arreglo se encuentran en la memoria principal de la computadora.

Los métodos directos, son complejos, difíciles de entender y son eficientes en grandes cantidades de datos.

Los métodos directos más conocidos son:

1.   Ordenación por intercambio.
2. Ordenación por inserción. 
3.  Ordenación por selección. 

Algoritmos de ordenamiento por intercambio.

La ordenación por intercambio consiste en comparar dos elementos del arreglo y determinar si existe un intercambio entre ellos, para esto debe definirse el tipo de ordenamiento que se quiere ya sea ascendente o descendente.

Los algoritmos de ordenación directa por intercambio que se analizaran son:

-       El método de la burbuja.

-       El método quicksort.

-       El método shellsort.

 

Burbuja

El método de ordenación por intercambio directo o método de la burbuja, es el más simple y consiste en comparar dos elementos adyacentes para determinar si se realiza un intercambio entre los mismos, esto en caso de que el primero sea mayor que el segundo (forma ascendente) o el caso de que el primero sea menor que el segundo (forma descendente).

 

1. Generar un ciclo que inicie desde uno hasta el número de elementos del arreglo.
2. Generar un segundo ciclo dentro del anterior que inicie desde cero hasta el número de elementos del arreglo menos dos.
3. Dentro del segundo ciclo debe existir una comparación que determina el tipo de ordenamiento (ascendente o descendente) entre el primer elemento (posición generado por el segundo ciclo) y el segundo elemento (el que le  sigue), si la respuesta a la condición es verdadera se realiza un intercambio entre los dos elementos.
4. Para realizar el intercambio se genera un almacenamiento temporal, el cual guarda el dato del primer elemento, el segundo elemento toma el lugar del primero y en el lugar del segundo se coloca lo que contiene el almacenamiento temporal.

Radix.

El método de ordenación radix es un algoritmo que ordena datos procesando sus elementos de forma individual, según la posición que ocupan dentro del dato. 

.

El método radix se clasifica en dos tipos según el orden en el que procesan los datos:

-       De derecha a izquierda y

-       De izquierda a derecha.

El procedimiento para aplicar  el algoritmo de radix es el siguiente:

Vector original:

25 57 48 37 12 92 86 33

Asignamos los elementos en colas basadas en el dígito menos significativo de cada uno de ellos.

0:

1:

2:12 92

3:33

4:

5:25

6:86

7:57 37

8:48

9:

Después de la primera pasada, la ordenación queda:

12 92 33 25 86 57 37 48

Colas basadas en el dígito más significativo.

0:

1:12

2:25

3:33 37

4:48

5:57

6:

7:

8:86

9:92

Lista ordenada:

12 25 33 37 48 57 86 92

QuickSort.

El método de ordenamiento rápido o método quicksort, es una técnica basada en otra conocida con el nombre divide y vencerás, que permite ordenar una cantidad de elementos . El algoritmo original es recursivo, como la técnica en la que se basa.

1. Recorrer el arreglo simultáneamente con izq y der: por la izquierda con izq (desde el primer elemento), y por la derecha con der (desde el último elemento). 
2. Mientras el arreglo en su posición izq (arreglo[izq]) sea menor que el pivote, continuamos el movimiento a la derecha.
3. Mientras el arreglo en su posición der (arreglo[der]) sea mayor que el pivote, continuamos el movimiento a la izquierda.
4. Terminando los movimientos se compara los índices y si izq es menor o igual al der, se intercambian los elementos en esas posiciones y las posiciones se cambian izq a la derecha y der a la izquierda. 

    ShellSort.

El método de ordenación shellsort es una versión mejorada del método de ordenación por inserción directa, que se utiliza cuando el número de elementos es grande.

 En el método de ordenación por inserción directa, cada elemento se compara con los elementos contiguos de su izquierda de uno por uno, para lograr su ordenamiento; si por ejemplo, el elemento a comparar  es el más pequeño y se encuentra en la última posición del arreglo.

 El método de ordenación shellsort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga pasos más grandes hacia la posición que debe ocupar.

El procedimiento para aplicar el algoritmo de shellsort es el siguiente:

1. Generar un ciclo que se encargue de controlar el tamaño que deben tener los incrementos.

1. Este ciclo debe iniciar con la división del tamaño del arreglo entre dos.
2. Mientras que el incremento sea mayor a cero debe continuar.
3. Y el cambio de incremento se elige de entre dos opciones: un uno o la división del incremento anterior entre dos.