urgencia
mohamed
19 de Enero del 2006
nesecto un ayuda urgenta para un tarea que tengo
se trata de mtodos de ordenamiento en memoria interna (quick sort-inserccion-soll sort). graciass
se trata de mtodos de ordenamiento en memoria interna (quick sort-inserccion-soll sort). graciass
marlen_fajardo
19 de Enero del 2006
28.3.2 Método de Insertion-Sort
Este método toma cada elemento de la lista a ordenar y lo compara con los que se encuentran en posiciones anteriores a la de él dentro de la lista. Si el elemento con el que se está comparando es mayor que el elemento a ordenar, se recorre hacia la siguiente posición superior. Si por el contrario, resulta que el elemento con el que se está comparando es menor que el elemento a ordenar, se detiene el proceso de comparación pues se encontró que el elemento ya está ordenado y se coloca en su posición (que es la siguiente a la del último número con el que se comparó).
28.3.2.1 Algoritmo
Algoritmo 28.2: Insertion-Sort.
Inicialización.
- Sea L una lista de elementos de tipo T.
Método:
Inicio
entero i, j;
T aux;
desde i <-2 hasta L.Longitud() con paso 1
inicio
aux <-- L[i]
j <-- i
mientras (j-1 > 1) y (aux < L[j-1])
inicio
L[j] <-- L[j-1] //Equivalente a
// T temp = L[j-1]
// L.Eliminar(i); L.Insertar(temp, i);
j <-- j-1
fin
L[j] <--aux //Equivalente a
// L.Eliminar(j); L.Insertar(aux, j);
fin
Fin
Ejemplo:
Supongamos que la lista L es una lista de enteros y L = (4, 3, 5, 2, 1).
En la primera iteración del ciclo externo, cuando i = 2, tenemos la siguiente situación:
aux = 3, L = (4, 3, 5, 2, 1)
La idea de este algoritmo es examinar los elementos que están antes de un elemento pivote (aux). Los elementos mayores que el elemento pivote se desplazan a una posición posterior. Se detiene este proceso cuando se encuentra un elemento menor que el elemento pivote. Luego, el elemento pivote (aux) se coloca en la posición donde se detuvo este proceso.
Es por eso que:
aux = 3  L = (4, 4, 5, 2, 1) Pues 4 > aux
 L = (3, 4, 5, 2, 1) Se llegó al principio de la lista,
se coloca aux en la posición donde
se detuvo el proceso
Luego, se toma como pivote, el elemento que está en la tercera posición, es decir, aux = 5. De entrada 5 > 4, es decir, el elemento pivote es mayor que el elemento que le antecede. Por tanto, no suceden cambios en la lista.
Tomando ahora el elemento que está en la cuarta posición como pivote, tenemos:
aux = 2  L = (3, 4, 5, 5, 1) Pues 5 > aux
 L = (3, 4, 4, 5, 1) Pues 4 > aux
 L = (3, 3, 4, 5, 1) Pues 3 > aux
 L = (2, 3, 4, 5, 1) Se llegó al principio de la lista,
