Beispiel zu Quicksort, siehe Skript Seite 15 und 17:


Startsituation:

 -------------------------------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 |
|-------------------------------------------------------|
|  1 17  2  7 22 10 14  3 19 12  6 30 11  8 28  4 21  9 |
 -------------------------------------------------------
   i                       x                          j

(* Merke: x hat den Wert 19 bis das Array partitioniert ist.
 * Erst dann werden neue Werte fuer x bestimmt!
 *)
WHILE a[i] < x DO
 INC(i)
END

 -------------------------------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 |
|-------------------------------------------------------|
|  1 17  2  7 22 10 14  3 19 12  6 30 11  8 28  4 21  9 |
 -------------------------------------------------------
               i                                      j


WHILE a[j] > x DO
 INC(j)
END

 -------------------------------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 |
|-------------------------------------------------------|
|  1 17  2  7 22 10 14  3 19 12  6 30 11  8 28  4 21  9 |
 -------------------------------------------------------
               i                                      j


(* Achtung: Nicht IF a[i] < a[j], sondern IF i < j !!! *)

IF i < j THEN (* hier reicht < statt <= *)
 vertausche a[i] und a[j];
 (* Achtung: jedesmal wenn a[i] und a[j] vertauscht werden i und j um 1 erhoehen: *)
 Inc(i); Inc(j);
END

 -------------------------------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 |
|-------------------------------------------------------|
|  1 17  2  7  9 10 14  3 19 12  6 30 11  8 28  4 21 22 |
 -------------------------------------------------------
                  i                                j


WHILE a[i] < x DO (* x hat noch immer den Wert 19 *)
 INC(i)
END

 -------------------------------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 |
|-------------------------------------------------------|
|  1 17  2  7  9 10 14  3 19 12  6 30 11  8 28  4 21 22 |
 -------------------------------------------------------
                           i                       j


WHILE a[j] > x DO
 INC(j)
END

 -------------------------------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 |
|-------------------------------------------------------|
|  1 17  2  7  9 10 14  3 19 12  6 30 11  8 28  4 21 22 |
 -------------------------------------------------------
                           i                    j


IF i < j THEN
 vertausche a[i] und a[j];
 (* Achtung: jedesmal wenn a[i] und a[j] vertauscht werden i und j um 1 erhoehen: *)
 Inc(i); Inc(j);
END

 -------------------------------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 |
|-------------------------------------------------------|
|  1 17  2  7  9 10 14  3  4 12  6 30 11  8 28 19 21 22 |
 -------------------------------------------------------
                              i              j



WHILE a[i] < x DO (* x hat noch immer den Wert 19 *)
 INC(i)
END

 -------------------------------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 |
|-------------------------------------------------------|
|  1 17  2  7 22 10 14  3 19 12  6 30 11  8 28  4 21  9 |
 -------------------------------------------------------
                                    i        j


WHILE a[j] > x DO
 INC(j)
END

 -------------------------------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 |
|-------------------------------------------------------|
|  1 17  2  7 22 10 14  3 19 12  6 30 11  8 28  4 21  9 |
 -------------------------------------------------------
                                    i     j


IF i < j THEN
 vertausche a[i] und a[j];
 (* Achtung: jedesmal wenn a[i] und a[j] vertauscht werden i und j um 1 erhoehen: *)
 Inc(i); Inc(j);
END

 -------------------------------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 |
|-------------------------------------------------------|
|  1 17  2  7  9 10 14  3  4 12  6  8 11 30 28 19 21 22 |
 -------------------------------------------------------
                                      ij



WHILE a[i] < x DO (* x hat noch immer den Wert 19 *)
 INC(i)
END

 -------------------------------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 |
|-------------------------------------------------------|
|  1 17  2  7 22 10 14  3 19 12  6  8 11 30 28  4 21  9 |
 -------------------------------------------------------
                                       j  i


WHILE a[j] > x DO
 INC(j)
END

 -------------------------------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 |
|-------------------------------------------------------|
|  1 17  2  7 22 10 14  3 19 12  6  8 11 30 28  4 21  9 |
 -------------------------------------------------------
                                       j  i


IF i < j THEN
 vertausche?; (* jetzt nicht mehr tauschen, da i > j *)
END

 -------------------------------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 |
