Con 6 confronti/scambi
Prova con i numeri
+-----+-----+-----+-----+
| x1 | x2 | x3 | x4 |
+-----+-----+-----+-----+------------+
| 100 | 10 | -8 | -25 | (x1 > x2)? | 100 sale di posizione
| 10 | 100 | -8 | -25 | (x2 > x3)? | ...
| 10 | -8 | 100 | -25 | (x3 > x4)? | ...
| 10 | -8 | -25 | 100 | (x1 > x2)? | 100 ha raggiunto la posizione definitiva
| -8 | 10 | -25 | 100 | (x2 > x3)? | 10 sale di posizione
| -8 | -25 | 10 | 100 | (x1 > x2)? | 10 ha raggiunto la posizione definitiva
| -25 | -8 | 10 | 100 | | -8 ha raggiunto la posizione definitiva
+-----+-----+-----+-----+------------+ In 1° posizione rimane il valore minimo!
La sequenza di confronti (e scambi) segue l’algoritmo Bubble Sort.
Codifica Pascal
If x1 > x2 Then
Begin
temp:=x1 ;
x1 :=x2 ;
x2 :=temp;
End;
If x2 > x3 Then
Begin
temp:=x2 ;
x2 :=x3 ;
x3 :=temp;
End;
If x3 > x4 Then
Begin
temp:=x3 ;
x3 :=x4 ;
x4 :=temp;
End;
If x1 > x2 Then
Begin
temp:=x1 ;
x1 :=x2 ;
x2 :=temp;
End;
If x2 > x3 Then
Begin
temp:=x2 ;
x2 :=x3 ;
x3 :=temp;
End;
If x1 > x2 Then
Begin
temp:=x1 ;
x1 :=x2 ;
x2 :=temp;
End;
Con 5 confronti/scambi
Prova con i numeri
+-----+-----+-----+-----+
| x1 | x2 | x3 | x4 |
+-----+-----+-----+-----+------------+
| 100 | -8 | 10 | -25 | (x1 > x2)? |
| -8 | 100 | 10 | -25 | (x3 > x4)? |
| -8 | 100 | -25 | 10 | (x1 > x3)? |
| -25 | 100 | -8 | 10 | (x2 > x4)? |
| -25 | 10 | -8 | 100 | (x2 > x3)? |
| -25 | -8 | 10 | 100 | |
+-----+-----+-----+-----+------------+
Ci sono 4 valori da ordinare
+----+----+----+----+
| x1 | x2 | x3 | x4 | Prima
+----+----+----+----+
| r1 | r2 | r3 | r4 | Dopo
+----+----+----+----+
+----+----+----+----+------------+
| x1 | x2 | x3 | x4 | (x1 > x2)? | Confronta x1 con x2 e se necessario effettua lo scambio dei valori
+-\/-+-\/-+----+----+------------+
| m1 | M1 | x3 | x4 | | m1 è un minimo locale, M1 è un massimo locale.
+----+----+----+----+------------+
+----+----+----+----+------------+
| x1 | x2 | x3 | x4 | (x1 > x2)? |
+-\/-+-\/-+----+----+------------+
| m1 | M1 | x3 | x4 | (x3 > x4)? | Confronta x3 con x4
+----+----+-\/-+-\/-+------------+
| m1 | M1 | m2 | M2 | | m2 è un minimo locale, M2 è un massimo locale.
+----+----+----+----+------------+
+----+----+----+----+------------+
| x1 | x2 | x3 | x4 | (x1 > x2)? |
+-\/-+-\/-+----+----+------------+
| m1 | M1 | x3 | x4 | (x3 > x4)? |
+----+----+-\/-+-\/-+------------+
| m1 | M1 | m2 | M2 | (m1 > m2)? | Confronta m1 e m2, minimi locali
+-\/-+----+-\/-+----+------------+
| r1 | M1 | i1 | M2 | | In 1° posizione il minimo globale, in 3° posizione un valore intermedio
+----+----+----+----+------------+
+----+----+----+----+------------+
| x1 | x2 | x3 | x4 | (x1 > x2)? |
+-\/-+-\/-+----+----+------------+
| m1 | M1 | x3 | x4 | (x3 > x4)? |
+----+----+-\/-+-\/-+------------+
| m1 | M1 | m2 | M2 | (m1 > m2)? |
+-\/-+----+-\/-+----+------------+
| r1 | M1 | i1 | M2 | (M1 > M2)? | Confronta M1 e M2, massimi locali
+----+-\/-+----+-\/-+------------+
| r1 | i2 | i1 | r4 | | In 4° posizione il massimo globale, in 2° posizione un valore intermedio
+----+----+----+----+------------+
+----+----+----+----+------------+
| x1 | x2 | x3 | x4 | (x1 > x2)? |
+-\/-+-\/-+----+----+------------+
| m1 | M1 | x3 | x4 | (x3 > x4)? |
+----+----+-\/-+-\/-+------------+
| m1 | M1 | m2 | M2 | (m1 > m2)? |
+-\/-+----+-\/-+----+------------+
| r1 | M1 | i1 | M2 | (M1 > M2)? |
+----+-\/-+----+-\/-+------------+
| r1 | i2 | i1 | r4 | (i2 > i1)? | Confronta i1 e i2, valori intermedi
+----+-\/-+-\/-+----+------------+
| r1 | r2 | r3 | r4 | |
+----+----+----+----+------------+
Codifica
If x1 > x2 Then
Begin
temp:=x1 ;
x1 :=x2 ;
x2 :=temp;
End;
If x3 > x4 Then
Begin
temp:=x3 ;
x3 :=x4 ;
x4 :=temp;
End;
If x1 > x3 Then
Begin
temp:=x1 ;
x1 :=x3 ;
x3 :=temp;
End;
If x2 > x4 Then
Begin
temp:=x2 ;
x2 :=x4 ;
x4 :=temp;
End;
If x2 > x3 Then
Begin
temp:=x2 ;
x2 :=x3 ;
x3 :=temp;
End;