FLORES NAVARRO JHONNY     UNICA

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

​

 

Métodos de ordenamiento.

La ordenación o clasificación es el proceso de organizar datos en algún orden o secuencia específica, tal como creciente o decreciente, para datos numéricos, o alfabéticos, para datos de caracteres. Los métodos de ordenación más directos son los que se realizan en el espacio ocupado por el array. Los más populares son:

Método de Intercambio o de Burbuja:

Se basa en el principio de comparar pares de elementos adyacentes e intercambiarlos entre si hasta que estén todos ordenados. Supongamos que se desea clasificar en orden ascendente el vector o lista:

9, 8, 0, 2, 5, 1, 3, 2, 9

A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]

Los pasos a dar son:

- CompararA[1] yA[2] si están en orden, se mantienen como están, en caso contrario se intercambian entre si.

- A continuación se comparan los elementos 2 y 3; de nuevo se intercambian si es necesario.

- El proceso continua hasta que cada elemento del vector ha sido comparado con sus elementos adyacentes y se han realizado los intercambios necesarios.

Este video muestra de manera simple el ordenamiento de burbuja:

Ejemplo Práctico

    /*Ordenamiento Burbuja */

 

    #include <stdio.h>

    #include <conio.h>

    #define TAM 9

 

    int main()

    {

        int a[TAM] = { 9, 8, 0, 2, 5, 1, 3, 2, 9};

        int i, pasada, aux;

 

        printf("Datos en el orden inicial:\n\n");

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

                printf("%4d",a[i]);

        for (pasada=1;pasada<=TAM-1;pasada++) /*pasadas*/

            for (i=0;i<=TAM-2;i++)

                if (a[i]>a[i+1]) /*comparación */

                {

                    /*intercambio*/

                    aux=a[i];

                    a[i] = a[i+1];

                    a[i+1] = aux;

                }

        printf( "\n\nDatos ordenados en sentido ascendente:\n\n" );

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

                printf("%4d", a[i]);

        printf("\n");

        getch();

    return 0;

    }

                      

Ordenamiento por inserción (Insertion Sort).

Consiste en insertar un elemento en el vector en una parte ya ordenada de este vector y comenzar de nuevo con los elementos restantes. Por ser utilizado generalmente por los jugadores de cartas se le conoce también por el método de la baraja. Por ejemplo, supóngase que se tiene la lista desordenada;

5 14 24 39 43 65 84 45

Para insertar el elemento 45, habrá que insertar entre 43 y 65, lo que supone desplazar a la derecha todos aquellos números de valor superior a 45, es decir, saltar sobre 65 y 84.

5 14 24 39 43 65 84 45

El método se basa en comparaciones y desplazamientos sucesivos. El algoritmo de clasificaciones de un vector X para N elementos se realiza con un recorrido de todo el vector y la inserción del elemento correspondiente en el lugar adecuado. El recorrido se realiza desde el segundo elemento al n-ésimo.

Ejemplo Práctico.

#include <stdio.h>

int arreglo[10] = {3,10,1,8,15,5,12,6,5,4}; /*Declaracion e inicialización

del arreglo. */

       
 

/*imprimearreglo - Funcion que muestra por pantalla

el contenido de un arreglo.*/

void imprimearreglo() {

    int i; for (i=0;i<10;i++)

        printf("Elemento %d: %d \n",i,arreglo[i]);

}

       

void main() /*Funcion Principal del Programa*/

{

    int i,j,k;

    imprimearreglo();

    for (i=1; i<10; i++) {

        j=i;

            while (j>=0 && arreglo[j]<arreglo[j-1]) {

                k=arreglo[j];

                arreglo[j]=arreglo[j-1];

                arreglo[j-1]=k;

                j--;

            }

    }

    printf("\n\nArreglo ordenado \n\n");

    imprimearreglo();

}

                      

Ordenamiento Rápido (Quicksort).

El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. Esta es la técnica de ordenamiento más rápida conocida. El algoritmo fundamental es el siguiente:

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

• 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. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.

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

• 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. Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.

Veamos el siguiente ejemplo.

Puedes ver otra explicación, esta vez con voz Aquí

Pseudocódigo QuickSort:

Nombre Función: OrdRap

Parámetros:

    lista a ordenar (lista)

    índice inferior (inf)

    índice superior (sup)

 

    // Inicialización de variables

    1. elem_div = lista[sup];

    2. i = inf - 1;

    3. j = sup;

    4. cont = 1;

 

    // Verificamos que no se crucen los límites

    5. if (inf >= sup)

    6. retornar;

 

    // Clasificamos la sublista

    7. while (cont)

    8. while (lista[++i] < elem_div);

    9. while (lista[--j] > elem_div);

    10. if (i < j)

    11. temp = lista[i];

    12. lista[i] = lista[j];

    13. lista[j] = temp;

    14. else

    15. cont = 0;

 

    // Copiamos el elemento de división

    // en su posición final

    16. temp = lista[i];

    17. lista[i] = lista[sup];

    18. lista[sup] = temp;

 

    // Aplicamos la función

    19. OrdRap (lista, inf, i - 1);

    20. OrdRap (lista, i + 1, sup);

              

Ejemplo de Implementación de Quicksort en C

void SortArray (int array[],int first,int last)

{

    int i,j,p,t;

 

    // i se hace igual al índice del primer elemento

    i= first;

    // y j igual al índice del último elemento

    j= last;

    // p se hace igual al elemento pivote del arreglo

    p= array[(first+last)/2];

 

    do {

        // se hace la partición del arreglo

        while (array[i]<p) i++;

        while (p<array[j]) j--;

        if (i<=j) {

 

                // se intercambian los elementos i-esimo y j-esimo del arreglo

                t= array[i];

                array[i]= array[j];

                array[j]= t;

                i++; j--;

            }

    } while (i<=j);

    if (first<j) SortArray(array,first,j);

    if (i<last) SortArray(array,i,last);

} 

 

​

EJERCICIO DE C++

//Metodo Burbuja

 

#include<iostream>

#include<conio.h>

using namespace std;

 

int main(){

            int numeros[] = {1,2,4,3,5};

            int i,j,aux;

           

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

                        for(j=0;j<=5;j++){

                                    if (numeros [j]>numeros[j+1]){

                                                aux = numeros [j];

                                                numeros [j] = numeros[j+1];

                                                numeros[j+1] = aux;

                                    }

                        }

            }

           

            cout<<"+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n";

            cout<<"Numeros de forma Ascendente: ";

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

                        cout<<numeros[i]<<"  ";

            }

            cout<<endl;

           

            cout<<"Numeros de forma Descendente: ";

            for(i=4;i>=0;i--){

                        cout<<numeros[i]<<"  ";

            }

             cout<<"\n+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n";

            getch();

            return 0;

}