martes, 26 de noviembre de 2013

Métodos de ordenamiento - Estructura de Datos


¿Qué es la ordenación? 

Ordenar significa reagrupar o reorganizar un conjunto de datos u objetos en una secuencia especifica, la cual puede ser de dos formas distintas:

-       Ascendente (menor a mayor) o
-       Descendente (mayor a menor).

 Los métodos de ordenación se clasifican en dos categorías:

-       Ordenación interna (de arreglos) y
-       Ordenación externa (de archivos).

La ordenación interna o de arreglos, recibe este nombre ya que los elementos o componentes del arreglo se encuentran en la memoria principal de la computadora.
Los métodos de ordenación interna a su vez se clasifican en:
-       Métodos directos (n2) y
-       Métodos logarítmicos (n * log n).



Los métodos directos, son los más simples y fáciles de entender, son eficientes cuando se trata de una cantidad de datos pequeña. Los métodos logarítmicos, son más complejos, difíciles de entender y son eficientes en grandes cantidades de datos.
Los métodos directos más conocidos son:
-       Ordenación por intercambio.
-       Ordenación por inserción.
-       Ordenación por selección.

La ordenación por intercambio consiste en comparar dos elementos del arreglo y determinar si existe un intercambio entre ellos, para esto debe definirse el tipo de ordenamiento que se quiere ya sea ascendente o descendente.
Los algoritmos de ordenación directa por intercambio que se analizaran son:
-       El método de la burbuja.
-       El método quicksort.
-       El método shellsort.

Burbuja.- 


Ejemplo del ordenamiento de burbuja ordenando una lista de números aleatorios.

El método de ordenación por intercambio directo o método de la burbuja, es el más simple y consiste en comparar dos elementos adyacentes para determinar si se realiza un intercambio entre los mismos, esto en caso de que el primero sea mayor que el segundo (forma ascendente) o el caso de que el primero sea menor que el segundo (forma descendente).

El primer procedimiento del método de la burbuja es:
  1. Generar un ciclo que inicie desde uno hasta el número de elementos del arreglo.
  2. Generar un segundo ciclo dentro del anterior que inicie desde cero hasta el número de elementos del arreglo menos dos.
  3. Dentro del segundo ciclo debe existir una comparación que determina el tipo de ordenamiento (ascendente o descendente) entre el primer elemento (posición generado por el segundo ciclo) y el segundo elemento (el que le  sigue), si la respuesta a la condición es verdadera se realiza un intercambio entre los dos elementos.
  4. Para realizar el intercambio se genera un almacenamiento temporal, el cual guarda el dato del primer elemento, el segundo elemento toma el lugar del primero y en el lugar del segundo se coloca lo que contiene el almacenamiento temporal.

Una vez que los ciclos terminan la estructura debe quedar ordenada de forma ascendente o descendente, pero este procedimiento es considerado como el pero de los casos ya que si el número de elementos de la estructura es de 100, se tienen que realizar 9900 comparaciones entes de terminar la ejecución del método.
Un segundo procedimiento del método de la burbuja es:
  1. Generar un ciclo que inicie desde cero hasta el número de elementos menos dos.
  2. Generar un segundo ciclo desde el valor del ciclo anterior mas uno hasta el número de elementos menos uno;
  3. Dentro del segundo ciclo debe existir una comparación que determina el tipo de ordenamiento (ascendente o descendente) entre el primer elemento (posición generada por el primer ciclo) y el segundo elemento (posición generada por el segundo ciclo), si la respuesta a la condición es verdadera se realiza un intercambio entre los dos elementos.
  4. Para realizar el intercambio se genera un almacenamiento temporal, el cual guarda el dato del primer elemento, el segundo elemento toma el lugar del primero y en el lugar del segundo se coloca lo que contiene el almacenamiento temporal.

Una vez que los ciclos terminan la estructura debe quedar ordenada, la diferencia con el procedimiento anterior radica en el número de comparaciones y posibles intercambios que se presentan, en este segundo procedimiento, es menor ya que cada pasada que se le da al arreglo se realiza una comparación menos que en la pasada anterior.
Un tercer procedimiento del método de la burbuja es el siguiente:
  1. Generar un ciclo que inicie desde uno hasta el número de elementos menos uno.
  2. Generar un segundo ciclo que inicie desde el número de elementos menos uno y mientras que ese valor sea mayor o igual al del ciclo anterior (con decrementos).
  3. Dentro del segundo ciclo debe existir una comparación que determina el tipo de ordenamiento (ascendente o descendente) entre el primer elemento (posición generada por el segundo ciclo) y el segundo elemento (posición generada por el segundo ciclo menos uno), si la respuesta a la condición es verdadera se realiza un intercambio entre los dos elementos.
  4. Para realizar el intercambio se genera un almacenamiento temporal, el cual guarda el dato del primer elemento, el segundo elemento toma el lugar del primero y en el lugar del segundo se coloca lo que contiene el almacenamiento temporal

