MÉTODOS DE ORDENAMIENTO INTERNO (EN MEMORIA PRINCIPAL)

  Para todos los algoritmos se cuenta con la siguiente estructura de datos  Const MAX = 100A = arreglo[1..MAX] de enterosVariable 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 paraFin

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 paraFin

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 MQFin

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>derFin

METODO 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<A[k])) haga                                   A[k+1] A[k]                                   k k -1                        Fin MQ                        A[k+1] aux            Fin paraFin

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 paraFin

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]<menor) entonces                                               Menor A[j]                                               k j                                   Fin si                        Fin para                        A[k] A[i]                         A[i] menor             Fin paraFin

 

COMPARACIÓN DE LOS MÉTODOS DIRECTOS DE ORDENAMIENTO

Método item Ordenada Desordenada Orden Inverso

IntercambioDirecto

comp.

Mov 0

InserciónDirecta

comp.

Mov 0

SelecciónDirecta

comp.

Mov 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 MQFin

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 MQFin

 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 PosFin

Arriba    Presentación

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 = 100V = arreglo[1..MAX] de enterosVariable 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 desordenadosAlgoritmo 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 siFin

Búsqueda en arreglos ordenadosEste 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 siFin

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 siFin

 

MÉTODO DE TRANSFORMACIÓN DE CLAVES

Este método permite asignar a un valor una posición determinada de un arreglo (no necesariamente secuencial y a veces independiente de su valor) y de igual forma permite recuperarla fácilmente. Presenta dos momentos principales. El primero consiste en la aplicación de una función de transformación o función hash a los valores que se van a insertar, para saber en que posición del arreglo quedarán. La función hash debe ser simple de calcular y debe asignar direcciones de la manera mas uniforme posible. La segunda alivia el hecho de que dos valores distintos sean asignados a la misma dirección del arreglo por causa de la función hash, hecho que se conoce como colisión. Es decir, el segundo momento es la recuperación de colisiones y consiste en como reasignar y recuperar un valor que por motivo de la función hash quede en la misma posición de otro. Para asignar funciones hash, existen varios métodos:Función módulo: Consiste en tomar el residuo de la división de la clave entre el número de componentes del arreglo. H(k) = (K mod N) +1. Para lograr una mayor uniformidad en la distribución, N debe ser un número primo. (El número primo próximo a N).Función cuadrado: Consiste en elevar al cuadrado la clave y tomar los dígitos centrales como dirección. H(k) = digitos_centrales(K2)+1.Función plegamiento:  Consiste en dividir la clave en partes de igual número de dígitos (La última puede tener menos dígitos) y operar con ellos tomando como dirección los dígitos menos significativos. La operación entre las partes puede hacerse por medio de sumas o multiplicaciones. H(k) = digitos_menos_significativos((d1..di)+(di+1..dj)+...+(dl..dn))+1Función Truncamiento: Consiste en tomar algunos de la clave y formar con ellos una dirección. Este método es de los más sencillos, pero es también de los que ofrece menos uniformidad en la distribución de las claves. Se pueden elegir los dígitos de las posiciones pares o impares. H(k) = elegirdigitos(d1,d2,...,dn)+1El método de resolución de colisiones es tan importante como la elección de una buena función hash. El tratamiento de las colisiones es costoso, por esto, es que debe hacerse un esfuerzo por encontrar una función hash que ofrezca mayor uniformidad en la distribución de las claves. Los métodos de solución de colisiones son también variados:Reasignación:   Se trabaja bajo el principio de comparación y reasignación de elementos.          Prueba lineal: Consiste en que una vez detectada la colisión se debe recorrer el arreglo

secuencialmente a partir del punto de la colisión, buscando el elemento. El proceso de búsqueda concluye cuando el elemento es hallado, o bien cuando se encuentra una posición vacía. Se trata el arreglo como una estructura circular. Algoritmo que  busca el dato con clave K en el arreglo V de N elementos. Resolución de colisiones  por medio de la prueba lineal.        

Pruebalineal(V, N, K) Inicio             Declarar D, Dx: entero                         D H(K)  /* Generar dirección */             Si (V[D]=K) entonces                         Imprimir “El elemento está en la posición D”             Sino                         Dx D+1                         Mientras Que ((Dx<=N) y (V[Dx]<>K) y (V[Dx]<>vacio) y (Dx<>D)) haga                                    Dx Dx+1                                     Si (Dx=(N+1)) entonces                                                Dx 1                                     Fin si                         Fin MQ                         Si (V[Dx]=K) entonces                                     Imprimir(“El elemento está en la posición Dx”)                         Sino                                     Imprimir(“El elemento no está en el arreglo”)                         Fin si             Fin si Fin

             Prueba Cuadrática: Similar al de prueba lineal. La diferencia consiste en que en el cuadrático

las direcciones alternativas se generarán como D+1, D+4, D+9,…, D+i2. Algoritmo que  busca el dato con clave K en el arreglo V de N elementos. Resolución de colisiones  por medio de la prueba lineal.

Pruebacuadratica(V, N, K) Inicio             Declarar D, Dx, i: entero                         D H(K)  /* Generar dirección */             Si (V[D]=K) entonces                         Imprimir “El elemento está en la posición D”             Sino                         i1                                         Dx D+i2                         Mientras Que ((V[Dx]<>K) y (V[Dx]<>vacio)) haga                                    i i+1                                    Dx D+i2                                     Si (Dx>N) entonces                                                i 0                                                 Dx 1                                                D 1                                     Fin si                         Fin MQ                         Si (V[Dx]=K) entonces

                                   Imprimir(“El elemento está en la posición Dx”)                         Sino                                    Imprimir(“El elemento no está en el arreglo”)                         Fin si             Fin si Fin

            Doble dirección hash: Consiste en que una vez detectada la colisión se debe generar otra

dirección aplicando la función hash a la dirección previamente obtenida. El proceso se detiene cuando el elemento es hallado, o cuando se encuentra una posición vacía. D = H(K)  D’ = H(D)   D”= H(D’) Algoritmo que  busca el dato con clave K en el arreglo V de N elementos. Resolución de colisiones  por medio de la prueba lineal.

Dobledireccion(V, N, K) Inicio             Declarar D, Dx: entero                         D H(K)  /* Generar dirección */             Si (V[D]=K) entonces                         Imprimir “El elemento está en la posición D”             Sino                         Dx H’(D)                         Mientras Que ((Dx<=N) y (V[Dx]<>K) y (V[Dx]<>vacio) y (Dx<>D)) haga                                    Dx H’(Dx)                         Fin MQ                         Si (V[Dx]=K) entonces                                    Imprimir(“El elemento está en la posición Dx”)                         Sino                                    Imprimir(“El elemento no está en el arreglo”)                         Fin si             Fin si Fin

 

Arreglos anidados: Consiste en que cada elemento del arreglo tenga otro arreglo con el cual se almacenan los elementos colisionados. Es una solución sencilla, pero ineficiente. No se analizará por ahora. Encadenamiento: Consiste en que cada elemento del arreglo tenga un apuntador a una lista encadenada, la cual se irá generando e irá almacenando los valores colisionados a medida que se requiera. Es el método más eficiente, pero no se analizará por ahora.