Quicksort pseudocode in Building Skills in Python 2.6.5

[JT Longino]

Exercise 3 of Chapter 15.9 (List Exercises) provides pseudocode for an implementation of Quicksort.

Swap To Partition.
while ls < hs:
    If a[ls].key ≤ a[middle].key: increment ls by 1. Move the low boundary of the partitioning.
    If a[ls].key > a[middle].key: swap the values a[ls] and a[middle].
    If a[hs].key ≥ a[middle].key: decrement hs by 1. Move the high boundary of the partitioning.
    If a[hs].key < a[middle].key: swap the values a[hs] and a[middle].

I'm not sure whether the swap cases are supposed to be mutually exclusive from the increment statements (elif) or independent statements that might both be executed.

Either way, I'm not sure this pseudocode gives the correct result for the following sequence:

[1, 2, 10, 11, 12, 13, 3, 14, 15, 16, 17, 4, 5]

Since both 1 and 2 (assuming both if statements are executed) are < 3, 3 remains at the middle position after dealing with ls. Since 5 >= 3, it remains at the end position and gets sorted with the [middle+1, hi] partition rather than the [lo, middle] partition where it belongs.

Is there something I'm missing?

[Steven Lott]

I haven't looked at this in a long time. Python 2.6 hasn't been supported for years.

Of of two things must be done with ls (either swap or increment) and one of two things must be done with hs (either swap or decrement). This is really two if statements with explicit elif clauses. I think I was trying to avoid simply proving the Python code in this example.

--
You received this message because you are subscribed to the Google Groups "Building Skills Books" group.
To unsubscribe from this group and stop receiving emails from it, send an email to building-skills-books+unsub...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

"It May Be A Hack, But It Works"