123 lines
2.4 KiB
Plaintext
123 lines
2.4 KiB
Plaintext
PROTO INT plusgrandstrict(n,m)
|
|
PROTO INT plusgrand(n,m)
|
|
PROTO VOID heapsort(t[], n)
|
|
|
|
// Ce programme lit un tableau de 10 entiers et imprime
|
|
// le tableau trie par heapsort.
|
|
//=====================================================
|
|
FUNC VOID main()
|
|
{
|
|
INT a[10], i, j
|
|
|
|
i := 0
|
|
WHILE 10-i DO
|
|
{
|
|
PRINT "\n Entrer le",i,"eme: "
|
|
READ j
|
|
a[i] := j
|
|
i := i+1
|
|
PRINT " i=", i, " j=",j
|
|
}
|
|
DONE
|
|
heapsort(a,10)
|
|
i := 0
|
|
WHILE 10-i DO
|
|
{
|
|
PRINT "\n t[",i,"] = ",a[i]
|
|
i:= i+1
|
|
}
|
|
DONE
|
|
}
|
|
|
|
|
|
// Implementation du heapsort
|
|
//===========================
|
|
FUNC VOID heapsort(t[], n ) // n: nombre d'elements a trier
|
|
{
|
|
INT l,r,j,s, test
|
|
|
|
l := n/2+1
|
|
r := n
|
|
|
|
WHILE plusgrand(r,2) DO
|
|
{
|
|
IF plusgrandstrict(l,1)
|
|
THEN // agrandissement t[l..r] -> t[l-1..r] heap
|
|
{
|
|
l := l-1
|
|
j := l
|
|
}
|
|
ELSE // selection : t[0] est le + grand et echange avec t[r-1]
|
|
// rearrangement de t[0..r-2]
|
|
{
|
|
INT ex
|
|
ex := t[0]
|
|
t[0] := t[r-1]
|
|
t[r-1] := ex
|
|
r := r-1
|
|
j := 1
|
|
}
|
|
FI
|
|
s := t[j-1]
|
|
test := plusgrand(r, 2*j)
|
|
WHILE test DO
|
|
{
|
|
INT k
|
|
k := 2*j // indice du premier fils de t[~j]
|
|
// on choisit le plus grand des deux
|
|
IF plusgrandstrict(r,k)*plusgrandstrict(t[k], t[k-1]) THEN k:=k+1 FI
|
|
// si le plus grand des deux est plus grand que s on echange avec s
|
|
IF plusgrandstrict(t[k-1],s)
|
|
THEN
|
|
{
|
|
t[j-1] := t[k-1]
|
|
j := k
|
|
test := plusgrand(r, 2*j)
|
|
}
|
|
ELSE test := 0 // une facon de faire un break
|
|
FI
|
|
}
|
|
DONE
|
|
t[j-1] := s
|
|
}
|
|
DONE
|
|
}
|
|
|
|
// fonctions de comparaison entre entiers
|
|
//=======================================
|
|
FUNC INT plusgrandstrict(n,m )
|
|
{
|
|
INT continue, nn, mm
|
|
|
|
continue := n*m
|
|
nn := n
|
|
mm := m
|
|
WHILE continue
|
|
DO
|
|
{
|
|
mm := mm-1
|
|
nn := nn-1
|
|
continue := nn*mm
|
|
}
|
|
DONE
|
|
IF nn THEN RETURN 1 ELSE RETURN 0 FI
|
|
}
|
|
|
|
FUNC INT plusgrand(n,m )
|
|
{
|
|
INT continue, nn, mm
|
|
|
|
continue := n*m
|
|
nn := n
|
|
mm := m
|
|
WHILE continue
|
|
DO
|
|
{
|
|
mm := mm-1
|
|
nn := nn-1
|
|
continue := nn*mm
|
|
}
|
|
DONE
|
|
IF nn THEN RETURN 1 ELSE IF mm THEN RETURN 0 ELSE RETURN 1 FI FI
|
|
}
|