Tired of the standard textbook descriptions of the Quicksort algorithm? Here’s a rhyming presentation suitable for all ages 🙂
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
A base-ball and a truck, a large shawl with a puck lie in the dormitory in order desultory. I should clean it up, I ought to tidy up, but sorting takes time, it can cost many a dime! "It's untrue that's expensive", replied Sam a bit pensive. "Tony Hoare and other men, showed that sorting's N log N." "All right then", I said, "Let's do it. Go ahead." The result will be prime: sorting in quasilinear time! A quick sort is driven by an item named pivot. Our primary ambition is build a partition where pivot is placed with items well spaced: where small ones go sinister; but big ones, right administer. As pivot "puck" I choose, so no one is confused. The items I partition with only one omission: partitioning in-place can be a tricky case; I will not flesh it out, go read to clear any doubt! There's no way we get stuck while partitioning with "puck", after switching it with "truck". A base-ball and a puck, a large shawl with a truck, partition the dormitory in order mandatory. A ball's smaller than a puck, which is smaller than shawls or trucks. If you think this is heretical, just assume order alphabetical. Sam said, "With your move, of which I fully approve, we're in a good position to progress in our mission. Based on the built partition, we now have the permission to split the work in two — what an excellent breakthrough!" A base-ball and a puck, partitioning we will; from the shawl with the truck, a partition we'll distill. Processing a pair, even with great care, won't be too much work — no reason for a irk. But wait, there's more — to the Quicksort algorithm by Sir C. A. R. Hoare. Partitioning a pair is just the same, I swear, as ordering the two — correctness will ensue. By binary splitting, in logarithmic sittings, we jump to the base case of the sorted ranking chase. The base-ball and the puck, partitioned they are; a large shawl and a truck, are well ordered so far. A room that was chaotic, a task a tad robotic, the dormitory is neat: we can all feel upbeat. There's still a final catch to ensure you win the match. Be careful what method you're using whenever the pivot you're choosing. A badly picked pivot can really, truly limit performance of Quicksort: runtime will not be short, you will be disappointed, when N log N you expect, but N times N you get! |
As a reading guide, here’s a matching pseudo-code partial implementation that follows the procedure described in the rhyme. Enjoy your holidays!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
quicksort (a: ARRAY[G]) local pivot: G p: INTEGER do if a.count > 1 then pivot := -- pick an element in 'a' p := partition (a, pivot) quicksort (a[0..p)) quicksort (a[p..a.count)) end -- empty and singleton arrays are trivially sorted ensure is_sorted (a) elements (a) = old elements (a) end partition (a: ARRAY[G], pivot: G): (p: INTEGER) require a.count > 0 ensure 0 <= p <= a.count forall i :: 0 <= i < p ==> a[i] <= pivot forall i :: p <= i < a.count ==> pivot <= a[i] elements (a) = old elements (a) end |