Métodos de Ordenamiento

Ordenamiento: Es la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento. El ordenamiento se efectúa con base en el valor de algún campo en un registro. El propósito principal de un ordenamiento es el de facilitar las búsquedas de los miembros del conjunto ordenado.

El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia tal que represente un orden, el cual puede ser numérico, alfabético o incluso alfanumérico, ascendente o descendente.

Tipos de ordenamiento:

Los 2 tipos de ordenamientos que se pueden realizar son: los internos y los externos.  

• Los internos: Son aquellos en los que los valores a ordenar están en memoria principal, por lo que se asume que el tiempo que se requiere para acceder cualquier elemento sea el mismo (a[1], a[500], etc).

•  Los externos: Son aquellos en los que los valores a ordenar están en memoria secundaria (disco, cinta, cilindro magnético, etc), por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la última posición accesada (posición 1, posición 500, etc). 

Algoritmos de ordenamiento:

Internos:

• Inserción directa.

o       Inserción directa.

o       Inserción binaria.

• Selección directa.

o       Selección directa.

• Intercambio directo.

o       Burbuja.

o       Shake.

• Inserción disminución incremental.

o       Shell.

• Ordenamiento de árbol.

o       Heap.

o       Tournament.

• Sort particionado.

o       Quick sort.

• Merge sort.

• Radix sort.

• Cálculo de dirección.

Externos:

• Straight merging.

• Natural merging.

• Balanced multiway merging.

• Polyphase sort.

• Distribution of initial runs.

Algunos de los métodos de ordenamiento mencionados son:

ORDENAMIENTO EN TARJETAS PERFORADAS

El ordenamiento de tarjetas perforadas fue el primer tipo de algoritmo de ordenamiento que existió. Hoy en día prácticamente no es utilizado debido a que existen otros métodos de ordenamiento más efectivos, más rápidos y cuya complejidad es menor. Ejemplo es el algoritmo  quicksort , que es considerado hoy por hoy el más eficiente de los métodos de ordenamiento de vectores y matrices.
A continuación presentamos este método de ordenamiento, que fué utilizado para ordenar tarjetas perforadas.
 

Algoritmo.

funcion radix (int p, int q[ ])
{
  int  m[50][9], v[9], pas, i, j, k, x;
  para  ( pas = 1; pas <=3; pas + + )
           {
             para  (i=0 ; i<=9; v[i++]=0)
                      {
                        for  ( k=1; k<=p; k++)
                               {
                                 x = q [k];
                                 para ( i = 1 ; i<= paz ; i + + )
                                          {
                                            j = x %10;                          /* x mod 10 */
                                            x = x / 10;
                                           }
                                 v [ j ] + = 1 ;
                                 m [ v [ j ] [ j ] ] = q [ k ];
                                }
                        k = 1;
                        para ( i = 0 ; i < = 9 ; i + + )
                                {
                                  para ( j = 1 ; j < = v [ i ] ; j + + )
                                           {
                                             q [ k + +] = m [ j ] [ i ];
                                            }
                                 }
                       }
           }
}
 
 

Nota: Este método de ordenamiento es un poco 'ARCAICO' en comparación con los otros métodos de ordenamiento que se encuentran a continuacion, sin embargo, vale la pena rescatarlo, ya que prácticamente se podría decir que este algoritmo es el padre de los métodos de ordenamiento que conocemos actualmente..
 

MÉTODO DE LA BURBUJA

 El ordenamiento burbuja es quizá el método de ordenamiento de vectores más conocido por los programadores. Existen diferentes tipos de ordenamiento burbuja. A continuación se presenta uno de ellos: 

El método burbuja:

Este tipo de ordenamiento se basa fundamentalmente en un ordenamiento de tipo ascendente. Como su nombre lo indica, todo el ordenamiento es basado en una especie de inserción y el comportamiento interno del vector es como el de una burbuja. Se basa en dos apuntadores y en una variable auxiliar. En un inicio, un apuntador inicial 'x' empieza a recorrer el vector desde la posición inicial (en nuestro caso la llamaremos uno, pero para C++ será la posición cero) hasta la posición anterior a la final, y un apuntador 'y' que recorrerá el vector desde la posición  ' i +1 '  hasta la posición final, siendo esta un valor conocido anteriormente (N). Estos apuntadores recorrerán el vector e irán comparando los valores de la posición en que se encuentra cada uno y si el valor de la  posición  V[ i ]  es mayor que el de la posición V[ j ], intercambiarán sus valores utilizando la ayuda de la variable auxiliar (aux).
 

