UNIDAD IV MÉTODOS DE ORDENAMIENTO

4.1 ALGORITMOS DE ORDENAMIENTO

Introducción

Ordenamiento

¿Qué es ordenamiento?

Es la operación que coloca los datos en un orden secuencial, basándose en un criterio de ordenamiento.
El ordenamiento se efectúa en base al valor del dato

¿Cuándo es conveniente usar un método de ordenamiento

1. Cuando se requiere hacer una cantidad considerable de búsquedas

 

  2.  Y cuando es importante el factor tiempo.

Tipos de ordenamiento

• 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).

• 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).

Método Burbuja

Historia

Determinar con exactitud el origen del ordenamiento burbuja es un poco complicado, ya que no existe información precisa sobre su origen.

Aunque en 1956 se encuentra expresado en un artículo al que lo llamaron "Ordenamiento por intercambio".

Existe una amplia bibliografía de artículos del año 1962 donde mencionan tipos de ordenamiento basados en este patrón, pero ninguno de ellos usando el nombre como tal.

Ventajas 

• Bastante sencillo y más utilizado por su fácil comprensión y programación.
• Código reducido.
• Eficaz.

Desventajas

• Consume bastante tiempo de cálculo computarizado.
• Requiere de muchas lecturas/escrituras en memoria.

  Características

 

La ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. 

Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado.

Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está  ordenada.

Método de los más conocidos y más fáciles, pero a la ves es uno de los menos eficaces que se basa en la ordenación por intercambio de elementos. 

Código en Java

public class Burbuja {

    public static void main(String[] args) {

        int [] nums={34,25,13,24,8,1,11};

        int aux;

        for(int i=0; i<nums.length; i++)

        {

            for(int j=i+1;j<nums.length;j++)

            {

                if (nums[j]<nums[i])

                {

                    aux=nums[i];

                    nums[i]=nums[j];

                    nums[j]=aux;

                }

            }

        }

        System.out.println("El arreglo ordenado es:");

        for (int i=0; i<nums.length; i++)

        {

            System.out.println(nums[i]+"");

        }

    }

    

}

Esta es la corrida del programa.

Metodo Quick Sort

 (Ordenamiento Rápido) 

Es un algoritmo creado por el científico británico en computación C.A.R. Hoare, se basa en la técnica "Divide y vencerás", que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

Forma en que trabaja el algoritmo:

1-•Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.

2-•Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. 

3-•Se comparan para ver si el número pivote es mayor.

4-•Se vuelven a comparar para ver si es mayor el número pivote

5-•Este sigue siendo el número pivote.

6-La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.

7-•Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

8-Elementos Ordenados.

Código en Java

public class quicksort {

    public static void main(String a[]){

  int i;

  int array[] = {12,9,4,99,120,1,3,10,13};

  System.out.println("    Quick Sort\n"); 

 System.out.println("Valores antes de QuickSort:\n");

 for(i = 0; i < array.length; i++)

    System.out.print( array[i]+"  ");

    System.out.println();

   quick_srt(array,0,array.length-1);

   System.out.print("\n\n\nValores despues de QuickSort:\n\n");

  for(i = 0; i <array.length; i++)

   System.out.print(array[i]+"  ");

    System.out.println();

             }

    public static void quick_srt(int array[],int low, int n){

            int lo = low; 

            int hi = n;

            if (lo >= n) {

            return;

            }

            int mid = array[(lo + hi) / 2];

            while (lo < hi) {

            while (lo<hi && array[lo] < mid) {

                  lo++;

             }

             while (lo<hi && array[hi] > mid) {

               hi--;

             }

             if (lo < hi) {

              int T = array[lo];

              array[lo] = array[hi];

              array[hi] = T;

              }

              }

               if (hi < lo) {

               int T = hi;

               hi = lo;

               lo = T;

             }

               quick_srt(array, low, lo);

               quick_srt(array, lo == low ? lo+1 : lo, n);

             }

 }

Corrida del programa

Donald Shell

Método Shell sort

Se denomina “SHELL” en honor a su inventor Donald Shell. .

Es un algoritmo de ordenación interna muy sencillo pero muy ingenioso, basado en comparaciones e intercambios, y con unos resultados radicalmente mejores que los que se pueden obtener con el método de la burbuja, el de selección directa o el de inserción directa.




El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:

1.El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".

2.El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.

Ventajas

• No requiere memoria adicional. 
• Mejor rendimiento que el método de inserción rápido. 
• Fácil implementación.

Desventajas

• Su funcionamiento puede resultar confuso 
• Suele ser un poco lento. 
• Realiza numerosas comparaciones e intercambios.

Pasos para el ordenamiento shell sort

1. Obtener n. 
2. Obtener k ( k=n/2) 3.Clarificar cada grupo por separado, comparando las parejas de elementos y si no están ordenados se intercambian 
3. N se divide entre 2 y se vuelve a obtener k. 
4. Nuevamente se clasifica cada grupo por separado. 
5. El algoritmo termina cuando el tamaño de k es igual a 1.

Código en Java

public class shell_sort {

    

    public static void shellSort( int b[ ])