Este tercer procedimiento es muy similar al anterior con la diferencia que el elemento que va quedando es su lugar el primero no el último como en el caso anterior.

QuickSort.-

El método de ordenamiento rápido o método quicksort, es una técnica basada en otra conocida con el nombre divide y vencerás, que permite ordenar una cantidad de elementos en un tiempo proporcional a n2 en el peor de los casos o a n log n en el mejor de los casos. El algoritmo original es recursivo, como la técnica en la que se basa.
La descripción del algoritmo para el método de ordenamiento quicksort es la siguiente:
  1. Debe elegir uno de los elementos del arreglo al que llamaremos pivote.
  2. Debe acomodar los elementos del arreglo a cada lado del pivote, de manera que del lado izquierdo queden todos los menores al pivote y del lado derecho los mayores al pivote; considere que en este momento, el pivote ocupa exactamente el lugar que le corresponderá en el arreglo ordenado.
  3. Colocado el pivote en su lugar, el arreglo queda separado en dos subarreglos, uno formado por los elementos del lado izquierdo del pivote, y otro por los elementos del lado derecho del pivote.
  4. Repetir este proceso de forma recursiva para cada subarreglo mientras éstos contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Para elegir un pivote se puede aplicar cualquiera de las siguientes tres opciones:
  1. El pivote será el primer elemento del arreglo,
  2. El pivote será el elemento que esta a la mitad del arreglo, o
  3. Que el pivote se elija de entre tres elementos del arreglo (cualesquiera), los cuales se deben comparar para seleccionar el valor intermedio de los tres y considerarlo como el pivote.

La forma o técnica de reacomodo de los elementos del lado izquierdo y derecho del pivote, aplica el siguiente procedimiento que es muy efectivo. Se utilizan dos índices: izq, al que llamaremos índice inicial, y der, al que llamaremos índice final. Conociendo estos elementos el algoritmo quedaría de la siguiente manera:
  1. Recorrer el arreglo simultáneamente con izq y der: por la izquierda con izq (desde el primer elemento), y por la derecha con der(desde el último elemento).
  2. Mientras el arreglo en su posición izq (arreglo[izq]) sea menor que el pivote, continuamos el movimiento a la derecha.
  3. Mientras el arreglo en su posición der (arreglo[der]) sea mayor que el pivote, continuamos el movimiento a la izquierda.
  4. Terminando los movimientos se compara los índices y si izq es menor o igual al der, se intercambian los elementos en esas posiciones y las posiciones se cambian izq a la derecha y der a la izquierda.
  5. Repetir los pasos anteriores hasta que se crucen los índices (izq sea menor o igual a der).
  6. El punto en que se cruzan los índices es la posición adecuada para colocar el pivote, porque sabemos que a un lado los elementos son todos menores y al otro son todos mayores (o habrían sido intercambiados).

ShellSort.-

El método de ordenación shellsort es una versión mejorada del método de ordenación por inserción directa, que se utiliza cuando el número de elementos es grande. Este método recibe su nombre gracias a su creados Donald L. Shell, también se conoce con el nombre inserción con incrementos decrecientes.
En el método de ordenación por inserción directa, cada elemento se compara con los elementos contiguos de su izquierda de uno por uno, para lograr su ordenamiento; si por ejemplo, el elemento a comparar  es el más pequeño y se encuentra en la última posición del arreglo, hay que ejecutar muchas comparaciones antes de colocar el elemento en su lugar de forma definitiva.
El método de ordenación shellsort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga pasos más grandes hacia la posición que debe ocupar. Los pasos múltiples sobre los elementos se hacen con tamaños de espacio cada vez más pequeños y el último paso del método es un simple ordenamiento por inserción directa, pero para entonces, los elementos de arreglo ya casi están ordenados.
Para determinar el tamaño de los incrementos (saltos) constantes, el primero debe ser generado a partir del tamaño del arreglo entre dos, obteniendo solo su parte entera de la división o redondeando el resultado de la misma, y posteriormente ir reduciendo a la mitad el incremento en cada repetición, hasta que el incremento sea un uno.

 
public static void main(String [] args) {
    //arreglo
    int Entrada[] = {
        321, 123, 213, 234, 1, 4, 5, 6, 21, 15
    };
    //llamada
    shellSort(Entrada);
    for (int i = 0; i < Entrada.length; i++) {
        System.out.print(Entrada[i]+" ");
    }
 }
 
 public static void shellSort( int vec[]) {
    // saltos 
    for( int p = vec.length / 2; p > 0; p = p == 2 ? 1 : (int) ( p / 2.2 ) ) {
        for( int i = p; i < vec.length; i++) {
            int tmp = vec[i];
            int j;
            for(j = i; j >= p && tmp < vec[j - p]; j -= p ) {
                vec[j] = vec[j - p];
            }
            vec[j] = tmp;
        }
    }
 }


