{"id":1019,"date":"2013-07-09T18:49:36","date_gmt":"2013-07-10T01:49:36","guid":{"rendered":"http:\/\/zackmdavis.net\/blog\/?p=1019"},"modified":"2013-07-09T18:57:42","modified_gmt":"2013-07-10T01:57:42","slug":"quicksort-in-fim","status":"publish","type":"post","link":"http:\/\/zackmdavis.net\/blog\/2013\/07\/quicksort-in-fim\/","title":{"rendered":"Quicksort in FIM++"},"content":{"rendered":"

Dear reader, I have got to tell you, fandom is intense<\/em>. One day last October Equestria Daily<\/em> (internet clearinghouse for fans of the animated series My Little Pony: Friendship Is Magic<\/em>) posts a joke proposal<\/a> for a programming language (FIM++) based on the show, and within the week<\/a> there's a working interpreter for it. What does it mean to model a programming language<\/em> after a cartoon<\/em>, you ask? Well, in the show, episodes typically end with our heroine Twilight Sparkle (or after Season Two, Episode Three "Lesson Zero", one of her friends) writing a letter about what she's learned about the magic of friendship to her mentor (and God-Empress of the sun) Princess Celestia. So, then, why not have an esoteric programming langauge where the source code reads like a letter to Princess Celestia? Adorable, right?<\/p>\n

So, this gift having been provided to us courtesy of Karol S.<\/a> and the brony community, let's do<\/em> something with it! More specifically, how about we implement quicksort?\u2014that is a classic<\/em>. What's quicksort? Well, we want to sort a list, right? So\u2014bear with me\u2014we define this partitioning procedure that, given indices into an array, partitions the subarray between those indices into a subsubarray of elements less-than-or-equal-to a given element dubbed the pivot<\/em>, then the pivot itself, then a subsubarray of elements greater than the pivot. How do we do that? Well, let's designate the last element in our subarray as the pivot. Then we're going to scan through all the other elements, and if any of them are less-than-or-equal-to the pivot, we swap it into our first subsubarray and increment a variable keeping track of where the first subsubarray ends. Then, we swap the pivot into place and return its index. In Ruby\u2014<\/p>\n

<\/p>\n

\r\ndef partition(array, p, r)\r\n  i = p-1\r\n  for j in p..(r-1) do\r\n      if array[j] <= array[r]\r\n        i += 1\r\n        array[i], array[j] = array[j], array[i]\r\n      end\r\n  end\r\n  array[i+1], array[r] = array[r], array[i+1]\r\n  i+1\r\nend\r\n<\/pre>\n
Then we can sort an entire array with a bunch of recursive calls to our partitioning procedure:<\/p>\n
\r\ndef quicksort(array, p, r)\r\n  if p < r\r\n    q = partition(array, p, r)\r\n    quicksort(array, p, q-1)\r\n    quicksort(array, q+1, r)\r\n  end\r\nend\r\n\r\n# Let's try it!\r\nmy_array = [9, 5, 4, 11, 2, 10, 6, 3, 8, 12, 1, 7]\r\nquicksort(my_array, 0, my_array.length-1)\r\nprint my_array # => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]\r\n<\/pre>\n
So that's quicksort. With a little more effort, we can do the same thing in FIM++:<\/p>\n
\r\nDear Princess Celestia: Letter about Quicksort:\r\n\r\nI learned about exchange with Applejack, Rainbow Dash, and Rarity.\r\n\r\n  On the page numbered by Rarity of Applejack I read about Sweetie\r\n  Belle.\r\n\r\n  On the page numbered by Rainbow Dash of Applejack I read about\r\n  Scootaloo.\r\n\r\n  On the page numbered by Rarity of Applejack I wrote what I knew\r\n  about Scootaloo.\r\n\r\n  On the page numbered by Rainbow Dash of Applejack I wrote what I\r\n  knew about Sweetie Belle.\r\n\r\nThat's about exchange.\r\n\r\n\r\nI learned about partitioning with Applejack, Rainbow Dash, and Rarity.\r\n\r\n  On the page numbered by Rarity of Applejack I read about Apple\r\n  Bloom.\r\n\r\n  Sweetie Belle made the difference of Rainbow Dash and the number one.\r\n\r\n  Did you know Scootaloo likes Rainbow Dash?\r\n\r\n  I did this while Scootaloo had less than Rarity:\r\n\r\n    On the page numbered by Scootaloo of Applejack I read about\r\n    Diamond Tiara.\r\n\r\n      When Diamond Tiara had not more than Apple Bloom:\r\n\r\n        Sweetie Belle got one more.\r\n\r\n        I did exchange of Applejack, Sweetie Belle, and Scootaloo.\r\n\r\n      That's what I did.\r\n\r\n    Scootaloo got one more.\r\n\r\n  That's what I did.\r\n\r\n  Sweetie Belle got one more.\r\n\r\n  I also caused exchange of Applejack, Sweetie Belle, and Rarity.\r\n\r\nThat's about partitioning with Sweetie Belle.\r\n\r\n\r\nI learned about quicksort with Applejack, Rainbow Dash, and Rarity:\r\n\r\n  When Rainbow Dash had less than Rarity:\r\n\r\n    Fluttershy did partitioning of Applejack, Rainbow Dash, and Rarity.\r\n\r\n    Fluttershy got one less.\r\n\r\n    I caused quicksort of Applejack, Rainbow Dash, and Fluttershy.\r\n\r\n    Fluttershy got two more.\r\n\r\n    I caused quicksort of Applejack, Fluttershy, and Rarity.\r\n\r\n  That's what I did.\r\n\r\nThat's about quicksort.\r\n\r\n\r\nToday I learned:\r\n\r\n  Did you know Applejack likes 9, 5, 4, 11, 2, 10, 6, 3, 8, 12, 1, and 7?\r\n\r\n  Applejack did dictionary of Applejack.\r\n\r\n  I said: Applejack!\r\n\r\n  I did quicksort of Applejack, one, and twelve.\r\n\r\n  I said: Applejack! \r\n\r\nYour Faithful Student,\r\nTwilight Sparkle\r\n<\/pre>\n
Bibliography<\/em><\/strong><\/p>\n
Cormen et al.<\/em>, Introduction to Algorithms<\/em>, third ed'n, \u00a77.1<\/p>\n","protected":false},"excerpt":{"rendered":"
Dear reader, I have got to tell you, fandom is intense. One day last October Equestria Daily (internet clearinghouse for fans of the animated series My Little Pony: Friendship Is Magic) posts a joke proposal for a programming language (FIM++) … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[20],"tags":[42,38,64],"_links":{"self":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts\/1019"}],"collection":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/comments?post=1019"}],"version-history":[{"count":10,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts\/1019\/revisions"}],"predecessor-version":[{"id":1043,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts\/1019\/revisions\/1043"}],"wp:attachment":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/media?parent=1019"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/categories?post=1019"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/tags?post=1019"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}