Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 98 vistas

    Métodos de Ordenamiento

    Cargado por

    Benito
    Este documento describe 5 métodos de ordenamiento de vectores: 1) ordenación por selección, 2) ordenación por inserción directa, 3) ordenación por montículos (heapsort), 4) ordenación por burbuja, y 5) ordenación por inserción binaria. Para cada método se explican sus características, ventajas, desventajas y se provee pseudocódigo en C++. Adicionalmente, se incluye una librería para leer y mostrar arreglos.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd

    Métodos de Ordenamiento

    Cargado por

    Benito
    98 vistas12 páginas
    Este documento describe 5 métodos de ordenamiento de vectores: 1) ordenación por selección, 2) ordenación por inserción directa, 3) ordenación por montículos (heapsort), 4) ordenación por burbuja, y 5) ordenación por inserción binaria. Para cada método se explican sus características, ventajas, desventajas y se provee pseudocódigo en C++. Adicionalmente, se incluye una librería para leer y mostrar arreglos.

    Descripción original:

    Métodos de Ordenamiento de Vectores

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    DOCX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento describe 5 métodos de ordenamiento de vectores: 1) ordenación por selección, 2) ordenación por inserción directa, 3) ordenación por montículos (heapsort), 4) ordenación por burbuja, y 5) ordenación por inserción binaria. Para cada método se explican sus características, ventajas, desventajas y se provee pseudocódigo en C++. Adicionalmente, se incluye una librería para leer y mostrar arreglos.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    98 vistas12 páginas

    Métodos de Ordenamiento

    Cargado por

    Benito
    Este documento describe 5 métodos de ordenamiento de vectores: 1) ordenación por selección, 2) ordenación por inserción directa, 3) ordenación por montículos (heapsort), 4) ordenación por burbuja, y 5) ordenación por inserción binaria. Para cada método se explican sus características, ventajas, desventajas y se provee pseudocódigo en C++. Adicionalmente, se incluye una librería para leer y mostrar arreglos.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    Está en la página 1de 12

    Mtodos de ordenamiento

    Ordenamientos con vectores.

    1- Ordenacin por seleccin

    Caractersticas, ventajas y desventajas


    Su tiempo de ejecucin es O(N2) para el mejor, peor y caso promedio.

    Es el ms fcil de codicar de los mostrados en este documento.

    Si el array de datos es A y su tamao es N, lo que hace el algoritmo, para


    cada i de [0..N-2] es intercambiar A[i] con el mnimo elemento del subarray
    [A[i+1], ..., A[N]].

    Dado que es muy simple de codicar, aunque no tiene los mejores tiempos de
    ejecucin, es apropiado utilizarlo para arrays de datos relativamente pequeos.

    Codificacin en c++
    #include<iostream>

    using namespace std;

    #include"leearreglo.h"

    #define largo 50

    void seleccionsort (int A[], int n)

    int min,i,j,aux;

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

    min=i;

    for(j=i+1; j<n; j++)

    if(A[min] > A[j])

    min=j;

    aux=A[min];

    A[min]=A[i];

    A[i]=aux ;

    }
    }

    int main ()

    int A[largo],n;

    do{

    cout<<"Cantidad de numeros a ingresar: ";cin>>n;

    if(n<=0||n>largo)

    cout<<"Debe ingresar un valor > a 0 y < a "<<largo<<endl;

    }while(n<=0||n>largo);

    leeCadena(n,A);

    seleccionsort(A,n);

    muestraCadena(n,A);

    2- Ordenacin por Insercin directa

    Caractersticas.
    Es un algoritmo sencillo de entender y de codicar.

    Si el tamao de la entrada es N, entonces el orden del tiempo de ejecucin,


    para el peor caso es O(N2);

    Si la entrada esta "casi ordenada", el algoritmo se ejecuta mucho ms


    rpidamente. Esta velocidad tiende a un tiempo O(N), peor caso que se cumple
    cuando la entrada est totalmente ordenada.

    Es por la propiedad anterior que este algoritmo, a pesar de no ser el ms


    rpido para entradas grandes, suele usarse de la siguiente manera: Se semi
    ordena la entrada con algn otro algoritmo ms rpido y ms adecuado para
    entradas grandes. Luego, cuando tenemos la entrada "casi ordenada" usamos
    este algoritmo. La velocidad de ejecucin ser muy buena por dos razones: su
    tiempo de ejecucin tiende a O(N) con entradas "casi ordenadas" y la simpleza
    de su implementacin har que se ejecute ms rpido que otros algoritmos
    ms complejos.

    Ventajas y Desventajas
    La principal ventaja de este tipo de ordenamiento es su simplicidad. Tambin
    exhibe un buen rendimiento cuando se trabaja con una pequea lista. El
    ordenamiento por insercin es un algoritmo de ordenamiento en el lugar, de
    modo que requiere de espacio mnimo. Su desventaja es que no funciona tan
    bien como otros algoritmos mejores de ordenamiento. Con n al cuadrado pasos
    requeridos para cada n elemento a ser ordenado, este algoritmo no funciona
    bien con una lista grande. Por lo tanto, este slo es til cuando se ordena una
    lista de pocos elementos.

    Codificacin en c++
    #include<iostream>

    #include"leearreglo.h"

    using namespace std;

    #define largo 50

    void insercionDirecta(int A[],int n)

    int i,j,v;

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

    v = A[i];

    j = i - 1;

    while (j >= 0 && A[j] > v)

    A[j + 1] = A[j];

    j--;
    }

    A[j + 1] = v;

    int main ()

    int A[largo],n;

    do{

    cout<<"Cantidad de numeros a ingresar: ";cin>>n;

    if(n<=0||n>largo)

    cout<<"Debe ingresar un valor > a 0 y < a "<<largo<<endl;

    }while(n<=0||n>largo);

    leeCadena(n,A);

    insercionDirecta(A,n);

    muestraCadena(n,A);

    3- Ordenacin por montculos (heapsort)

    Caractersticas ventajas y desventajas.


    Es un algoritmo que se construye utilizando las propiedades de los montculos
    binarios.

    El orden de ejecucin para el peor caso es O(Nlog(N)), siendo N el tamao


    de la entrada.
    Aunque tericamente es ms rpido que los algoritmos de ordenacin vistos
    hasta aqu, en la prctica es ms lento que el algoritmo de ordenacin de Shell
    utilizando la secuencia de incrementos de Sedgewick

    Codificacin en c++

    #include"leearreglo.h"

    #include <iostream>

    #define max 100

    using namespace std;

    int main()

    int A[max],j,item,temp,i,k,n;

    cout<<"Ingresa la cantidad de elementos del arreglo: ";

    cin>>n;

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

    cin >> A[i];

    for(k=n;k>0;k--)

    for(i=1;i<=k;i++)

    item=A[i];

    j=i/2;

    while(j>0 && A[j]<item)

    A[i]=A[j];
    i=j;

    j=j/2;

    A[i]=item;

    temp=A[1];

    A[1]=A[k];

    A[k]=temp;

    cout<<"El orden es:"<<endl;

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

    cout<<A[i] << endl;

    return 0;

    4- Ordenacin por burbuja

    Caractersticas, ventajas y desventajas


    Si se tienen en cuenta las versiones mejoradas haciendo uso de las variables
    interruptor o ndice intercambio, entonces se tendr una eficiencia diferente a cada
    algoritmo. En el mejor de los casos, la ordenacin de burbuja hace una sola pasada en
    el caso de una lista que ya est ordenada en orden ascendente y por tanto su
    complejidad es 0(n). En el caso peor se requieren (n i 1) comparaciones y (n i
    1) intercambios. La ordenacin completa requiere n(n 1) 2 comparaciones y (n i
    1) intercambios. La ordenacin completa requiere n(n 1)/2 comparaciones y un
    nmero similar de intercambios. La complejidad para el caso peor es 0(n2 )
    comparaciones y 0(n2 ) intercambios. De cualquier forma, el anlisis del caso general
    es complicado dado que alguna de las pasadas puede no realizarse. Se podra
    sealar, entonces, que el nmero medio de pasadas k sea 0(n) y el nmero total de
    comparaciones es 0(n2 ). En el mejor de los casos, la ordenacin por burbuja puede
    terminar en menos de n 1 pasadas pero requiere, normalmente, muchos ms
    intercambios que la ordenacin por seleccin y su prestacin media es mucho ms
    lenta, sobre todo cuando los arrays a ordenar son grandes.
    Codificacin en c++

    #include<iostream>

    using namespace std;

    int main()

    int i,j,k,cn;

    int n[cn];

    cout<<"Cantidad de numeros que desea Ingresar: ";cin>>cn;

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

    cout<<"Ingrese numero "<<i+1<<" : ";

    cin>>n[i];

    for(i=1;i<cn;i++)

    for(j=0;j<cn-i;j++)

    if(n[j]>n[j+1])

    {k=n[j+1]; n[j+1]=n[j]; n[j]=k;}

    for(i=0;i<cn;i++)
    {

    cout<<n[i]<<endl;

    cin.ignore();

    return 0;

    5- Ordenacin por insercin binaria

    Caractersticas
    El algoritmo de insercin directa se presentan en la seccin anterior realiza una
    bsqueda lineal para encontrar la posicin en que para hacer la insercin. Sin
    embargo, puesto que el elemento es insertado en una secuencia que ya est
    ordenado, se puede utilizar una bsqueda binaria en lugar de una bsqueda lineal.
    Mientras que una bsqueda lineal requiere O (n) comparaciones en el peor de los
    casos, una bsqueda binaria slo requiere comparaciones. Por lo tanto, si el costo de
    una comparacin es significativo, la bsqueda binaria puede ser preferible.

    Ventajas y Desventajas
    La ventaja de este mtodo respecto al de insercin directa es que se disminuye el
    nmero de comparaciones, aunque el nmero de movimientos se mantiene del mismo
    orden

    Y al ser parecido a la insercin directa presenta algunas desventajas similares


    a ella.

    Codificacin en c++
    #include<iostream>

    #include"leearreglo.h"

    using namespace std;

    #define largo 50

    void insercionBinaria(int A[],int n)

    int i,j,aux,izq,der,m;

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

    {
    aux = A[i];

    izq=0;

    der=i-1;

    while(izq<=der)

    m=((izq+der)/2);

    if (aux<A[m])

    der=m-1;

    else

    izq=m+1;

    j=i-1;

    while(j>=izq)

    A[j+1]=A[j];

    j=j-1;

    A[izq]=aux;

    int main ()

    int A[largo],n;

    do{

    cout<<"Cantidad de numeros a ingresar: ";cin>>n;


    if(n<=0||n>largo)

    cout<<"Debe ingresar un valor > a 0 y < a "<<largo<<endl;

    }while(n<=0||n>largo);

    leeCadena(n,A);

    insercionBinaria(A,n);

    muestraCadena(n,A);

    Librera leearreglo.h
    #include<iostream>

    using namespace std;

    void leeCadena(int cant,int n[])

    int i;

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

    cout<<"Ingresa numero "<<i+1<<": ";

    cin>>n[i];

    void muestraCadena(int cant,int n[])

    int i;

    for(i=0;i<cant;i++)
    {

    cout<<n[i]<<endl;

    También podría gustarte