El procedimiento para aplicar el algoritmo de shellsort es el siguiente:

  1. Generar un ciclo que se encargue de controlar el tamaño que deben tener los incrementos.
    1. Este ciclo debe iniciar con la división del tamaño del arreglo entre dos.
    2. Mientras que el incremento sea mayor a cero debe continuar.
    3. Y el cambio de incremento se elige de entre dos opciones: un uno o la división del incremento anterior entre dos.

  1. Un segundo ciclo dentro del anterior, controla el número de comparaciones que se deben hacer según el tamaño del incremento.
    1. El control de este ciclo debe iniciar con el incremento generado anteriormente.
    2. Mientras el control del ciclo sea menor que el tamaño del arreglo.
    3. El control debe cambiar de uno en uno.

  1. Un tercer ciclo dentro del segundo controla en que momento se detienen las comparaciones o se hacen los posibles intercambios entre los elementos.
    1. El control de este ciclo debe iniciar con el valor del ciclo anterior.
    2. Mientras que el control sea mayor o igual al incremento del primer ciclo y el elemento del arreglo de la posición del control de este ciclo menos el incremento, sea mayor que el elemento del arreglo de la posición control de este ciclo, realice los intercambios entre estas posiciones.
    3. Y el control se decremente con el valor del incremento.

Algoritmos de ordenamiento por distribución.- 

Los algoritmos de ordenamiento por distribución, ordenan el arreglo tomando cada número e insertándolo en la posición que toma su valor, es decir, si se tiene un cinco se coloca en la posición cinco del arreglo, algo así como: “lo que valgas en esa posición te pongo”. Esto indica que no se podrán ordenar los arreglos que tengan valores repetidos y el arreglo necesita el tamaño del número más grande que se encuentre en él.
Lo que debemos hacer cuando se repitan los datos es incrementar la capacidad de la posición (urna). Para lograrlo podemos hacer lo siguiente:
  1. Definir un arreglo en el que cada posición puede ser ocupada por más de un elemento (arreglo bidimensional) puede darse la situación de ser insuficiente la cantidad de posiciones adicionales o de existir demasiado desperdicio de memoria.
  2. Definir el tamaño de la urna variable a través del uso de estructuras de datos como las listas simples enlazadas.
Los algoritmos de ordenamiento por distribución se clasifican en:
-       CountingSort.
-       RadixSort.
-       BucketSort.

Radix.-

El método de ordenación radix es un algoritmo que ordena datos procesando sus elementos de forma individual, según la posición que ocupan dentro del dato. Los datos numéricos los por dígitos y los datos alfabéticos por letras.

El método radix se clasifica en dos tipos según el orden en el que procesan los datos:
-       De derecha a izquierda y
-       De izquierda a derecha.

Si aplicamos este método solo a enteros, el método se clasificaría de la siguiente manera:

-       El digito menos significativo (LSD, Least Significat Digit) y
-       El digito más significativo (MSD, More Significat Digit).

El radix LSD procesa los enteros iniciando por el digito menos significativo y moviéndose al digito más significativo (de derecha a izquierda).
El radix MSD procesa los enteros iniciando por el digito más significativo y moviéndose al digito menos significativo (de izquierda a derecha).
El método más aplicado de radix, es el LSD, y se encarga de colocar los números en una de las 10 colas que representan un digito cada una de ella, iniciando desde la cola que controla el digito 0 hasta la cola que controla el digito 9, en estas colas se colocan los números dependiendo del digito que se este analizando en ese momento, hasta que termine con el número que contenga la mayor cantidad de dígitos, en cada cambio de digito los elementos se integran al arreglo nuevamente desde la cola 0 hasta la cola 9, para elegir el siguiente digito de ordenamiento. Cuando se efectúa este proceso para cada dígito  al arreglo  está ordenado.



