Discussion :

[biba1980]

Bonjour,
Soit le problème suivant, T, un tableau dont les indices vont de 1 à n contenant des 0 et des 1 dans un ordre quelconque.
Trouver un algorithme linéaire en temps et de complexité spatiale en O(1) pour trier ce tableau et retourner le nombre de 0, et ce, sans compter explicitement le nombre de 0 et de 1. Justifiez que votre algorithme est linéaire. Identifiez le type d’algorithme que vous avez conçu (vorace, programmation dynamique, etc.). Décrivez votre algorithme en pseudo-code.

Moi, j'ai fait ce code là:
Programme trier

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
tab, tab1 : tableau [1..n]
debut
    c:=1
    k:=n
    pour i := 1 haut n faire
        si tab[j] =0 alors 
            tab1[c]:=tab[i]
            c:=++
        sinon tab1[k]:=tab[i]
            k:=--
        finsi
    finpour
fin

Je veux, si possible savoir si cet algorithme est de complexité spatiale constante donc dans O(1), Je ne sais pas de quel type est cet algorithme.
Merci à tt le monde.

[ToTo13]

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
tab, tab1 : tableau [1..n]
debut
    c:=1
    k:=n
    pour i := 1 à n faire // Ok c'est linéaire
        si tab[i] = 0 alors  tab1[c++]:=tab[i] // Attention tu avais mis tab[J]
        sinon tab1[k--]:=tab[i]
        finsi
    finpour
    retourner c-1 // Ne pas oublier de retourner le nombre de zéros
fin

Ton algorithme est bien linéaire car tu ne parcours qu'une seule fois le tableau sans opérations à l'intérieur et la taille mémoire dépend de n.

[pseudocode]

Ton algorithme est bien linéaire car tu ne parcours qu'une seule fois le tableau sans opérations à l'intérieur et la taille mémoire dépend de n.

Tout a fait. L'algo n'est donc pas en complexité spatiale O(1).

La complexité spatiale O(1) signifie qu'il ne faut pas "dupliquer" le tableau existant. Il faut donc un algo de tri "in place", c'est à dire qu'il modifie directement le tableau de départ.

[lcfseth]

L'algo que j'aurais fais, en gros (je me rappelle plus trop de la syntaxe):

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
 
tab: tableau [1..n]
debut
<div style="margin-left:40px">
i:=1
c:=n
tantque i<= n et c>=i faire
<div style="margin-left:40px">
si tab[i] = 1 alors
<div style="margin-left:40px">
tab[i]:=tab[c]
tab[c]:=1
c--</div>sinon
<div style="margin-left:40px">
i++</div>finsi</div>fintantque
retourner n-c // c est le nombre de 1 :)</div>fin

L'idée et de mettre tout les 1 en fin de tableau, en faisant un simple swap avec la valeur en cours. Si le tableau est plein de 0, i atteindra n, si le tableau est plein de 1, i restera à 1 et c'est c qui ira à 1.
Complexite algorithmique en n au pire, complexite spaciale 1.

[pseudocode]

D'accord avec lcfseth. Quoique j'aurais plutot écrit l'algo ansi :

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
left:=1
right:=n
TANTQUE left<=right FAIRE
    SI tab[left]=0 ALORS
        left++
    SINON
        SI tab[right]=1 ALORS
            right--
        SINON
            tab[left]:=0
            tab[right]:=1
        FINSI
    FINSI
FINTANTQUE
RETOURNER (left-1)

Edit : modif du code pour un tableau commencant à l'indice "1", comme indiqué dans le PO

[lcfseth]

Joli manière de profiter du faible nombre de l'ensemble de départ (0,1)
Respect