    { 

for(int k= b.length/2; k>0; k=k==2?1:(int)( k/2.2))

{ 

      for(int i=k;i<b.length; i++ )

      { 

        int tmp =b[i]; 

        int j; 

        for(j=i; j>=k&&tmp<b[j-k]; j-=k)

        { 

          b[j]=b[j-k]; 

        } 

        b[j]=tmp; 

     } 

} 

    } 

public static void main(String args[]){ 

int a[]={321, 6, 1, 234, 213, 4, 5, 123}; //Este es el array de elementos que vamos a ordenar 

    System.out.println("Antes del ordenamiento");

for(int i=0;i<a.length;i++)

{

    System.out.print(a[i]+" ");

    

}

shellSort(a); //llamada al metodo shellSort 

    System.out.println("\n");

System.out.println("Ordenado por el método Shell");

for (int i=0;i < a.length;i++){ //Este bucle imprime el contenido del array 

    

    System.out.print(a[i]+" "); 

}//fin del for 

}//fin del main 

}//class ShellSort

Corrida del programa

Método Radix

En informática, el ordenamiento Radix (radix sort en inglés) es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y, especialmente, números en punto flotante especialmente formateados, radix sort no está limitado sólo a los enteros.

Descripción

Las representaciones de enteros que son procesadas por los algoritmos de ordenamiento se les llama a menudo "claves", que pueden existir por sí mismas o asociadas a otros datos. Radix sort LSD usa típicamente el siguiente orden: claves cortas aparecen antes que las claves largas, y claves de la misma longitud son ordenadas de forma léxica. Esto coincide con el orden normal de las representaciones de enteros, como la secuencia "1, 2, 3, 4, 5, 6, 7, 8, 9, 10". Radix sorts MSD usa orden léxico, que es ideal para la ordenación de cadenas de caracteres, como las palabras o representaciones de enteros de longitud fija. Una secuencia como "b, c, d, e, f, g, h, i, j, ba" será ordenada léxicamente como "b, ba, c, d, e, f, g, h, i, j". Si se usa orden léxico para ordenar representaciones de enteros de longitud variable, entonces la ordenación de las representaciones de los números del 1 al 10 será "1, 10, 2, 3, 4, 5, 6, 7, 8, 9", como si las claves más cortas estuvieran justificadas a la izquierda y rellenadas a la derecha con espacios en blanco, para hacerlas tan largas como la clave más larga, para el propósito de este ordenamiento.

Ejemplo

Vector original:

25 57 48 37 12 92 86 33

Asignamos los elementos en colas basadas en el dígito menos significativo de cada uno de ellos.0:
1:
2:12 92
3:33
4:
5:25
6:86
7:57 37
8:48
9:


Después de la primera pasada, la ordenación queda:

12 92 33 25 86 57 37 48

Colas basadas en el dígito más significativo.0:
1:12
2:25
3:33 37
4:48
5:57
6:
7:
8:86
9:92


Lista ordenada:

12 25 33 37 48 57 86 92

4.2 Métodos de Búsqueda

Método de búsqueda Secuencial

Se utiliza cuando el vector no está ordenado o no puede ser ordenado previamente. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del arreglo hasta encontrarlo, o hasta que se llegue al final. La existencia se puede asegurar cuando el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del arreglo. A continuación se muestra el pseudocódigo del algoritmo:[cita requerida].

Pasos de la Búsqueda Secuencial:

1.Consiste en recorrer el arreglo elemento a elemento e ir comparando con el valor buscado.

2.Se empieza con la primera casilla del arreglo y se observa una casilla tras otra hasta que se encuentra el elemento buscado o se han visto todas las casillas.

3.El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero.

4.El método de búsqueda lineal funciona bien con arreglos pequeños o para arreglos no ordenados.

 

Ejemplo:

int busquedaSimple(int vector[], int n, int dato) { 

 int i; 

 for(i=0; i<n; i++)

{ 

       if(dato==vector[i]) 

     { 

          return i; 

       } 

 }

 return -1; 

 }

Método de búsqueda Binaria

Se utiliza cuando el vector en el que queremos determinar la existencia de un elemento está previamente ordenado. Este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente el número de iteraciones necesarias.

Está altamente recomendado para buscar en arrays de gran tamaño. Por ejemplo, en uno conteniendo 50.000.000 elementos, realiza como máximo 26 comparaciones (en el peor de los casos).

Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del array (normalmente el elemento central): si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del array que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del array que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en todo el array.


Ventajas:

• La búsqueda binaria es un método eficiente siempre que el vector esté ordenado.
• La búsqueda binaria proporciona un medio para reducir el tiempo requerido para buscar en una lista.
• Este método funciona a un 100% 

Desventajas:

• Si los datos del arreglo no están ordenados no hará la búsqueda
• Este método Necesita un método de ordenamiento como: Burbuja, Quicksort, shell sort, etc. Para que así funcione bien.

Código en Java

public class secuencialdesordenado {
public void buscar()
{
Scanner leer=new Scanner(System.in);
int i=0;
boolean bandera=false;
int x;
int v[]= new int[10];
for(int c=0;c<v.length;c++)
{
System.out.println("introduce los datos del arreglo");
v[c]=leer.nextInt();
}
System.out.println("introduzca elemento a buscar");
x=leer.nextInt();


do{
if(v[i]==x)
{
bandera=true;
}
else {
bandera=false;
}
i++;
}while(i<v.length && bandera==false);

if(bandera==true)
{
System.out.println("el elemento esta en la posicion "+ i);
}
else if(bandera==false)
{
System.out.println("el elemento no esta en la lista");
}
}