se coloca aux en la posición donde
se detuvo el proceso
El mismo proceso se harÃa para aux = 1, por lo que al finalizar el método, la lista L quedarÃa ordenada de forma ascendente.
28.3.3 Método Quick-Sort
Vimos que en un algoritmo de ordenamiento por intercambio, son necesarios intercambios de elementos en sublistas hasta que no son posibles más intercambios. En el Bubble-Sort, son comparados elementos correlativos en cada paso de la lista. Por lo tanto para ubicar un elemento en su correcta posición, pueden ser necesarios varios intercambios.
Veremos el ordenamiento que sigue el método de intercambio y fue desarrollado por C.A.R. Hoare: Quicksort. Es más eficiente que el bubblesort porque los intercambios involucran elementos que están más apartados, entonces menos intercambios son requeridos para poner un elemento en su posición correcta.
La idea básica del algoritmo es elegir un elemento llamado pivote, y ejecutar una secuencia de intercambios tal que todos los elementos menores que el pivote queden a la izquierda y todos los mayores a la derecha. Lo único que requiere este proceso es que todos los elementos a la izquierda sean menores que el pivote y que todos los de la derecha sean mayores luego de cada paso, no importando el orden entre ellos, siendo precisamente esta flexibilidad la que hace eficiente al proceso.
Se hacen dos búsquedas, una desde la izquierda y otra desde la derecha, comparando el pivote con los elementos que se van recorriendo, buscando los menores o iguales y los mayores respectivamente. Ese pivote no necesariamente (casi nunca) va a estar en el centro del arreglo.
El algoritmo sigue los pasos esenciales de la estrategia recursiva ‘Divide y Vencerás’.
Divide la lista en dos partes, hace la llamada recursiva a cada una de las partes hasta ordenar todos los elementos.
28.3.3.1 Algoritmo
Algoritmo 28.3: Quick-Sort.
Inicialización.
- Sea L una lista de elementos de tipo T.
- Sean izq y der dos valores enteros que indican las posiciones extremas que definen la sublista de donde se determinará el pivote. Inicialmente izq = 0 y der = L.Longitud()
Método:
Inicio
entero i, j;
entero pos_pivote;
T pivote;
pivote <--L.SeleccionPivote(izq, der);
pos_pivote <--L.Buscar(pivote);
i <--izq; j <-- der;
mientras (i < j) hacer
inicio
mientras (L[i] < pivote) hacer
i <--i + 1;
mientras (L[j] > pivote) hacer
j <--j - 1;
si ( i < j) entonces
inicio
L.Intercambiar(i, j);
i <-- i + 1;
j <-- j – 1;
fin
fin
L.Intercambiar(i, pos_pivote); //Posiciona el pivote en la
//posición que le corresponde en
//la lista ordenada
si (izq < i-1) entonces QuickSort(L, izq, i-1);
si (der > i+1) entonces QuickSort(L, i+1, der);
Fin
Ejemplo:
Para este ejemplo supongamos que la lista es L = (5, 3, 7, 6, 2, 1, 4). Tomemos como pivote el último elemento.
Comenzamos con la lista completa. El elemento pivote será el 4:
5 - 3 - 7 - 6 - 2 - 1 - 4
Comparamos con el 5 por la izquierda y el 1 por la derecha.
5 - 3 - 7 - 6 - 2 - 1 - 4
5 es mayor que cuatro y 1 es menor. Intercambiamos:
1 - 3 - 7 - 6 - 2 - 5 - 4
Avanzamos por la izquierda y la derecha:
1 - 3 - 7 - 6 - 2 - 5 - 4
3 es menor que 4: avanzamos por la izquierda. 2 es menor que 4: nos mantenemos ahÃ.
1 - 3 - 7 - 6 - 2 - 5 - 4
7 es mayor que 4 y 2 es menor: intercambiamos.
1 - 3 - 2 - 6 - 7 - 5 - 4
Avanzamos por ambos lados:
1 - 3 - 2 - 6 - 7 - 5 - 4
En este momento termina el ciclo principal, porque los Ãndices se cruzaron. Ahora intercambiamos el 4 con el 6.
1 - 3 - 2 - 4 - 7 - 5 - 6
Aplicamos recursivamente a la sublista de la izquierda (Ãndices 0 - 2). Tenemos lo siguiente:
1 - 3 - 2
1 es menor que 2(elemento pivote): avanzamos por la izquierda. 3 es mayor: avanzamos por la derecha. Como se intercambiaron los Ãndices termina el ciclo. Se intercambia el 3 con el 2
1 - 2 - 3
Al llamar recursivamente para cada nueva sublista tenemos que tienen un solo elemento por lo que se retorna sin hacer cambios.
Segunda sublista:
7 - 5 - 6
5 - 7 - 6
5 - 6 - 7
Para cada nueva sublista se retorna sin hacer cambios (se cruzan los Ãndices).
Finalmente, al retornar de la primera llamada se tiene la lista ordenado:
1 - 2 - 3 - 4 - 5 - 6 - 7
Este método toma cada elemento de la lista a ordenar y lo compara con los que se encuentran en posiciones anteriores a la de él dentro de la lista. Si el elemento con el que se está comparando es mayor que el elemento a ordenar, se recorre hacia la siguiente posición superior. Si por el contrario, resulta que el elemento con el que se está comparando es menor que el elemento a ordenar, se detiene el proceso de comparación pues se encontró que el elemento ya está ordenado y se coloca en su posición (que es la siguiente a la del último número con el que se comparó).
28.3.2.1 Algoritmo
Algoritmo 28.2: Insertion-Sort.
Inicialización.
- Sea L una lista de elementos de tipo T.
Método:
Inicio
entero i, j;
T aux;
desde i <-2 hasta L.Longitud() con paso 1
inicio
aux <-- L[i]
j <-- i
mientras (j-1 > 1) y (aux < L[j-1])
inicio
L[j] <-- L[j-1] //Equivalente a
// T temp = L[j-1]
// L.Eliminar(i); L.Insertar(temp, i);
j <-- j-1
fin
L[j] <--aux //Equivalente a
// L.Eliminar(j); L.Insertar(aux, j);
fin
Fin
Ejemplo:
Supongamos que la lista L es una lista de enteros y L = (4, 3, 5, 2, 1).
En la primera iteración del ciclo externo, cuando i = 2, tenemos la siguiente situación:
aux = 3, L = (4, 3, 5, 2, 1)
La idea de este algoritmo es examinar los elementos que están antes de un elemento pivote (aux). Los elementos mayores que el elemento pivote se desplazan a una posición posterior. Se detiene este proceso cuando se encuentra un elemento menor que el elemento pivote. Luego, el elemento pivote (aux) se coloca en la posición donde se detuvo este proceso.
Es por eso que:
aux = 3  L = (4, 4, 5, 2, 1) Pues 4 > aux
 L = (3, 4, 5, 2, 1) Se llegó al principio de la lista,
