TIPO DE METODOS NO ELEMENTALES

Conocidos como métodos de ordenamiento no elementales, van más allá de las operaciones básicas y aprovechan técnicas avanzadas para lograr una clasificación más rápida y efectiva de conjuntos de datos considerablemente grandes.

Método de Ordenamiento Shell:

El método de ordenamiento Shell o también denominado como Shell sort se caracteriza como una optimización del método de organización por inserción el cual se basa en una técnica de comparación y traslado de elementos adyacentes, lo que cambio con el método Shell es que estas comparaciones y traslados se hará en elementos con una separación específica entre ellos. A medida que el algoritmo progrese hará que el tamaño de esta separación se vea reducida de manera progresiva, lo que contribuye a una aproximación de los elementos desordenados hacia sus ubicaciones definitivas.

A continuación se presentara un ejemplo debidamente explicado para mayor comprensión al tema.

EJEMPLO:

Tenemos el siguiente arreglo:

Suponiendo que ya conocemos el número de espacios que tiene nuestro arreglo lo dividimos entre dos.

9/2 = 4.5

En este caso no podemos utilizar números decimales, solo un número entero para este ejemplo.

Ya obtenido el número anterior nos sirve para saber cuantos saltos debemos dar entre las celdas del arreglo, comenzamos comparando desde la celda 1.

El conteo se realiza desde el dato que se tiene como sucesor que es la celda 2, contamos 2 3 4 5, comparamos el dato de la celda 5 con nuestra celda 1.

Empezamos a comparar:

 

Ahora realizamos el paso anterior, pero desde la celda 5 y hacemos la cuenta que es 6 7 8 9, después comparamos:

Repetimos el mismo proceso, pero ahora desde la celda 2 y contamos 3 4 5 6

 

Nos quedamos en la celda 6 pero a la hora de contar 7 8 9… no cumple con los 4 saldos de celda por lo tanto termina este recorrido.

Ahora dividimos entre dos el número de saltos que estábamos realizando anteriormente que en este caso era 4:

4/2= 2

El nuevo número de saltos entre celdas será 2.

Realizamos los mismos pasos que aprendimos anteriormente, se mostrará las comparaciones que se harán a continuación:

Comparamos:

Comenzamos el segundo recorrido desde la cerda 2. Contamos y las comparaciones serán:

Comparamos:

No se puede hacer más comparaciones ya que el número de saltos es más grande que el arreglo y volvemos a dividir el número de saltos entre 2:

2/2 = 1

Las comparaciones son de la siguiente forma:

 

Después de comparar y cambiar celdas quedará el vector de la siguiente forma

Como ya no queda un número para dividir se sigue usando 1 hasta que no haya ningún movimiento.

Las comparaciones son de la siguiente manera:

 

Así quedaría el vector después de las comparaciones terminando su recorrido.

 

Nuevamente hacemos el mismo procedimiento terminando su recorrido y el vector quedaría así:

Igualmente hacemos las mismas comparaciones de solo 1 salto de celda y así quedaría el vector después de hacer su recorrido:

Ya finalizado el recorrido nos damos cuenta que ya esta ordenado el vector de izquierda a derecha de menor a mayor. Pero eso no basta, ya que el mismo método menciona que si hubo algún cambio de celda se tiene que repetir el ciclo de nuevo, comparando cada una de las celdas y si no se realizan cambios quiere decir que el método de ordenamiento a finalizado.

Método de Ordenamiento Quick Sort:

El método de ordenamiento Quick Sort se basa en una descomposición progresiva de un arreglo en segmentos mucho mas pequeños, dichos segmentos se les aplicara el proceso de ordenamiento. El método tiene como principal forma de organización la de elegir un elemento central al cual se le llamará “pivote”, este mismo será utilizado para poder reorganizar los elementos dentro del arreglo. Este ordenamiento se hará tomando los elementos menores para de esta forma situarlos hacia la izquierda, mientras que los elementos mayores serán ubicados a la derecha y de esta forma, se efectúa una partición que se repite en cada subconjunto, llevando al ordenamiento total de los elementos.

A continuación se presentara un ejemplo debidamente explicado para mayor comprensión al tema.

EJEMPLO:

Tenemos el siguiente arreglo y escogeremos un pivote, en este caso será el 4, también necesitamos dos punteros, de la izquierdo será el 8 y este se evalúa como Menor qué (<), al otro extremo del arreglo al lado derecho es el número 1, este se evalúa como Mayor qué (>). Empezamos a comparar con el puntero izquierdo de la siguiente manera: ¿8 < 4? Como no cumple pasamos al puntero derecho y evaluamos: ¿1 > 4? Tampoco cumple por lo tanto se cambia las posiciones de los punteros y se corren a su posición siguiente:

Empezamos a evaluar: ¿3 < 4? Si cumple por lo tanto se mueve el puntero de la izquierda a la siguiente posición y su número es 6, luego evaluamos: ¿6 < 4? No cumple entonces pasamos al puntero derecho y evaluamos: ¿7 > 4? Si cumple por lo tanto el puntero corre a su otra posición que en este caso es el número 5.

 

Luego evaluamos desde el puntero derecho: ¿5 > 4? Si cumple entonces el puntero corre a la siguiente posición que es el número 2 y evaluamos: ¿2 > 4? No cumple por lo tango se cambia de posición con el puntero izquierdo:

En este momento vamos a separar en dos grupos nuestro vector, nuevamente tenemos que elegir nuestro pivote y señalar los punteros que escogeremos de pivote el número 3 quedando de la siguiente manera:

Evaluamos el puntero izquierdo (1) con el pivote (3): ¿1 < 3? Si cumple por lo tanto el puntero izquierdo cambia a su siguiente posición que es 3. Pasamos al puntero derecho y empezamos a evaluar: ¿4 > 3? Si cumple entonces el puntero cambia a la siguiente posición que es (2) y evaluamos así: ¿2 > 3? No cumple por lo tanto cambia de posición con el otro puntero que es (3) organizando el primer grupo del vector.

Ahora escogemos un pivote en este caso es 5 y acomodamos los punteros a los extremos. Evaluamos desde el puntero izquierdo: ¿6 < 5? No cumple por lo pasamos al puntero derecho y evaluamos: ¿8 > 5? Si cumple entonces nuestro puntero derecho para a la siguiente posición que es (7) y evaluamos: ¿7 > 5) Si cumple por lo tanto el puntero derecho pasa a si siguiente posición (5) y evaluamos: ¿5 > 5? No entonces se cambia de posición con el puntero izquierdo finalizando así el ordenamiento del vector.

Método de Ordenamiento Fusión:

El método de ordenamiento de fusión o también llamado mezcla es un algoritmo el cual toma la lista con la que estamos trabajando y procede a dividirla en dos partes las cuales a su vez se irán dividiendo más y más veces dependiendo obviamente del tamaño de la lista, cuando ya se dividiera el máximo de veces que pueda lo que hará es el comparar los datos divididos en grupos de dos y los comparara para luego organizarlo y esto sucede con cada parte de la lista dividida y cuando estén ordenadas estas se irán fusionando para dar al final dos partes completamente ordenadas que se volverán a fusionar para dar la lista original pero completamente ordenada.

A continuación se presentara un ejemplo debidamente explicado para mayor comprensión al tema.

EJEMPLO:

Tenemos el siguiente arreglo:

 

Se dividirán en dos grupos, luego se sigue dividiendo hasta tener arreglos individuales:

 

Lo que prosigue es combinar estos nuevos arreglos en de dos unidades comparándolos en el mismo orden que fueron divididos, así quedarían las comparaciones:

Ahora tenemos estos cinco arreglos diferentes, lo que sucederá a continuación es que combinaremos estos arreglos comparando el primer elemento de cada arreglo recordando el orden en que fueron divididos.

Ahora tomamos las dos primeras listas y las comparamos, tenemos el 1 y 5, el 1 es menor que el 5, por lo tanto lo quitamos de su arreglo previo y lo ponemos primero en el nuevo arreglo, después sigue el 3 y el 5, el 3 es menor que 5 entonces es el siguiente, por último queda el arreglo de 5 y 6, comparamos y los acomodamos en ese orden.

Continuamos con los siguiente dos arreglos, comparamos el 7 y el 2, el 2 es menor entonces va primero en el arreglo, luego comparamos el 7 y 4, el 4 es menor por lo tanto es el siguiente, después el 7 y 9, el 7 es menor entonces es el siguiente en el arreglo y por último tenemos el 8 y 9, los comparamos y ponemos el 8 como siguiente.

Ahora tenemos dos listas, con las cuales crearemos un nuevo arreglo ordenándolo con el mismo método.

Comparamos el 1 y 2, el 1 es el nuevo elemento del arreglo, continuamos con el 5, 6, 7, 8 y al final 9. Finalmente quedaría ordenado.