Unidad V Métodos de ordenamiento

5.1 Algoritmos de Ordenamiento Internos
5.1.1 Burbuja.
5.1.2 Quicksort.
5.1.3 ShellSort.
5.1.4 Radix
5.2 Algoritmos de ordenamiento Externos
5.2.1 Intercalación
5.2.2 Mezcla Directa
5.2.3 Mezcla Natural

Animación de algunos argoritmos de ordenamiento
http://luda.uam.mx/CursoPoo/curso_poo_10.html#01

Ordenación interna.

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.

Algoritmos de ordenamiento por intercambio.

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.

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.

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.
  2. 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.


Ejercicios

Ordenar por el método de la burbuja, quicksort, shellsort 10 nombres que se encuentran desordenados en un vector de cadenas.

Ordenar 10 números almacenados en un vector de cadenas a través del método radix

Ordenar 10 registros ordenados que contienen num_tarjeta y el nombre a través de intercalación Sencilla.

Ordenar 10 registros desordenados que contienen num_tarjeta y el nombre a través de Mezcla natural.











Comments