/ * Algoritmo  * /

para ( i = 1 ; i < N ; i + + )
        {
          para ( j = i + 1 ; j <= N ; j + + )
                  {
                     si ( V [ i ] > V [ j ] )
                        {
                          aux = V [ i ];
                          V [ i ] = V [ j ];
                          V [ j ] = aux;
                         }
                    }
         }
 

Tiempo de ejecución del algoritmo burbuja:

Para el mejor caso (un paso) O(n)

Peor caso n(n-1)/2

Promedio O(n²)

ORDENAMIENTO QUICKSORT 

Método Quicksort: 

El ordenamiento quicsort está basado en el principio de guerra "DIVIDE Y VENCERÁS". Este procedimiento es en realidad muy sencillo y se desarrolla así:

La idea principal es dividir la lista en dos sub-listas y ordenarlas en forma independiente cada una. El proceso de partición es
repetido hasta llegar a listas de tamaño 1 (que están ordenadas).

Lo central en este método es encontrar un método eficiente para particionar la lista en dos partes, tal que:

     Todos los elementos de una sub-lista deben ser menores que un elemento llamado pivote.
     Todos los elementos en la otra sub-lista deben ser mayores que el pivote.

Si asumimos que los elementos de la lista están almacenados en un arreglo, el método para particionar el arreglo en dos es
como sigue:

1. Escoja un elemento en el arreglo como pivote. Por conveniencia, usaremos el primer elemento del arreglo.

2. Ponga un índice al segundo elemento del arreglo (i1) y otro al último elemento (i2).

3. Decremente i2 hasta que encuentre un elemento con valor menor que el pivote o i2 llegue a i1. Incremente i1 hasta que encuentre un elemento mayor que el pivote o hasta que i1 llegue a i2. Llamaremos a este proceso "búsqueda".

4. Si los dos índices son distintos, los dos elementos del arreglo (los apuntados por i2 e i1) están fuera de lugar, por lo que se intercambian. Repita el paso anterior de búsqueda, resumiendo la operación donde se había quedado. 

5. Si los dos índices son iguales y el valor que ambos índices apuntan es menor que el pivote, intercámbielos. El arreglo está ahora particionado por el elemento referenciado por i2 (o i1).

     La localización del pivote separa el arreglo en una porción donde todos sus valores son menores que el pivote, y otra
     porción donde todos sus valores son mayores que el pivote.

Ejemplo: Tomemos como ejemplo una lista con 8 elementos para estudiar el algoritmo de partición. Estos elementos de la lista están desordenados así:    65, 70, 50, 85, 55, 80, 45, 90   respectivamente.

Usamos el primer elemento como pivote, 65, y realizamos el proceso de búsqueda con i1 igual a 1 e i2 igual a 7 (70 y 90).
Recuérdese que el arreglo parte de 0. Decrementamos i2 a 6 y paramos, ya que 45 es menor que el pivote, 65. De acuerdo a
lo antes definido, los intercambiamos. Con esto, la lista queda:

     65 45 50 85 55 80 70 90

Retomamos el proceso de búsqueda desde las posiciones 1 y 6, y paramos en 3 y 4; intercambiamos.

     65 45 50 55 85 80 70 90

El proceso de búsqueda es retomado y termina con los dos índices en 3, elemento que es intercambiado por el pivote:

     55 45 50 65 85 80 70 90

Por último, esta lista se particiona tomando el pivote original (65), obteniendo las dos siguientes sublistas:

     55 45 50

     85 80 70 90

Obsérvese que el pivote es mayor que todos los elementos de la primera sub-lista y menor que todos los elementos de la
segunda sub-lista. En este punto, ambos arreglos serán ordenados en forma recursiva, es decir, se repetirá el mismo procedimiento para cada una de las sub-listas.
 

 MÉTODO DE INSERCIÓN DIRECTA

Ordenamiento por inserción directa: La idea central de este algoritmo consiste en insertar un elemento del arreglo en la parte izquierda del mismo, que ya se encuentra ordenada . Este procedimiento se repite desde el segundó hasta el último término. Veamos el algoritmo:

/* algoritmo */

INSERCIÓN (A, N)
{
 para (i=2 hasta N)
         {
           aux = A[i];
           k=I-1;
           mientras ((aux=1))
                         {
                           A[k+1]=A[k];
                            k=k-1;
                          }
           si (A[k]<=aux)
              {
                A[k+1]=aux;
               }
           si no
                 {
                   A[k+1]=A[k];
                   A[k]=aux;
                 }
         }
}
 

MÉTODO DE  INSERCIÓN BINARIA

 El método de ordenación por 'inserción binaria'' es una mejora del método de  inserción directa . Como se dijo, el método de ordenamiento por inserción binaria es una mejora del ordenamiento por inserción directa. Para lograr esta mejora se recurre a una búsqueda binaria en lugar de una búsqueda secuencial para insertar un elemento en la parte izquierda del arreglo, que ya se encuentra ordenado. El resto del procedimiento es similar al de inserción directa, es decir, se repite este mismo procedimiento desde el segundo término hasta el último elemento. Veamos el algoritmo:
 

/* algoritmo */

INSERCION BINARIA (A, N)
{
 para (i=2 hasta N)
         {
           aux = A[i];
           izq=1;
           der=i-1;
           mientras (izq<=der)
                         {
                            m=[parte entera ((izq+der)/2)];
                            si (aux                                {
                                 der=m-1;
                                }
                            si no
                                  {
                                    izq=m+1;
                                   }
                         }
           j=i-1;
           mientras (j>=izq)
                         {
                           A[j+1]=A[j];
                           j=j-11;
                          }
          A[izq]=auz;
}

MÉTODO POR  SELECCIÓN DIRECTA

El método de ordenamiento por selección directa no es muy recomendable utilizarlo cuando el número de elementos del arreglo es grande. La idea básica de este algoritmo es la misma que la del burbuja. Buscar el menor elemento del arreglo y lo coloca en la primera posición. Luego el segundo en la segunda y así hasta terminar de recorrer el arreglo.
 

/* algoritmo */

SELECCION (A, N)
{
 para (i=1 hasta N)
        {
          menor=A[i];
          k=I;
          para (j=I+1 hasta N)
                  {
                    si (A[j]                         {
                          menor=A[j];
                          k=j;
                         }
                  }
          A[k]=A[i];
          A[i]=menor;
        }
}

Los métodos a continuación descritos son algunos de los mas  recientes:

MÉTODO DE JSORT

JSORT es un subproducto de JCAT V1.1 o  JCATSORT V1.1.

JSORT  es rápido como relámpago. Utiliza un método modificado del quicksort y maneja un fichero 63kB en un dígito binario concluido 3 segundos (en mi 16MHz 286 con un 65ms Harddisk) cuando la CLASE que vino con el DOS pasa 1 minuto 28 segundos que pasan a través del fichero. 

No debe haber ficheros de clase con  líneas de  más  de 80 caracteres. Porque JSORT no hace caso de los extremos de las líneas más allá de 80 columnas que usted terminará para arriba con algo más que con qué usted comenzó. 

Su uso es realmente algo simple. Si va algo mal JSORT le deja saber sobre él y sale del proceso.

MÉTODO SWAP

Para sustituir las paginaciones o los segmentos de datos en memoria. Este metodo es  una técnica útil que permite a un ordenador ejecutar programas y manipular memoria más en gran parte que principal de los ficheros de datos

. El sistema operativo copia tantos datos como posible en memoria principal, y deja el resto en el disco. Cuando el sistema operativo necesita datos del disco, intercambia una porción de datos (llamados una paginación o un segmento) en memoria principal por una porción de datos sobre el disco.

 El DOS no realiza el intercambio, sino la mayoría de los otros sistemas operativos, incluyendo OS/2, Windows, y UNIX, .

El intercambio a menudo se llama paginación. 

- En los sistemas de UNIX, intercambiando refiere a procesos enteros de mudanza dentro y fuera de memoria principal.

 -Cuando INTERCAMBIO deletreado, siglas para el protocolo sin hilos compartido del acceso

Diccionario

http://www.webopedia.com/

Autor: Raiger Murillo Moreno

Email: [email protected]

Ingeniero de Sistemas

http://www.lafacu.com/apuntes/informatica/algorit_ordena/default.htm