El procedimiento para aplicar el algoritmo de radix es el siguiente: 

  1. Determinar cuál es la mayor cantidad de dígitos del elemento mayor del arreglo.
  2. Crear un arreglo de colas, que permita almacenar cana uno de los dígitos del 0 al 9.
  3. Crear cada posición del arreglo como un objeto que permita almacenar los elementos en cada cola, según el índice que le corresponde.
  4. Generar un ciclo que determine el número de digito que se esta procesando y el factor que permite encontrar el digito.
    1. Inicializar el número de digito y el factor en uno;
    2. Mientras el digito sea menor o igual a la cantidad de dígitos encontrados en le paso uno.
    3. El número de digito se debe incrementar de uno en uno.

  1. Crear un segundo ciclo que se encuentra dentro del anterior y que se encarga de recorrer todo el arreglo desde la posición inicial hasta la final del arreglo.
    1. Iniciar el control del ciclo en cero.
    2. Mientras el control sea menor al tamaño del arreglo, continuamos en el ciclo.
    3. El control del ciclo se cambia de uno en uno.

  1. Generar un segundo ciclo que se encuentra dentro del primero, al igual que el anterior y este controla el paso de los elementos de las colas al arreglo nuevamente.
    1. El control de este ciclo inicia desde la cola cero, al igual que el índice que controla el arreglo de los elementos.
    2. Mientras el control sea menor a diez continua dentro del ciclo.
    3. El control del ciclo se incrementa de uno en uno.

  1. Dentro del ciclo anterior se genera otro ciclo que se encarga de colocar el contenido de cada cola dentro del arreglo original y su condición es que mientras la cola no este vacía retire los elementos guardándolos en el arreglo e incrementar el índice que controla el arreglo.

Ordenamientos con las clases Arrays y Collections de la librería java.util.
Java ofrece dos versiones de métodos de ordenación: por arreglos (clase Arrays) y por listas (clase Collections).
La clase Arrays incluye métodos para procesar arreglos, en particular, métodos para ordenar, buscar, llenar y transformar un arreglo a una lista. Todos los métodos de ordenación en Arrays implementan una versión del algoritmo de ordenación rápida (quicksort); cada método sea plica a cada tipo definido por java a excepción del tipo boolean. Para cada tipo hay dos versiones, una para ordenar el arreglo completo y otra para ordenar solo una parte del arreglo.

 La sintaxis de cada versión es la siguiente:
            Arrays.sort(tipo[ ]_arreglo);
            Arrays.sort(tipo[ ]_arreglo, int_inicio, int_fin);

La clase Collections incluye métodos para procesar listas enlazadas, dichos métodos permiten ordenar, buscar, copiar, entre otro métodos. El método de ordenación implementado en esta clase es el megasort y puede aplicarse a estructuras de tipo Vector,ArrayLista y LinkedList. Está clase se compone de dos métodos para el ordenamiento cuya sintaxis es la siguiente:
            Collections.sort(lista);
            Collections.sort(lista, Comparator comp);

Funcionamiento de los algoritmos de ordenamiento

Quick sort.-

Dados los siguientes números
Para implementar este método se debe de recibir como argumentos el vector con los números, la posición inicial y la posición final del vector (vec, inicio(0),final(9)).  Las posiciones recibidas de inicio y final se deben de respaldar porque sus valores van  cambiar durante la ejecución del método. Los respaldos los llamaremos Izq y Der donde Izq tiene el valor recibido en inicio y Der el valor recibido de final. Estas variables se representan en el vector siguiente como las posiciones inicial y final del vector respectivamente. También se debe de sacar un pivote que esta dado por la suma de la posición inicial, final y dividida entre dos.

Izq=0;inicio=0;
Der=9;final=9;
Pospivote=(inicio+final)/2=(0+9)/2=4;
Pivote=vec[Pospivote]=vec[4]=70

pos
0
1
2
3
4
5
6
7
8
9
valores
10
80
50
95
70
5
95
17
87
65

Izq



Pivote




Der
Paso 1:             Incrementar Izq mientras que  el valor que se encuentra en la posición Izq sea menor que el pivote (se busca tener todos los números menores del lado izq del pivote) 

