StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<blockquote> <p>where is the actual comparison/swap done on two elements for a re-order? Is this handled by the <code>Ord</code> (ordered) type definition itself. So the type enforces this condition of being ordered?</p> </blockquote> <h2>What does <code>Ord</code> mean?</h2> <p><code>Ord</code> just means that <code>a</code> should be comparable with itself or in stricter terms operations such as <code>></code>, <code><</code>, and <code>==</code> should be defined for <code>a</code>. You can think of it as a constraint on the method.</p> <h2>So, where is the ordering done?</h2> <p>And the answer is the last pattern:</p> <pre><code>quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater) where lesser = filter (< p) xs greater = filter (>= p) xs </code></pre> <p>At run time, the program is going to get an array and the array must meet either of these two patterns:</p> <p>Pattern 1#: It is empty, in which case the function returns that same empty array and stops.</p> <p>Pattern 2#: It is not empty or in other words, there is a head element <code>p</code> appended to a tailing array <code>xs</code>. In such a case, the function is told to put <code>p</code> in the middle, put all elements of <code>xs</code> that are less than <code>p</code> on the left (as defined by <code>lesser</code>) of <code>p</code> and all elements of <code>xs</code> that are greater than or equal to <code>p</code> on the right of <code>p</code>. Furthermore, the function is finally told to apply itself (i.e., the same function <code>quicksort</code>) on <code>lesser</code> (which as we defined above, is the array on the left hand side of <code>p</code>) and <code>greater</code> (which as we defined above, is the array on the right hand side of <code>p</code>). As you can see, this will go on till you are left with a zero sized array and pattern 1# terminates the function.</p> <p>Finally, whenever those recursive calls terminate the function shall return the array:</p> <pre><code>sortedlesser ++ p ++ sortedgreater </code></pre> <p>where <code>sortedlesser</code> is the array that resulted from the application of <code>quicksort</code> on <code>lesser</code> and <code>sortedgreater</code> is the array that resulted from the application of <code>quicksort</code> on <code>greater</code>.</p> <h2>Wait… are we not duplicating p again and again?</h2> <blockquote> <p>the 'greater' predicate defines items '>= p' (the pivot), so doesn't this mean we'll end up with an extra pivot [p] in resulting list of the function, due to the '++ [p]' item?</p> </blockquote> <p>No, this is not how pattern matching works. It is saying all elements in <code>xs</code> that are greater than or equal to <code>p</code>. By definition <code>p</code> itself is out of <code>xs</code>. If there are duplicates of <code>p</code> in <code>xs</code> then they will fall on the right hand side. Note that this choice will preserve the natural ordering of the original array.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload