Demo entry 3860447

tri rapide

   

Submitted by Ahmed Noukta on Mar 03, 2016 at 22:50
Language: C. Code size: 2.5 kB.

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

void echanger(int tableau[], int a, int b)
{
    int temp = tableau[a];
    tableau[a] = tableau[b];
    tableau[b] = temp;
}

void quickSort(int tableau[], int debut, int fin)
{
    int gauche = debut-1;
    int droite = fin+1;
    const int pivot = tableau[debut];

    /* Si le tableau est de longueur nulle, il n'y a rien à faire. */
    if(debut >= fin)
        return;

    /* Sinon, on parcourt le tableau, une fois de droite à gauche, et une
       autre de gauche à droite, à la recherche d'éléments mal placés,
       que l'on permute. Si les deux parcours se croisent, on arrête. */
    while(1)
    {
        do droite--; while(tableau[droite] > pivot);
        do gauche++; while(tableau[gauche] < pivot);

        if(gauche < droite)
            echanger(tableau, gauche, droite);
        else break;
    }

    /* Maintenant, tous les éléments inférieurs au pivot sont avant ceux
       supérieurs au pivot. On a donc deux groupes de cases à trier. On utilise
       pour cela... la méthode quickSort elle-même ! */
    quickSort(tableau, debut, droite);
    quickSort(tableau, droite+1, fin);
}

void lireNentiers(int tableau[], int n)
{
    FILE* fichier = NULL;
    int i;
    fichier = fopen("entiers.txt", "r");
    if (fichier != NULL)
    {
        srand(time(NULL));
        for(i = 0; i < n && fscanf(fichier, "%d ", &tableau[i]) != EOF; i++);
        fclose(fichier);
    }
    else
    {
        // On affiche un message d'erreur si on veut
        printf("Impossible d'ouvrir le fichier entiers.txt");
    }
}

void ecrireResultat(int n, float tempsExecution)
{
    FILE* fichier = NULL;
    fichier = fopen("resultatTriRapideC.txt", "a");
    if (fichier != NULL)
    {
        fprintf(fichier, "taille : %d, temps : %.20f\n", n,tempsExecution);
        fclose(fichier);
    }
    else
    {
        // On affiche un message d'erreur si on veut
        printf("Impossible d'ouvrir le fichier resultatTriRapideC.txt");
    }
}

int main(void)
{
    int n, i;
    printf("nombre des entiers :\t");
    scanf("%d", &n);
    int tableau[n];
    lireNentiers(tableau, n);
    clock_t start, stop;
    start = clock();
    quickSort(tableau, 0, n-1);
    stop = clock();
    ecrireResultat(n, (double)(stop - start)/CLOCKS_PER_SEC*1000);
    for(i = 0; i < n; i++)
    {
        printf("%d ", tableau[i]);
    }
    putchar('\n');
    
    return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).