se coloca aux en la posición donde
se detuvo el proceso
Luego, se toma como pivote, el elemento que está en la tercera posición, es decir, aux = 5. De entrada 5 > 4, es decir, el elemento pivote es mayor que el elemento que le antecede. Por tanto, no suceden cambios en la lista.
Tomando ahora el elemento que está en la cuarta posición como pivote, tenemos:
aux = 2  L = (3, 4, 5, 5, 1) Pues 5 > aux
 L = (3, 4, 4, 5, 1) Pues 4 > aux
 L = (3, 3, 4, 5, 1) Pues 3 > aux
 L = (2, 3, 4, 5, 1) Se llegó al principio de la lista,
se coloca aux en la posición donde
se detuvo el proceso
El mismo proceso se harÃa para aux = 1, por lo que al finalizar el método, la lista L quedarÃa ordenada de forma ascendente.
28.3.3 Método Quick-Sort
Vimos que en un algoritmo de ordenamiento por intercambio, son necesarios intercambios de elementos en sublistas hasta que no son posibles más intercambios. En el Bubble-Sort, son comparados elementos correlativos en cada paso de la lista. Por lo tanto para ubicar un elemento en su correcta posición, pueden ser necesarios varios intercambios.
Veremos el ordenamiento que sigue el método de intercambio y fue desarrollado por C.A.R. Hoare: Quicksort. Es más eficiente que el bubblesort porque los intercambios involucran elementos que están más apartados, entonces menos intercambios son requeridos para poner un elemento en su posición correcta.
La idea básica del algoritmo es elegir un elemento llamado pivote, y ejecutar una secuencia de intercambios tal que todos los elementos menores que el pivote queden a la izquierda y todos los mayores a la derecha. Lo único que requiere este proceso es que todos los elementos a la izquierda sean menores que el pivote y que todos los de la derecha sean mayores luego de cada paso, no importando el orden entre ellos, siendo precisamente esta flexibilidad la que hace eficiente al proceso.
Se hacen dos búsquedas, una desde la izquierda y otra desde la derecha, comparando el pivote con los elementos que se van recorriendo, buscando los menores o iguales y los mayores respectivamente. Ese pivote no necesariamente (casi nunca) va a estar en el centro del arreglo.
El algoritmo sigue los pasos esenciales de la estrategia recursiva ‘Divide y Vencerás’.
Divide la lista en dos partes, hace la llamada recursiva a cada una de las partes hasta ordenar todos los elementos.
28.3.3.1 Algoritmo
Algoritmo 28.3: Quick-Sort.
Inicialización.
- Sea L una lista de elementos de tipo T.
- Sean izq y der dos valores enteros que indican las posiciones extremas que definen la sublista de donde se determinará el pivote. Inicialmente izq = 0 y der = L.Longitud()
Método:
Inicio
entero i, j;
entero pos_pivote;
T pivote;
pivote <--L.SeleccionPivote(izq, der);
pos_pivote <--L.Buscar(pivote);
i <--izq; j <-- der;
mientras (i < j) hacer
inicio
mientras (L[i] < pivote) hacer
i <--i + 1;
mientras (L[j] > pivote) hacer
j <--j - 1;
si ( i < j) entonces
inicio
L.Intercambiar(i, j);
i <-- i + 1;
j <-- j – 1;
fin
fin
L.Intercambiar(i, pos_pivote); //Posiciona el pivote en la
//posición que le corresponde en
//la lista ordenada
si (izq < i-1) entonces QuickSort(L, izq, i-1);
si (der > i+1) entonces QuickSort(L, i+1, der);
Fin
Ejemplo:
Para este ejemplo supongamos que la lista es L = (5, 3, 7, 6, 2, 1, 4). Tomemos como pivote el último elemento.
Comenzamos con la lista completa. El elemento pivote será el 4:
5 - 3 - 7 - 6 - 2 - 1 - 4
Comparamos con el 5 por la izquierda y el 1 por la derecha.
5 - 3 - 7 - 6 - 2 - 1 - 4
5 es mayor que cuatro y 1 es menor. Intercambiamos:
1 - 3 - 7 - 6 - 2 - 5 - 4
Avanzamos por la izquierda y la derecha:
1 - 3 - 7 - 6 - 2 - 5 - 4
3 es menor que 4: avanzamos por la izquierda. 2 es menor que 4: nos mantenemos ahÃ.
1 - 3 - 7 - 6 - 2 - 5 - 4
7 es mayor que 4 y 2 es menor: intercambiamos.
1 - 3 - 2 - 6 - 7 - 5 - 4
Avanzamos por ambos lados:
1 - 3 - 2 - 6 - 7 - 5 - 4
En este momento termina el ciclo principal, porque los Ãndices se cruzaron. Ahora intercambiamos el 4 con el 6.
1 - 3 - 2 - 4 - 7 - 5 - 6
Aplicamos recursivamente a la sublista de la izquierda (Ãndices 0 - 2). Tenemos lo siguiente:
1 - 3 - 2
1 es menor que 2(elemento pivote): avanzamos por la izquierda. 3 es mayor: avanzamos por la derecha. Como se intercambiaron los Ãndices termina el ciclo. Se intercambia el 3 con el 2
1 - 2 - 3
Al llamar recursivamente para cada nueva sublista tenemos que tienen un solo elemento por lo que se retorna sin hacer cambios.
Segunda sublista:
7 - 5 - 6
5 - 7 - 6
5 - 6 - 7
Para cada nueva sublista se retorna sin hacer cambios (se cruzan los Ãndices).
Finalmente, al retornar de la primera llamada se tiene la lista ordenado:
1 - 2 - 3 - 4 - 5 - 6 - 7