pos
0
1
2
3
4
5
6
7
8
9
valores
10
80
50
95
70
5
95
17
87
65


Izq


Pivote




Der
Paso 2:             Decrementar Der mientras que  el valor que se encuentra en la posición Der sea mayor que el pivote (se busca tener todos los números menores del lado izq del pivote)

pos
0
1
2
3
4
5
6
7
8
9
valores
10
80
50
95
70
5
95
17
87
65


Izq


Pivote




Der
Paso 3:             Como ya no se cumplen los pasos anteriores entonces se intercambian los números a los que apuntan Izq y Der (ya que el que apunta izquierda es mayor que pivote y viceversa el número que apunta derecha es menor que pivote) esto solo se realiza si Izq es menor o igual que Der (Izq<=Der), además se incrementa Izq y se decrementa Der.

pos
0
1
2
3
4
5
6
7
8
9
Valores
10
65
50
95
70
5
95
17
87
80



Izq

Pivote



Der




Paso 4:           Se repite el paso 1,2,3 mientras que Izq sea menor o igual que Der Izq<=Der.
                       
                        Repetición paso 1
pos
0
1
2
3
4
5
6
7
8
9
valores
10
65
50
95
70
5
95
17
87
80




Izq
Pivote




Der

                        Repetición paso 2
pos
0
1
2
3
4
5
6
7
8
9
valores
10
65
50
95
70
5
95
17
87
80




Izq
Pivote


Der


                        Repetición paso 3: intercambio
                       
pos
0
1
2
3
4
5
6
7
8
9
valores
10
65
50
17
70
5
95
95
87
80





Izq Pivote

Der




                        Repetición paso 1:
                       
pos
0
1
2
3
4
5
6
7
8
9
valores
10
65
50
17
70
5
95
95
87
80





Izq Pivote

Der




                        Repetición paso 2:
                       
pos
0
1
2
3
4
5
6
7
8
9
Valores
10
65
50
17
70
5
95
95
87
80





Izq Pivote
Der




                        Repetición paso 3: Intercambiar
                       
pos
0
1
2
3
4
5
6
7
8
9
valores
10
65
50
17
5
70
95
95
87
80





Der Pivote
Izq





Ya no se cumple el paso 4 por lo que se avanza al paso cinco: Ya tenemos del lado izquierdo todos los números menores a 70 y del lado derecho los mayores a 70.

Paso 5: Llamar de manera recursiva a el mismo método solo si inicio<Der  enviando el vector,inicio,Der. (Se están enviando los valores menores al pivote).

Paso 6: Llamar de manera recursiva a el mismo método solo si Izq<final  enviando el vector,Izq,final. (Se están enviando los valores mayores al pivote).

Se repiten los pasos 1,2,3,4 con las dos partes enviadas.



Shellsort.-

Para implementar este método se debe de recibir el vector y con el ya se obtiene el tamaño del vector.
En este método se utiliza un intervalo que se calcula con el tamaño del vector dividido entre 2, de tal forma que el intervalo da la mitad del vector y se comparan los números de la posición 0, con el de la posición obtenida de intervalo, si el primero es menor que el segundo se intercambian, y se avanza al siguiente par (posición 1 con posición del intervalo mas 1) y así sucesivamente.
Paso 1: Calcular el intervalo Interv=tam_vec/2;  Interv=8/2=4
Paso 2: Se compara la posición 0 con la posición 4 y si el primero es mayor que el segundo se intercambian.
pos
0
1
2
3
4
5
6
7
valores
20
66
2
26
48
3
60
8

c



c



Paso 2: Se compara la posición 1 con la posición 5 y si el primero es mayor que el segundo se intercambian.
pos
0
1
2
3
4
5
6
7
valores
20
66
2
26
48
3
60
8


C



c


                       
pos
0
1
2
3
4
5
6
7
valores
20
3
2
26
48
66
60
8



c



c

Paso 3: Se compara la posición 2 con la posición 6 y si el primero es mayor que el segundo se intercambian.

pos
0
1
2
3
4
5
6
7
valores
20
3
2
26
48
66
60
8



c



c

Paso 4: Se compara la posición 3 con la posición 7 y si el primero es mayor que el segundo se intercambian.
pos
0
1
2
3
4
5
6
7
valores
20
3
2
26
48
66
60
8




c



c

pos
0
1
2
3
4
5
6
7
valores
20
3
2
8
48
66
60
26









Paso 5: Se vuelve a calcular el intervalo pero ahora con el calculado anteriormente entre dos. Interv=4/2=2.
Paso 6: Se compara la posición 0 con la posición 2, 1 con 3,2 con 4,3 con 5,4 con 6 y así sucesivamente  y si el primero es mayor que el segundo se intercambian.
pos
0
1
2
3
4
5
6
7
valores
20
3
2
8
48
66
60
26

c

c






pos
0
1
2
3
4
5
6
7
valores
2
3
20
8
48
66
60
26


c

c






                                  
pos
0
1
2
3
4
5
6
7
valores
2
3
20
8
48
66
60
26



c

c



                                  
                                  
pos
0
1
2
3
4
5
6
7
valores
2
3
20
8
48
66
60
26




c

c


                       
pos
0
1
2
3
4
5
6
7
valores
2
3
20
8
48
66
60
26





c

c


pos
0
1
2
3
4
5
6
7
valores
2
3
20
8
48
66
60
26






c

c

pos
0
1
2
3
4
5
6
7
valores
2
3
20
8
48
26
60
66









Paso 5: Se vuelve a calcular el intervalo pero ahora con el calculado anteriormente entre dos. Interv=2/2=1.
Paso 6: Se compara la posición 0 con la posición 1, 1 con 2,2 con 3,3 con 4,4 con 5 y así sucesivamente  y si el primero es mayor que el segundo se intercambian.
pos
0
1
2
3
4
5
6
7
valores
2
3
20
8
48
26
60
66

c
c







pos
0
1
2
3
4
5
6
7
valores
2
3
20
8
48
26
60
66


c
c






pos
0
1
2
3
4
5
6
7
valores
2
3
8
20
48
26
60
66



C
c





pos
0
1
2
3
4
5
6
7
valores
2
3
8
20
48
26
60
66




c
c




pos
0
1
2
3
4
5
6
7
valores
2
3
8
20
48
26
60
66





c
c



pos
0
1
2
3
4
5
6
7
valores
2
3
8
20
26
48
60
66





c
c



pos
0
1
2
3
4
5
6
7
valores
2
3
8
20
26
48
60
66






c
c



pos
0
1
2
3
4
5
6
7
valores
2
3
8
20
26
48
60
66







c
c

Radix.-
 Este método permite ordenar los números a través de los dígitos que contienen los números utilizar estructuras dinámicas (colas).

pos
0
1
2
3
4
5
6
7
valores
125
7
58
17
5
328
168
218









Paso 1: Checar el último digito de cada número y ponerlo en la columna correspondiente (cola) a su valor.
pos
0
1
2
3
4
5
6
7
valores
125
7
58
17
5
328
168
218
                                   
Dígitos
d0
d1
d2
d3
d4
d5
d6
d7
d8
d9






125

7
58







5

17
328










168










218

 Paso 2:  Se sacan cada uno de los valores de las colas y se almacenan en el vector a partir de la cola cero.

pos
0
1
2
3
4
5
6
7
valores
125
5
7
17
58
328
168
218
 Se checa el segundo dígito más a la izquierda de los números y se almacenan en su cola respectiva a su valor, los que no tienen digito se almacenan en la cero.

Dígitos
d0
d1
d2
d3
d4
d5
d6
d7
d8
d9

5
17
125


58
168




7
218
328







 Paso 3:  Se sacan cada uno de los valores de las colas y se almacenan en el vector a partir de la cola cero.

Pos
0
1
2
3
4
5
6
7
valores
5
7
17
218
125
328
58
168
 Se checa el segundo dígito más a la izquierda de los números y se almacenan en su cola respectiva a su valor, los que no tienen digito se almacenan en la cero.

Dígitos
d0
d1
d2
d3
d4
d5
d6
d7
d8
d9

5
125
218
328







7
168









17










58









 Paso 3:  Se sacan cada uno de los valores de las colas y se almacenan en el vector a partir de la cola cero.

Pos
0
1
2
3
4
5
6
7
valores
5
7
17
58
125
168
218
328

Como ya no se tienen más dígitos se termina con el proceso y ya quedan ordenados.



Archivos de acceso directo.-
   Son aquellos que permiten posicionamiento dentro del archivo, es decir se puede posicionar el puntero del fichero dentro del archivo. Por ejemplo en las cuentas de banco solo se puede acceder a cuentas particulares que corresponden a la posición dentro del archivo.
  Constructores:
