Enrere Mòdul 3
Fonaments de Programació. Llenguatge C/C++---
Pràctica  Resum teòric Exercicis
Pràctica d'ampliació

 
Alguns mètodes d'Ordenació

Segurament, amb la cerca, l'ordenació és una de les tasques més importants i més extensament analitzades de totes les tasques de programació. En aquesta pràctica veurem, sense entrar en massa detalls, dos dels mètodes d'ordenació més coneguts.

 
El mètode de la bombolla

Aquest mètode és, potser, un dels més coneguts mètodes d'ordenació i el més simple, però també dels pitjors en quant a rapidesa.

El mètode de la bombolla utilitza el mètode d'ordenació per canvi. Fa servir repetides comparacions i, si és necessari, canvis en els elements adjacents. 

//m3pa21.cpp: ordenació pel mètode de la bombolla

#include <stdio.h>
#define MAX_n 100

void main(){

    int n,ct1,ct2;
    int num[MAX_n];
    int aux;

    do{

        printf("introduïu el nombre de números a ordenar ");
        scanf("%d",&n);

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

    printf("introduïu els %d nombres\n",n);

    for (ct1=0;ct1<n;ct1++){

        printf("\nnum %d ",ct1);scanf("%d",&num[ct1]);

    }

 

    //algoritme principal

    for (ct1=1;ct1<n;ct1++){

        for(ct2=n-1;ct2>=ct1;ct2--){

             if( num[ct2-1]>num[ct2]){

                 aux=num[ct2-1]; 
                 num[ct2-1]=num[ct2];
                 num[ct2]=aux;

             }

        }

    }

 

    for (ct1=0;ct1<n;ct1++){

         printf("%d ",num[ct1]);

    }

}

L'algoritme principal està destacat en un color de fons més fosc.

Per tal d'entendre com funciona aquest algoritme veurem com es canvien els números en cada pas. Imaginem que entrem 5 números que són: 5,1,4,3,2. Els successius canvis fins arribar a l'ordenació final són:
0 5 5 5 1 1 1 1 1
1 1 1 1 5 5 2 2 2
2 4 4 2 2 2 5 3 3
3 3 2 4 4 3 3 5 4
4 2 3 3 3 4 4 4 5
 

Cada pas correspon a una columna.

Les caselles de color verd corresponen als números que ja estan ben col·locats.

 

Ordenació per selecció

Una ordenació per selecció selecciona l'element més baix i el canvia pel primer element. A continuació fa el mateix amb els n-1 elements restants. En aquest mètode, si un número està ja en la seva posició no es mou.

Exemple, si els números introduïts són: 5,1,4,3,2 els successius passos d'ordenació són:

0 5 1 1 1
1 1 5 2 2
2 4 4 4 3
3 3 3 3 4
4 2 2 5 5
 

El programa que implementa aquest algorisme és el següent:

//m3pa22.cpp: ordenació per selecció

 

#include <stdio.h>

#define MAX_n 100

 

void interc(int *num,int n,int m);

int min(int *num,int n,int m); //calcula el mínim entre n i m

 

void main(){

    int n,ct;

    int num[MAX_n];

 

    do{

        printf("introduïu el nombre de números a ordenar ");

        scanf("%d",&n);

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

 

    printf("introduïu els %d nombres\n",n);

 

    for (ct=0;ct<n;ct++){

        printf("\nnum %d ",ct);scanf("%d",&num[ct]);

    }

 

    for (ct=0;ct<n-1;ct++){

        interc(num,ct,min(num,ct,n-1));

    }

    for (ct=0;ct<n;ct++){

        printf("%d ",num[ct]);

    }

 

}

 

int min(int *num,int n, int m){

    int aux,ctmin,ct;

 

    aux=num[n];ctmin=n;

    for(ct=n;ct<=m;ct++){

        if (aux>num[ct]){

            aux=num[ct];

            ctmin=ct;

        }

    }

    return ctmin;

}

 

 

void interc(int *num, int n, int m){

    int aux;

 

    aux=num[n];

    num[n]=num[m];

    num[m]=aux;

}

 

Ordenació ràpida (Quicksort)

L'ordenació ràpida va ser inventada i denominada d'aquesta forma per C.A.R. Hoare i és un mètode més eficient que els dos mètodes anteriors. No escriurem el codi d'aquesta ordenació perquè aquesta funció ja està implementada en les llibreries C estàndards. Només citarem que en l'ordenació ràpida es tria un element de comparació i se separen tots els números en dos conjunts: els que són més grans que aquest element de comparació i els que són més petits. Per a cada element es torna a fer el mateix procés amb uns altres elements de comparació.