|-------------------------------------------------------|
|  1 17  2  7  9 10 14  3  4 12  6  8 11 30 28 19 21 22 |
 -------------------------------------------------------
                                       j  i

...
UNTIL i > j 

(* Until Schleife wird beendet und das Array zwischem i und j gesplittet
 * und das ganze beginnt von vorne mit den beiden TeilArrays!
 *)

Achtung: Das Splitten hat im Prinzip nichts mit x zu tun,
ausser dass der Wert von x ein Wert aus dem Array ist.

Also: Auf der linken Seite stehen alle Werte kleiner als 19, 
auf der rechten Seite alle Werte groesser als 19
BEZUEGLICH i und j (und nicht bezueglich x (= 19))!

Optimales x: Der optimale Wert von x ist der Wert, der
das Array in 2 gleich grosse Haelften zerlegt, also hier
waere x = 10.5 optimal!

Merke: Es handelt sich hierbei um den MEDIAN, nicht um den Mittelwert!

Beispiel:
102, 2, 200, 1, 812, 100
(1,2,100,102,200,812)

Mittelwert = 202,8333

Median = (100 + 102) / 2 = 101




Beispiel2:

Startsituation:

 ----------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 |
|----------------------------------|
| 17  5 12  8  7  9 18 13  1 15 16 |
 ----------------------------------
   i              x              j

(* Merke: x hat den Wert 9 bis das Array partitioniert ist.
 * Erst dann werden neue Werte fuer x bestimmt!
 *)
WHILE a[i] < x DO
 INC(i)
END

 ----------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 |
|----------------------------------|
| 17  5 12  8  7  9 18 13  1 15 16 |
 ----------------------------------
   i              x              j


WHILE a[j] > x DO
 INC(j)
END

 ----------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 |
|----------------------------------|
| 17  5 12  8  7  9 18 13  1 15 16 |
 ----------------------------------
   i              x        j


(* Achtung: Nicht IF a[i] < a[j], sondern IF i < j !!! *)

IF i < j THEN (* hier reicht < statt <= *)
 vertausche a[i] und a[j];
 (* Achtung: jedesmal wenn a[i] und a[j] vertauscht werden i und j um 1 erhoehen: *)
 Inc(i); Inc(j);
END

 ----------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 |
|----------------------------------|
|  1  5 12  8  7  9 18 13 17 15 16 |
 ----------------------------------
      i           x     j


WHILE a[i] < x DO (* x hat noch immer den Wert 9 *)
 INC(i)
END

 ----------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 |
|----------------------------------|
|  1  5 12  8  7  9 18 13 17 15 16 |
 ----------------------------------
         i        x     j


WHILE a[j] > x DO
 INC(j)
END

 ----------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 |
|----------------------------------|
|  1  5 12  8  7  9 18 13 17 15 16 |
 ----------------------------------
         i        j


IF i < j THEN
 vertausche a[i] und a[j];
 (* Achtung: jedesmal wenn a[i] und a[j] vertauscht werden i und j um 1 erhoehen: *)
 Inc(i); Inc(j);
END

 ----------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 |
|----------------------------------|
|  1  5  9  8  7 12 18 13 17 15 16 |
 ----------------------------------
            i  j


WHILE a[i] < x DO (* x hat noch immer den Wert 19 *)
 INC(i)
END

 ----------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 |
|----------------------------------|
|  1  5  9  8  7 12 18 13 17 15 16 |
 ----------------------------------
               j  i


WHILE a[j] > x DO
 INC(j)
END

 ----------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 |
|----------------------------------|
|  1  5  9  8  7 12 18 13 17 15 16 |
 ----------------------------------
               j  i


IF i < j THEN
 vertausche a[i] und a[j];
 (* Achtung: jedesmal wenn a[i] und a[j] vertauscht werden i und j um 1 erhoehen: *)
 Inc(i); Inc(j);
END

 ----------------------------------
| 00 01 02 03 04 05 06 07 08 09 10 |
|----------------------------------|
|  1  5  9  8  7 12 18 13 17 15 16 |
 ----------------------------------
               j  i

...
UNTIL i > j 

(* Until Schleife wird beendet und das Array zwischem i und j gesplittet
 * und das ganze beginnt von vorne mit den beiden TeilArrays!
 *)