Discussion :

[om38100]

Je n'arrive pas a faire cet exercice étant débutant en langage C

Ecrire en C un programme qui saisit un tableau de 9 réels puis qui indique si les éléments de ce tableau sont triés en ordre décroissant ou non.

Merci

[Kaamui]

Bonsoir,

la première idée qui vient en général serait de comparer chaque élément aux reste du tableau, mais la complexité serait de O(n²) et c'est pas top.

je penses qu'une bonne manière de faire serait de créer une copie du tableau que tu trie dans l'ordre croissant (quickSort est en O(n log n) je crois). Ensuite il te suffit de comparer chaque case de même indice. A la première différence, le tableau n'est pas croissant.

Quick sort :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
void quickSort(float tableau[], int debut, int fin)
{
    int gauche = debut-1;
    int droite = fin+1;
    const float 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);
}

le code n'est pas très simple dans cette version, mais essaie de le comprendre (pas de copié-collé tout con hein)


Edit : encore mieux, je viens de voir que dans la SL (librairie standard (#include <stdlib.h>) ) il y a déjà une fonction quicksort : qsort.

Donc tu fais saisir tes valeurs (utilise scanf pour commencer, tu verra ensuite qu'il y a des méthodes plus simples, mais un peu plus complexes, en terme de notion), tu trie ton tableau clone, tu fais une comparaison de chaque élément de même valeur d'indice (O(n)) et voilou.


Bon courage,

[diogene]

Ce n'est vraiment pas la peine de monter une usine à gaz pour si peu !
Il suffit de vérifier que tab[i] >= tab[i+1] pour i = 0 à 7

[Kaamui]

ouio en effet je ne sais pas pourquoi je pensais qu'un chiffre pouvait être croissant au précédant mais pas au suivant et donc qu'il fallait vérifier pour chaque élément s'il est plus ou moins grand que le reste du tableau...

Me aculpa c'était débile.