Tarea 3 Unidad II

Los Algoritmos de pop mejorado

Con Pila Auxiliar

- Bubble Sort (Intercambio directo)

El método de intercambio directo puede trabajar de dos maneras diferentes. 

1. llevando los elementos más pequeños hacia la parte izquierda del arreglo. 

2. llevando los elementos más grandes hacia la parte derecha del mismo. 

La idea básica de este algoritmo consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados. Se realizan N-1 pasadas, transportando en cada una de las mismas el menor o mayor elemento (Según sea el caso) su posición ideal. Al final de las N-1 pasadas los elementos del arreglo estarán ordenados. 

Lo siguiente, es una implementación en Pseudocódigo, donde A es un arreglo de N elementos 

BURBUJA(A,N)

{I, J y AUX son variables de tipo entero}

1. Repetir con I desde 2 hasta N

1.1 Repetir con J desde N hasta I

1.1.1 Si A [J-1] > A [J] entonces

Hacer AUX? A [J-1] A [J-1] ? A [J]

A[J] ? AUX

1.1.2 {Fin del condicional del paso 1.1.1}

1.2 {Fin del ciclo del paso 1.1}

2. {Fin del ciclo del paso 1}

Con Corrimientos

· Insertion Sort

Este es uno de los métodos más sencillos. Consta de tomar uno por uno los elementos de un arreglo y recorrerlo hacia su posición con respecto a los anteriormente ordenados. Así empieza con el segundo elemento y lo ordena con respecto al primero. Luego sigue con el tercero y lo coloca en su posición ordenada con respecto a los dos anteriores, así sucesivamente hasta recorrer todas las posiciones del arreglo. Este es el algoritmo: 

- Procedimiento Insertion Sort

Este procedimiento recibe el arreglo de datos a ordenar a[] y altera las posiciones de sus elementos hasta dejarlos ordenados de menor a mayor. N representa el número de elementos que contiene a[]. 

paso 1: [Para cada pos. del arreglo] For i <- 2 to N do 

paso 2: [Inicializa v y j] v <- a[i] j <- i.

paso 3: [Compara v con los anteriores] While a[j-1] > v AND j>1 do

paso 4: [Recorre los datos mayores] Set a[j] <- a[j-1], paso 5: [Decrementa j] set j <- j-1. paso 5: [Inserta v en su posición] Set a[j] <- v.

paso 6: [Fin] End.

- Selection Sort

El método de ordenamiento por selección consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición. Luego el segundo mas pequeño, y así sucesivamente hasta ordenar todo el arreglo.

- Procedimiento Selection Sort

paso 1: [Para cada pos. del arreglo]

paso 2: [Inicializa la pos. del menor]

For i <- 1 to N do

menor <- i

paso 3: [Recorre todo el arreglo]

paso 4: [Si a[j] es menor]
For j <- i+1 to N do If a[j] < a[menor] then

paso 5: [Reasigna el apuntador al menor] min = j paso 6: [Intercambia los datos de la pos. min y posición i] Swap(a, min, j).

paso 7: [Fin] End.