–        RandomAccessFile(File objFile, String Acceso) throws IOException
–        RandomAccessFile(String nomFile, String Acceso) throws IOException
 La primera forma, objFile indica el nombre del archive que se a abrir como objeto File. En la segunda forma se pasa el nombre del archivo en nomFile. En ambos casos, Acceso determina qué tipo de acceso al fichero esta permitido. Si es r (read), el fichero se puede leer, pero no escribir. Si es rw (read-write), entonces el fichero se abre en modo de lectura-escritura.
Método
Descripción
void close( )
Cierra el archivo y libera los recursos asociados.
long getFilePointer( )
Proporciona el desplazamiento actual de la posición de lectura/escritura del archivo.
long length( )
Devuelve la longitud del archivo en bytes.
int read( )
Lee un byte
int read(byte b[ ])
Lee hasta b.length bytes del archivo
boolean readBoolean( )
byte  readByte( )
Char, Double, Float ,Int , Long, Short,                
 Lee los diferentes tipos de datos del archivo (booleanos, byte, char, double, float, int, etc…);
String readLine( )
Lee un String
void write(int b )
Escribe un byte
void write(byte b[])
Escribe un arreglo de bytes
void writeBoolean(boolean v)
 Char, Double, Float, Int, Long, Short, Chars

void seek(long Nuevapos)
Sitúa el puntero en la posición pos
void setLength(long longitud)
Establece un nuevo tamaño de fichero.
int skipBytes(int v)
Trata de saltar v bytes en el archivo.
El método seek(long Nuevapos) thows IOException  buscar, se usa para establecer la posición actual del puntero dentro del fichero.
Aquí, en Nuevapos especifica la nueva posición, en bytes, del puntero del archivo desde el principio de este.


Ordenación externa.

La ordenación externa o de archivos, recibe este nombre ya que los elementos se encuentran almacenados en un archivo, el cual se almacena en un dispositivo de almacenamiento secundario o externo.

Algoritmos de ordenación externa.

Los algoritmos de ordenación externa son necesarios cuando los datos que se quiere ordenar no cabe en la memoria principal (RAM) de la computadora y por tal motivo se encuentran almacenados en un dispositivo secundario externo (el disco duro, cinta, memoria usb, etc.). La mayoría de estos algoritmos utilizan la técnica de divide y vencerás y la intercalación de archivos, para aplicar el ordenamiento.
Por intercalación de archivos se entiende la unión o fusión de dos o más archivos, previamente ordenados, en un solo archivo, el cual debe quedar ordenado al hacer la intercalación.
Si se cuenta con dos archivos con datos previamente ordenados, el proceso de intercalación entre los dos archivos, consiste en extraer el primer elemento de cada archivo y determinar cuál es el menor, para colocarlo en el tercer archivo, extraer el siguiente elemento del archivo y compararlo nuevamente contra el otro elemento que ya se tenia del otro archivo, para determinar cuál ingresa al tercer archivo, este proceso se repita hasta que uno de los archivos originales llegue hasta el fin, en este caso, solo resta transcribir los números del archivo que no se ha llegado a su fin al tercer archivo.
Los algoritmos de ordenación externa más comunes son dos:
-       Intercalación directa o mezcla directa y 
-       Mezcla natural o mezcla equilibrada.

 Intercalación directa.-

La intercalación directa o mezcla directa es un algoritmo de ordenación externa, que permite organizar los elementos de un archivo, de forma ascendente o descendente.
 La idea centrar de este algoritmo consiste en realizar de forma sucesiva una partición y una fusión que produce secuencias ordenadas de longitud cada vez mayor. En la primera pasada la partición es de longitud 1 y la fusión produce secuencias ordenadas de longitud 2. En la segunda pasada la partición es de longitud 2 y la fusión produce secuencias ordenadas de longitud 4. Este proceso se repite hasta que la longitud de la partición sea menor o igual al número de elementos del archivo original.
