Here is a better description of the code:

Take $array=3,3,6,2,4,6,7,9,2

1. Set pivot to average index of 1st and last element to be sorted:

code:
$p=$L+($U-$L)/2
3,3,6,2,4,6,7,9,2


2. Exchange the pivot value with the lower value:

code:
$t=$a[$L]
$A[$L]=$A[$P]
$A[$P]=$t
4,3,6,2,3,6,7,9,2

3. Leave pivot point alone, and working with the other elements in the set, going from left to right, find a number greater than the pivot value.. working from right to left find a number less than the pivot value.

code:
$i=$L+1
$j=$U
:L1
   While ($i<$j) AND $A[$L] > $A[$i]
    $i=$i+1
   Loop
   While ($j>=$i) AND $A[$j] > $A[$L]
    $j=$j-1
   Loop
4,3,6,2,3,6,7,9,2

4. Swap these numbers.

code:
   IF $i >= $j goto L2 ENDIF
   $t=$A[$i]
   $A[$i]=$A[$j]
   $A[$j]=$t
4,3,2,2,3,6,7,9,6

5. Continue to the right to find a larger number than the pivot, and to the left to find a smaller number. Repeat process.

code:
   $j=$j-1
   $i=$i+1
   Goto L1
4,3,2,2,3,6,7,9,6

6. If no other numbers to swap are found, exit loop.

code:
   IF $i >= $j goto L2 ENDIF
4,3,2,2,3,6,7,9,6

7. Swap pivot with the location the left and the right converge. Notice that the pivot is sorted and you can now split the array into two sets of numbers.

code:
   $t=$a[$l]
   $a[$l]=$a[$j]
   $a[$j]=$t
3,3,2,2,4,6,7,9,6

8. Set pointer to index where pivot ends up.

code:
   $m=$j
In this case $j is 4 so $m is set to 4

9. If set on the left has fewer or the same number of elements as the one on the right, put $m+1 index on the left stack and the right index on the right stack. Set upper index to the element left of the pivot. Otherwise do the reverse.

code:
   If $m-$l <= $u - $m
    If $m+1 < $u
     $ls[$sp]=$m+1
     $us[$sp]=$u
     $sp=$sp+1
    Endif
    $u=$m-1
   Else
    If $m-1 > $l
     $ls[$sp]=$l
     $us[$sp]=$m-1
     $sp=$sp+1
   Endif
3,3,2,2,4,6,7,9,6

StackL=5,0,0,0,0,0...
StackU=8,0,0,0,0,0...

Stack pointer changed to 1
Upper element of set = 3
Lower element of set = 0

3,3,2,2,4,6,7,9,6

9. Repeat process from 1 to 7. (loop)

a. swap pivot:

3,3,2,2, 4,[6,7,9,6]

2,3,3,2, 4, [6,7,9,6]

b. swap from greater than pivot from left with less than pivot from right:
2,3,3,2, 4,[6,7,9,6]

2,2,3,3, 4, [6,7,9,6]
-- no change in this case --
c. when right and left converge, swap pivot with convergence.

2,2,3,3, 4, [6,7,9,6]

Because this set is now sorted, no more swaps will take place.

10. The item on the stack is pulled off and the process is repeated until the sort is complete.

code:
While $sp >=0
$l=$ls[$sp]
$u=$us[$sp]
The set 6,7,9,6 is pointed to by the 5 and 8 of the stack pointer

The process is repeated for these:

choose pivot:
[2,2,3,3,4,] 6,7,9,6

find numbers to swap:
[2,2,3,3,4,] 7,6,9,6

[2,2,3,3,4,] 7,6,6,9

swap pivot into place where right and left meet:

[2,2,3,3,4,] 6,6,7,9

11. Sort finished:

2,2,3,3,4,6,6,7,9

Total swaps = 9
This is more efficient with larger data sets
Any questions? (I apologize.. I had pointers showing what numbers were related to what, but i had to delete them because they weren't lining up correctly.)

Brian

[ 27. September 2002, 23:20: Message edited by: BrianTX ]