Tri quicksort compilé avec c++builder5

Commenter

Contenu du snippet

Petit code montrant le principe de récursivité à l'aide de l'algorithm du QuickSort. Conçu avec des variables dimensionnées (fonctionne aussi très bien avec des pointeurs)

Source / Exemple : 


#include <iostream.h>
#include <conio.h>

void Echange(int tab[], int i, int j);
int Partition(int tab[], int gauche, int droite);
void Tri_Rapide(int tab[], int gauche, int droite);
void Afficher(int tab[], int N);

//Fonction principal  -->

void main(void)
{
  int tab[45];
  int i, Num = 1, ligne = 4;

  gotoxy(20, 1);
  cout << "Entrez 45 Nombres différents:";

  for (i=0; i<45; i++, Num++)
    {
        if (Num > 30)
        {
          if (ligne >= 19)
            ligne = 4;
          gotoxy( 51, ligne++ );
          cout << "Nombre " << Num << ": ";
        }
        else if (Num > 15)
        {
          if (ligne >= 19)
            ligne = 4;
          gotoxy( 26, ligne++ );
          cout << "Nombre " << Num << ": ";
        }
        else
        {
          gotoxy( 1, ligne++ );
          cout << "Nombre " << Num << ": ";
        }
      cin >> tab[i];
    }

  gotoxy(20, 20);
  cout << "\nLes nombres en ordre d'entré sont:\n\n";
  Afficher(tab, 45);
  gotoxy(20, 25);
  cout << "\nLes nombres une fois le tri effectué sont:\n\n";
  Tri_Rapide(tab, 0, i-1);
  Afficher(tab, 45);

  getch();  // Pause
}

//Fonction récursive du QuickSort

void Tri_Rapide(int tab[], int gauche, int droite)
{
  int pivot;

  if ( droite > gauche )
  {
    pivot = Partition( tab, gauche, droite);
    Tri_Rapide( tab, gauche, pivot);
    Tri_Rapide( tab, pivot+1, droite);
  }
}

//Fonction répartissant les données à l'aide d'un pivot (le premier élément) -->

int Partition( int tab[], int gauche, int droite)
{
  int g, d, p;

  p = tab[gauche];
  g = gauche-1;
  d = droite+1;

  while(true)
  {
    do
       d--;
    while ( tab[d] > p );

    do
       g++;
    while ( tab[g] < p );

    if ( g < d)
       Echange( tab, g, d );
    else
       return d;
  }
}

//Fonction Échangeant les éléments de droites et de gauches -->

void Echange(int tab[], int i, int j)
{
   int temp;

   temp = tab[i];
   tab[i] = tab[j];
   tab[j] = temp;
}

//Simple fonction d'affichage -->

void Afficher(int tab[], int N)
{
  for(int i=0;i<N;i++)
     cout << tab[i] << " ";
}

Conclusion :


Selon moi c'est l'algorithm du QuickSort le plus simple à comprendre!

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (Danforth)