Monografias.com > Computación > Programación
Descargar Imprimir Comentar Ver trabajos relacionados

Algoritmos de ordenación no recursivos




Enviado por Rolf Pinto López



Partes: 1, 2

    1. Conceptos
      preliminares
    2. Cuándo aplicar un
      método
    3. Tipos de
      ordenamientos
    4. Clasificación de los
      algoritmos de ordenamiento
    5. Algoritmo
      burbuja
    6. Algoritmo
      inserción
    7. Algoritmo
      selección
    8. Algoritmo
      Shake
    9. Algoritmo
      Shell
    10. Ejercicios
      de aplicación
    11. Bibliografía

    INTRODUCCION

    El ordenamiento es una labor común que realizamos
    cotidianamente, es un proceso tan
    común en nuestras vidas que no nos detenemos a meditar
    mucho en ello. Ordenar es meramente colocar información de una manera especial
    basándonos en un criterio de ordenamiento.

    En la ciencia de
    la computación el ordenamiento de datos
    también cumple un rol muy importante, ya sea como un fin
    en sí o como parte de otros procedimientos
    más complejos. Se han desarrollado muchas técnicas
    en este ámbito, cada una con características
    específicas, y con ventajas y desventajas sobre las
    demás. El propósito principal de un ordenamiento es
    el de facilitar la búsqueda de
    información.

    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.

    Conceptos
    Preliminares

    Antes de comenzar a ver cada algoritmo
    vamos a ponernos de acuerdo en algunos conceptos, para que no
    haya confusiones:

    • Clave: La parte de un registro por la
      cual se ordena la lista. Por ejemplo, una lista de registros con
      campos nombre, dirección y teléfono se puede ordenar
      alfabéticamente de acuerdo al nombre. En este caso los
      campos dirección y teléfono no se toman en cuenta
      en el ordenamiento.
    • Criterio de ordenamiento o de
      comparación:
      El criterio que utilizamos para asignar
      orden a los registros con base en una o más claves. De
      esta manera decidimos si un registro es mayor o menor que
      otro.
    • Registro: Un grupo de datos que forman la
      lista. Pueden ser datos primitivos enteros, caracteres, reales,
      etc., o grupos de
      ellos, que en C++ equivalen a estructuras
      de datos.

    Cuándo APLICAR un
    método

    Cuando se requiere hacer una cantidad considerable de
    búsquedas y es importante el factor tiempo.

    Al estudiar algoritmos de
    todo tipo, no sólo de ordenamiento, es bueno tener una
    forma de evaluarlos antes de pasarlos a código.
    De esta manera podremos decidir cuál se adapta mejor a los
    requerimientos de nuestro programa.
    Así que veamos estos aspectos:

    • Estabilidad: Cómo se comporta con
      registros que tienen claves iguales. Algunos algoritmos
      mantienen el orden relativo entre éstos y otros no.
      Veamos un ejemplo. Si tenemos la siguiente lista de
      datos:

    (Nombre, Edad)

    Pedro 19, Juan 23, Felipe 15, Marcela 20, Juan 18,
    Marcela 17

    Ordenada alfabéticamente por el nombre con un
    algoritmo estable quedaría así:

    Felipe 15, Marcela 20, Marcela 17, Juan 23, Juan
    18, Pedro 19

    Un algoritmo no estable podría dejar a Juan
    18
    antes de Juan 23, o a Marcela 20
    después de Marcela 17.

    • Tiempo de ejecución: La complejidad del
      algoritmo, que no tiene que ver con dificultad del algoritmo,
      mas bien con el rendimiento o la eficiencia del
      algoritmo. Es una función
      independiente de la implementación o de los factores
      externos. Tendremos que identificar una operación
      fundamental que realice nuestro algoritmo, que en este caso es
      comparar. Ahora contamos cuántas veces el algoritmo
      necesita comparar. Si en una lista de n términos realiza
      n comparaciones la complejidad es O(n). Una medida de
      eficiencia es:
    • Contar el número de comparaciones
    • Contar el número de movimientos de
      ítems
    • Estos están en función del
      número de elementos a ser ordenados.
    • Un buen algoritmo de ordenamiento requiere de O(n log
      n) comparaciones.
    • Requerimientos de memoria: El
      algoritmo puede necesitar memoria adicional para realizar su
      labor. En general es preferible que no sea así, pero es
      común en la programación tener que sacrificar memoria
      por rendimiento.

    Tipos de ordenamientos

    internos

    Los datos a ordenar están en memoria la principal
    RAM, por lo que
    se asume que el tiempo que se requiere para acceder cualquier
    elemento sea el mismo.

    Inserción Directa

    Inserción Directa

    Inserción Binaria

    Selección Directa

    Selección Directa

    Intercambio Directo

    Burbuja

    Shake

    Inserción Disminución
    Incremental

    Shell

    Ordenamiento De Árbol

    Heap

    Tournament

    Sort Particionado

    Quick Sort

    Merge Sort

    Radix Sort

    Cálculo De Dirección

    externos

    Los datos a ordenar están en la memoria
    secundaria, es decir, disco duro,
    disco extraíble, por lo que se asume que el tiempo que se
    requiere para acceder a cualquier elemento depende de la
    última posición consultada.

    Straight Merging

    Natural Merging

    Balanced Multiway Merging

    Polyphase Sort

    Distribution Of Initial Runs

     

    Clasificación de
    los algoritmos de ordenamiento

    Algoritmos de inserción:


    Inserción Directa


    Shell

    Inserción Binaria

    Hashing

    Algoritmos de intercambio:


    Burbuja


    Shake


    Quick Sort

    Algoritmos de selección:


    Selección Directa
    ü

    Algoritmos de enumeración:


    Merge


    Radix


    Heap

    Los métodos
    simples son: Inserción Directa, Selección, Burbuja
    y Shell, en dónde el último es una extensión
    al método de
    Inserción, siendo más rápido. Los
    métodos más complejos son Quick Sort y
    Heap.

    Algoritmo Burbuja

    Bubble Sort recorre el arreglo intercambiando los
    elementos adyacentes que estén desordenados. Recorre el
    arreglo tantas veces hasta que ya no haya cambios.
    Prácticamente lo que hace es tomar el elemento mayor y lo
    coloca en las últimas posiciones o tomar el menor y
    colocarlo en las primeras posiciones.

    PSEUDOCÓDIGO

    ALGORITMO BURBUJA

    INICIO

    ENTERO X, Z, ARREGLO[N]

    X ß 0

    MIENTRAS(X < N)

    {

    Z ß N

    MIENTRAS(Z >= 0)

    {

    SI(ARREGLO[Z] < ARREGLO[Z-1])

    {

    INTERCAMBIO(ARREGLO[Z],ARREGLO[Z-1])

    }

    Z ß Z –
    1

    }

    X ß X + 1

    }

    FIN

    CÓDIGO EN
    C++

    void burbuja(void)

    {

    int x, z, aux, ARREGLO[N];

    x = 0;

    while(x < N)

    {

    z = N;

    while(z >= 0)

    {

    if(ARREGLO[z] < ARREGLO[z – 1])

    {

    aux = ARREGLO[z];

    ARREGLO[z] = ARREGLO[z – 1];

    ARREGLO[z – 1] = aux;

    }

    z–;

    }

    x++;

    }

    }

    Tiempo de ejecución: El ciclo interno se
    ejecuta n veces. El ciclo externo también se ejecuta n
    veces, la complejidad es n * n = O(n2). El comportamiento
    del caso promedio depende del orden de entrada de los datos, pero
    es sólo un poco mejor que el del peor caso, y sigue siendo
    O(n2).

    Estabilidad: No intercambia registros con claves
    iguales.

    Ventajas:

    • Fácil implementación.
    • No requiere memoria adicional.

    Desventajas:

    • Muy lento.
    • Muchas comparaciones.
    • Muchos intercambios.

    Algoritmo Inserción

    Este método consiste en insertar un elemento en
    una parte ya ordenada del vector y comenzar de nuevo con los
    elementos restantes. Este también es un algoritmo lento,
    pero puede ser de utilidad para
    listas semiordenadas, pues en ese caso realiza pocos
    desplazamientos.

    PSEUDOCÓDIGO

    ALGORITMO INSERCIÓN

    INICIO

    ENTERO X, Z, AUX, ARREGLO[N]

    LOGICO B

    PARA(X ß 1, HASTA N,
    X ß X + 1)

    {

    AUX ß
    ARRAY[X]

    Z ß X – 1

    B ß FALSO

    MIENTRAS(B = FALSO Y Z >= 0)

    {

    SI(AUX < ARREGLO[Z])

    {

    ARREGLO[Z + 1] ß
    ARREGLO[Z]

    Z ß Z –
    1

    }

    SI NO

    {

    B ß
    VERDAD

    }

    }

    ARREGLO[Z + 1] ß
    AUX

    }

    FIN

    CÓDIGO EN
    C++

    void insercion(void)

    {

    int x,z, aux, ARREGLO[N];

    bool b;

    for(x = 1; x < N; x++)

    {

    aux = ARREGLO[x];

    z = x – 1;

    flag = false;

    while(b == false && z >= 0)

    {

    if(aux < ARREGLO[z])

    {

    ARREGLO[z + 1] = ARREGLO[z];

    z–;

    }

    else

    b = true;

    }

    ARREGLO[z + 1] = aux;

    }

    }

    Ejemplo:

    [0]

    15

    15

    10

    10

    10

    10

    10

    10

    10

    10

    10

    10

    10

    10

    7

    [1]

    10

    ð 15

    15

    15

    15

    14

    14

    14

    14

    11

    11

    11

    11

    ð 10

    10

    [2]

    14

    14

    14

    ð 15

    15

    15

    15

    ð 14

    14

    14

    14

    14

    ð 11

    11

    11

    [3]

    11

    11

    11

    11

    11

    11

    ð 15

    15

    15

    15

    15

    ð 14

    14

    14

    14

    [4]

    7

    7

    7

    7

    7

    7

    7

    7

    7

    7

    ð 15

    15

    15

    15

    15

    ê

    ê

    ê

    ê

    ê

    X

    1

    2

    3

    4

    5

    Z

    0

    -1

    1

    0

    2

    1

    0

    3

    2

    1

    0

    -1

    4

    B

    F

    F

    T

    F

    T

    F

    F

    AUX

    10

    14

    11

    7

    ?

    Tiempo de Ejecución: Para una
    lista de n elementos el ciclo externo se ejecuta n-1 veces. El
    ciclo interno se ejecuta como máximo 1, 2, 3 veces a la
    tercera iteración, etc., esto tratándose del pero
    caso posible. Esto produce una complejidad
    O(n2).

    Estabilidad: No intercambia
    registros con claves iguales. Por lo tanto es estable.

    Ventajas:

    • Fácil implementación.
    • Requerimientos mínimos de memoria.

    Desventajas:

    • Lento.
    • Numerosas comparaciones.

    Partes: 1, 2

    Página siguiente 

    Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

    Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

    Categorias
    Newsletter