Exemple 3 : Les tris

Contenu du fichier

#include <iostream>

using namespace std;

#define MAX 20
int main()
{
    int tri_fusion(int, int []);
    int tab[MAX], nb, i;
    bool reussite;

    cout << "Entrer les valeurs (-1 pour arreter): " << endl;
    cin >> nb;
    i = 0;
    while (nb > -1 && i < MAX)
    {
        cout << nb << endl;
        tab[i] = nb;
        i++ ;
        cin >> nb;
    }

    reussite = tri_fusion(i, tab);

    cout << "Liste triee" << endl;
    if (reussite)
    {
        for (int j = 0; j < i; j++) cout << "  " << tab[j];
        cout << endl;
    }
    return 0;
}

bool tri_fusion(int longueur, int liste[])
{
    int liste1[MAX], liste2[MAX];
    int  long1, long2;
    int index, index1, index2, i;

    if (longueur == 0) return false;
    if (longueur == 1)  return true;

    long1 = longueur / 2;
    long2 = longueur - long1;
    for (i = 0; i<long1; i++) 
    {
        liste1[i] = liste[i];
    }
    for (int j = 0; j < long2; j++) 
    {
        liste2[j] = liste[i+j];
    }

    tri_fusion(long1, liste1);
    tri_fusion(long2, liste2);

    index1 = 0;
    index2 = 0;
    for (index=0; index1<long1 && index2<long2; index++)
    {
        if (liste1[index1] < liste2[index2])
        {
            liste[index]=liste1[index1];
            index1++;
        }
        else
        {
            liste[index]=liste2[index2];
            index2++;
        }
    }
    while (index1<long1)
    {
        liste[index]=liste1[index1];
        index++;
        index1++;
    }
    while (index2<long2)
    {
        liste[index]=liste2[index2];
        index++;
        index2++;
    }
    return true;
}


void tri_bulle(int nb, int tab[])
{
    void swap(int&, int&);

    for (int i = 1; i < nb; i++)
    {
        if ( tab[i-1] > tab[i] )
        {
            swap(tab[i-1], tab[i]);
        }
    }
    tri_bulle(nb-1, tab);

    return;
}


void tri_bulle_it(int nb, int tab[])
{
    void swap(int&, int&);

    for (int k = nb; k > 1; k--)
    {
        for (int i = 1; i < k; i++)
        {
            if ( tab[i-1] > tab[i] )
            {
                swap(tab[i-1], tab[i]);
            }
        }
    }

    return;
}

void swap (int &a, int &b) 
{
    int t;
    t=a;
    a=b;
    b=t;
    
    return;
}