Ejemplo. Considere el archivo F con los elementos 324, 230, 942, 700, 714, 139, 6, 915, 890 y 717, y los archivos auxiliares F1 y F2. El proceso de ordenamiento según la descripción del algoritmo anterior seria:
F:         324, 230, 942, 700, 714, 139, 6, 915, 890, 717                    T.  Partición:   1
Partición:Se construye tomando un número para cada una de las particiones
F1:       324, 942, 714, 6, 890
F2:       230, 700, 139, 915, 717
Fusión: Se fusionan las dos particiones comparando el menor de la partición va primero
F:         230, 324, 700, 942, 139, 714, 6, 915, 717, 890                    T.  Partición:   2
Partición: Se construye tomando dos números para cada una de las particiones
F1:       230, 324, 139, 714, 717, 890
F2:       700, 942, 6, 915
Fusión:
F:         230, 324, 700, 942, 6, 139, 714, 915, 717, 890                    T.  Partición:   4
Partición:
F1:       230, 324, 700, 942, 717, 890
F2:       6, 139, 714, 915
Fusión:
F:         6, 139, 230, 324, 700, 714, 915, 942, 717, 890                    T.  Partición:   8
Partición:
F1:       6, 139, 230, 324, 700, 714, 915, 942
F2:       717, 890
Fusión:
F:         6, 139, 230, 324, 700, 714, 717, 890, 915, 942        

 Mezcla natural.-

La mezcla natural o mezcla equilibrada es un algoritmo de ordenación externa, que se encarga de organizar los elementos de un archivo de forma ascendente o descendente.
La idea central de este algoritmo consiste en realizar particiones tomando secuencias ordenadas de máxima longitud en lugar de secuencias ordenadas de tamaño fijo previamente determinadas, como la intercalación directa. Posteriormente se realiza la fusión de esas secuencias ordenadas, alternándolas entre los dos archivos auxiliares. Repitiendo este proceso, se logra que el archivo quede completamente ordenado. Para aplicar este algoritmo, se necesitarán cuatro archivos. El archivo original y tres archivos auxiliares. De estos cuatro archivos, dos serán considerados de entrada y dos de salida, alternativamente en cada paso del algoritmo. El proceso termina cuando al finalizar un paso, el segundo archivo de salida quede vacío y el primero queda completamente ordenado.

Ejemplo.- 

Considere el archivo F con los elementos 324, 230, 942, 700, 714, 139, 6, 915, 890 y 717, y los archivos auxiliares F1, F2 y F3. El proceso de ordenamiento según el algoritmo anterior seria:

F:         324, 230, 942, 700, 714, 139, 6, 915, 890, 717
Partición inicial
F1:       324, 700, 714, 6, 915, 717
F2:       230, 942, 139, 890
Fisión-Partición
F:         230, 324, 700, 714, 942
F3:       6, 139, 890, 915, 717
Fisión-Partición
F1:       6, 139, 230, 324, 700, 714, 890, 915, 942
F2:       717

Fisión-Partición
F:         6, 139, 230, 324, 700, 714, 717, 890, 915, 942
F3:       (sin elementos)

Otra alternativa de solución a este algoritmo, es un procedimiento que solo utiliza tres archivos: el archivo original y dos auxiliares, el primer proceso consiste en dividir el archivo original en dos, colocando secuencias ordenadas de máxima longitud en cada uno de los auxiliares, una secuencia a la vez en cada auxiliar; el siguiente proceso consiste en hacer una fusión de los dos auxiliares colocando los elementos en el archivo original, con secuenciar ordenadas de máxima longitud, extraídas de los dos archivos auxiliares. Estos dos pasos se repiten mientras que el segundo archivo auxiliar sea diferente de cero.

Ejemplo. 

Considere el archivo F con los elementos 324, 230, 942, 700, 714, 139, 6, 915, 890 y 717, y los archivos auxiliares F1 y F2. El proceso de ordenamiento según la descripción del algoritmo anterior seria:
 F:         324, 230, 942, 700, 714, 139, 6, 915, 890, 717

Partición: Se crea con una intercalación (Se almacenan en la primera partición mientras sean mayores y se pasa a la segunda partición cuando sea menor y se siguen almacenando mientras sean mayores)

F1:       324, 700, 714, 6, 915, 717
F2:       230, 942, 139, 890
Fisión:  Se aplica una intercalación 
F:         230, 324, 700, 714, 6, 915, 717, 942, 139, 890
Partición
F1:       230, 324, 700, 714, 717, 942
F2:       6, 915, 139, 890
 Fisión
F:         6, 230, 324, 700, 714, 717, 915, 139, 890, 942
Partición
F1:       6, 230, 324, 700, 714, 717, 915
F2:       139, 890, 942
Fisión
F:         6, 139, 230, 324, 700, 714, 717, 890, 915, 942
Falta otra pasada y F2 se queda sin valores.



Publicadas por a la/s No hay comentarios.:
Suscribirse a: Entradas (Atom)