MÉTODOS DE ORDENAMIENTO INTERNO (EN MEMORIA PRINCIPAL)
Para todos los algoritmos se cuenta con la siguiente estructura de datos
Const MAX = 100
A = arreglo[1..MAX] de enteros
Variable N:entero
ORDENAMIENTO DIRECTO. MÉTODO DE BURBUJA.
Ordena los elementos del arreglo usando el método de burbuja. Transporta en cada pasada el elemento más pequeño a la parte izquierda del arreglo A de N elementos.
Burbuja1(A,N)
Inicio
Declarar i,j,aux:entero
Para iß 2 hasta N haga
Para j ß i hasta 2 inc (–1) haga
Si (A[j-1]>A[j]) entonces
Aux ß A[j-1]
A[j-1] ß A[j]
A[j] ß aux
Fin si
Fin para
Fin para
Fin
ORDENAMIENTO DIRECTO. METODO DE LA BURBUJA. CONTRARIO AL ANTERIOR.
La lógica de este algoritmo cambia con el anterior, en el hecho de que en cada pasada se lleva el valor mas grande a hacia la parte derecha del arreglo A de N elementos.
Burbuja2(A,N)
Inicio
Declarar i,j,aux:entero
Para iß 1 hasta N-1 haga
Para j ß 1 hasta N-i haga
Si (A[j]>A[j+1]) entonces
Aux ß A[j]
A[j] ß A[j+1]
A[j+1] ß aux
Fin si
Fin para
Fin para
Fin
ORDENAMIENTO DIRECTO CON SEÑAL
Algoritmo que usa el principio de ordenamiento del método de la burbuja, usando una señal para saber si en cada pasada hubo intercambios. Arreglo A de N elementos enteros.
Burbujaconseñal(A, N)
Inicio
Declarar i,j,aux:entero
Declarar band:booleano
i ß 1
Band ß FALSO
Mientras Que (i<= N-1) y (band = FALSO) haga
Band ß VERDADERO
Para j ß 1 hasta N-i haga
Si (A[j]>A[j+1]) entonces
Aux ß A[j]
A[j] ß A[j+1]
A[j+1] ß aux
Band ß FALSO
Fin si
Fin para
Fin MQ
Fin
ORDENAMIENTO POR EL MÉTODO DE LA SACUDIDA (SHAKER SORT)
Este método es una optimización del método de la burbuja. Consiste en mezclar las dos formas como se puede realizar el método de ordenamiento directo. En cada pasada hay dos etapas, el la primera etapa se trasladan los elementos más pequeños hacia la izquierda almacenando en una variable el último elemento intercambiado. En la segunda etapa, se trasladan los elementos más grandes hacia la parte derecha del arreglo almacenando en otra variable la posición del último elemento intercambiado.
Algoritmo que ordena los elementos del arreglo A, de N elementos, por el método de la sacudida.
Shakersort(A,N)
Inicio
Declarar i, izq, der, k, aux: entero
izq ß 2
der ßN
k ß N
Repetir
Para i ß der hasta izq inc (-1) haga
Si (A[i-1]>A[i]) entonces
Aux ß A[i-1]
A[i-1] ß A[i]
A[i] ß aux
k ß i
Fin si
Fin para
Izq ß k + 1
Para i ß izq hasta der haga
Si (A[i-1] > A[i]) entonces
Aux ß A[i-1]
A[i-1] ß A[i]
A[i] ß Aux
k ß i
Fin si
Fin para
Der ß k-1
Hasta que izq>der
Fin
MÉTODO DE ORDENAMIENTO POR INSERCIÓN DIRECTA
El objetivo de este método es copiar la forma como los jugadores de cartas ordenan la baraja en una mano. El objetivo de este método es insertar un elemento en la parte izquierda del arreglo que ya se encuentra ordenada. El proceso se repite desde el segundo hasta el n-esimo elemento.
Algoritmo que ordena los elementos del arreglo usando el método de inserción directa. Arreglo A de N elementos.
insercion(A,N)
Inicio
Declarar i, aux, k: entero
Para i ß 2 hasta N haga
Aux ß A[i]
k ß i-1
Mientras Que ((k>=1) y (aux
k ß k -1
Fin MQ
A[k+1] ß aux
Fin para
Fin
ORDENAMIENTO POR MÉTODO DE INSERCIÓN BINARIA
Es una mejora del método de inserción directa, ya que se hace una búsqueda binaria en lugar de una búsqueda secuencial para insertar el elemento a la izquierda del arreglo, que ya se encuentra ordenado. Y el proceso se repite hasta el n-esimo elemento.
Algoritmo que ordena los elementos del arreglo usando el método de inserción binara. Arreglo A de N elementos.
insercionbinaria(A,N)
Inicio
Declarar i, aux, izq, der, m, j: entero
Para i ß 2 hasta N haga
Aux ß A[i]
Izq ß 1
Der ß i-1
Mientras Que (izq<=der) haga
m ß parteentera((izq+der)/2)
Si (aux <= A[m]) entonces
Der ß m-1
Sino
Izq ß m+1
Fin si
Fin MQ
j ß i-1
Mientras Que (j>=izq) haga
A[j+1] ß A[j]
j ß j-1
Fin MQ
A[izq] ß aux
Fin para
Fin
ORDENAMIENTO POR SELECCIÓN DIRECTA
La idea de este algoritmo es buscar el menor elemento del arreglo y colocarlo en la primera posición, luego se busca el segundo elemento más pequeño del arreglo y se coloca en la segunda posición y así. El algoritmo se basa en:
1. Seleccionar el menor elemento del arreglo.
2. Intercambiar dicho elemento con el primero.
3. Repetir los pasos anteriores con los (n-1), (n-2)... elementos y así sucesivamente hasta que solo quede el elemento mayor.
Algoritmo que ordena los elementos de un arreglo usando el método de selección directa. A arreglo de N elementos.
seleccion(A,N)
Inicio
Declarar i, menor, k, j: entero
Para i ß 1 hasta N-1 haga
Menor ß A[i]
k ß i
Para j ß i+1 hasta N haga
Si (A[j]
k ß j
Fin si
Fin para
A[k] ß A[i]
A[i] ß menor
Fin para
Fin
ORDENAMIENTO CON EL MÉTODO DE SHELL (INSERCIÓN CON INCREMENTOS DECRECIENTES)
Este algoritmo compara cada elemento del arreglo para su ubicación correcta, con los elementos que se encuentran en la parte izquierda del mismo. Este método propone que las comparaciones entre los elementos se efectúen con saltos de mayor tamaño, pero con incrementos decrecientes.
Algoritmo que ordena los elementos de un arreglo usando el método de shell. A arreglo de N elementos.
shell(A,N)
Inicio
Declarar int, i, aux: entero
Declarar band: booleano
Int ß N+i
Mientras Que (int>1) haga
int ß parteentera(int/2)
band ß VERDADERO
Mientras Que (band=VERDADERO) haga
Band ß FALSO
i ß 1
Mientras Que ((I+int)<=N) haga
Si (A[i]>A[i+int]) entonces
aux ß A[i]
A[i] ß A[i+int]
A[i+int] ß aux
Band ß VERDADERO
Fin si
i ß i+1
Fin MQ
Fin MQ
Fin MQ
Fin
ORDENAMIENTO POR EL MÉTODO DE QUICKSORT (MÉTODO RÁPIDO DE ORDENACIÓN POR PARTICIÓN)
Este algoritmo es el mas eficiente y veloz de los métodos de ordenación interna. La idea central del algoritmo es:
1. Se toma un elemento X de una posición cualquiera del arreglo
2. Se trata de ubicar a X en la posición de correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a X y todos los elementos que se encuentran a su derecha sean mayores o iguales a X.
3. Se repiten los pasos anteriores, pero con los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición correcta de X en el arreglo.
4. El proceso termina cuando todos los elementos se encuentran en su posición correcta en el arreglo.
El paso 3 se puede hacer de forma iterativa o recursiva. En este ejemplo, se hará de forma iterativa, dejando el método recursivo para más adelante en el curso.
Se necesitan dos algoritmos. Quicksortitera y reduceitera.
Algoritmo que ordena los elementos de un arreglo A de N elementos, usando el método Quicksort iterativo.
Quicksortitera(A, N)
Inicio
Declarar top, ini, fin, pos: entero
Pilamayor: Arreglo[1..MAX] de entero
Pilamenor: Arreglo[1..MAX] de entero
Top ß 1
Pilamenor[top] ß 1
Pilamayor[top] ß N
Mientras Que (top>0) haga
Ini ß pilamenor[top]
Fin ß pilamayor[top]
Top ß top-1
Pos ß Reduceitera(ini, fin)
Si (ini<(pos-1)) entonces
Top ß top+1
Pilamenor[top] ß ini
Pilamayor[top] ß pos-1
Fin si
Si (fin>(pos+1)) entonces
Top ß top+1
Pilamenor[top] ß pos+1
Pilamayor[top] ß fin
Fin si
Fin MQ
Fin
Reduceitera(INI, FIN)
/* INI y FIN representa las posiciones de los extremos izquierdo y derecho respectivamente del conjunto de elementos a evaluar. En POS es una variable donde se almacenará el resultado de este algoritmo */
Inicio
Declarar izq, der, aux, pos: entero
Declarar band: booleano
Izq ß ini
Der ß fin
Pos ß ini
Band ß VERDADERO
Mientras Que (band=VERDADERO) haga
Mientras Que ((A[pos]<=A[der]) y (pos<>der)) haga
der ß der-1
Fin MQ
Si (Pos=der) entonces
Band ß FALSO
Sino
Aux ß A[pos]
A[pos] ß A[der]
A[der] ß aux
Pos ß der
Mientras Que ((A[pos]>=A[izq])y(pos<>izq)) haga
Izq ß izq+1
Fin MQ
Si (pos=izq) entonces
Band ß Falso
Sino
Aux ß A[pos]
A[pos] ß A[izq]
A[izq] ß aux
Pos ß izq
Fin si
Fin si
Fin MQ
Retornar Pos
Fin
MÉTODOS DE BÚSQUEDA INTERNA (BÚSQUEDA EN MEMORIA PRINCIPAL)
Para todos los algoritmos se cuenta con la siguiente estructura de datos
Const MAX = 100
V = arreglo[1..MAX] de enteros
Variable N:entero
Existen 4 métodos principales de búsqueda interna:
• Secuencial líneal
• Binaria
• Por transformación de Claves (Solo se menciona, después se añadirán los algoritmos)
• Árboles de búsqueda (no se tratan aquí)
BÚSQUEDA SECUENCIAL LINEAL.
Consiste en la revisión elemento por elemento del arreglo hasta encontrar el dato buscado, o hasta llegar al final del arreglo, sin haberlo encontrado. Se puede diferenciar entre buscar en un arreglo desordenado y buscar en un arreglo ordenado.
Búsqueda en arreglos desordenados
Algoritmo que busca secuencialmente el elemento X en el arreglo desordenado V, con N elementos.
Secuencialdesordenado(V, N, X)
Inicio
Declarar i:entero
Declarar bandera: booleano
i ß 1
Bandera ß FALSO
Mientras Que ((i<=N) y (Bandera=FALSO)) haga
Si (V[i]=X) entonces
Bandera ß VERDADERO
Sino
i ß i+1
Fin si
Fin MQ
Si (bandera=VERDADERO) entonces
Imprimir(“El elemento está en la posición i”);
Sino
Imprimir(“El elemento no está en el arreglo”)
Fin si
Fin
Búsqueda en arreglos ordenados
Este algoritmo es similar al anterior, pero se agrega una nueva condición basada en el orden de los elementos. Busca secuencialmente un elemento X en un arreglo ordenado V de N elementos. El orden de V es creciente. {V[1]≤V[2] ≤...≤V[N]}
Secuencialordenado(V, N, X)
Inicio
Declarar i:entero
Declarar bandera: booleano
i ß 1
Bandera ß FALSO
Mientras Que ((i<=N) y (Bandera=FALSO) y (X>=V[i]) haga
Si (X=V[i]) entonces
Bandera ß VERDADERO
Sino
i ß i+1
Fin si
Fin MQ
Si (bandera=VERDADERO) entonces
Imprimir(“El elemento está en la posición i”);
Sino
Imprimir(“El elemento no está en el arreglo”)
Fin si
Fin
BÚSQUEDA BINARIA
La búsqueda binaria, sirve exclusivamente para arreglos ordenados, consiste en dividir el intervalo de búsqueda en dos partes, comparando el elemento buscado con el central, , en caso de no ser iguales se redefinen los extremos del intervalo (según si el elemento central es mayor o menor que el buscado). El proceso termina cuando se encuentra el elemento o cuando se anula el intervalo de búsqueda.
Algoritmo que busca el elemento X mediante búsqueda binaria en el arreglo ordenado V con N elementos.
binaria(V, N, X)
Inicio
Declarar izq, cen, der: entero
Declarar bandera: booleano
Izq ß 1
Der ß N
Bandera ß FALSO
Mientras Que ((izq<=der) y (Bandera=FALSO)) haga
Cen ß parteentera((izq+der)/2)
Si (X=V[cen]) entonces
Bandera ß VERDADERO
Sino
Si (X>V[cen]) entonces
izq ß cen+1
Sino
der ß cen-1
Fin si
Fin si
Fin MQ
Si (bandera=VERDADERO) entonces
Imprimir(“El elemento está en la posición cen”);
Sino
Imprimir(“El elemento no está en el arreglo”)
Fin si
Fin
No hay comentarios:
Publicar un comentario