If anyone's wondering, yes, there's a quickSort function already in the Swift standard library (no import required):<p><pre><code> var ar = [3456,45,53567,356,7225,47858]
quickSort(&ar, Range(start: ar.startIndex, end: ar.endIndex))
// [45, 356, 3456, 7225, 47858, 53567]
</code></pre>
There's also a version that let's you specify the "less" comparator.
I was surprised this example didn't take advantage of Swift's built-in Comparable protocol, so I rewrote it! I also wrote an example of how you can implement the Comparable protocol for a struct, so that they can then be sorted.<p><a href="https://gist.github.com/dstaley/e7171375d3f5cb9f2fe4" rel="nofollow">https://gist.github.com/dstaley/e7171375d3f5cb9f2fe4</a>
This actually highlights one area where I find Swift slightly deficient. I was just thinking earlier today that Swift is remarkably close to my dream language, i.e. incorporates the great features of many languages I've come in contact with. But one thing it lacks is Haskell's amazing list comprehension, which helps make Haskell quicksort so succinct.
Had a chat about Swift over lunch today, one topic was the choice of using .. and ... to represent ranges. Interesting to see the comments of the gist focus on this as well. Surely is a confusing and potentially dangerous syntax.
Hoare's original paper from 1962.<p><a href="http://comjnl.oxfordjournals.org/content/5/1/10.full.pdf+html" rel="nofollow">http://comjnl.oxfordjournals.org/content/5/1/10.full.pdf+htm...</a><p>There are reasons not to perform quickSort the way people did fifty years ago. Data sets are larger and worst case time for quickSort approach 0(n^2) when data is already ordered and pivots are selected in-order. Randomizing pivot selection mitigates this back toward O(log n).<p>All that mutation and pointer swapping are artifacts of the way things used to have to be done by programmers. And they're useful as academic exercises. Hoare's algorithm is really fucking brilliant. But mapping and filtering in a functional style, makes more sense than dotting the 'i's and 'j's if someone is going to be reading and maintaining the code. There's a reason people don't use C to program mobile devices.<p>Moreover, while Hoare's original algorithm was designed to work in place, the idea of working in place is less coherent today. When we strive to distribute and parallelize big nasty resource intensive jobs, what does "in-place" mean? See Leslie Lamport, <i>Thinking for Programmers</i> at about time = 36:00<p><a href="http://channel9.msdn.com/Events/Build/2014/3-642" rel="nofollow">http://channel9.msdn.com/Events/Build/2014/3-642</a><p>And even on a non-distributed system, when are we really coming up against the bounds of 'fast memory' these days? A serious problem that stretches 16 GigaBytes of RAM is less than $10,000 from 64 GigaBytes...or $200 from an SSD and using 'slow memory'.<p>Of course if we are parallelizing, we can even do it on one machine and again, what is 'in-place'? The caches? Again which ones and at what level. The Swift code (or Java or C#) may look like C, but it's not. It may be garbage collected, JIT'd, byte coded, and micro-coded all before it hits the mulit-stage branch predicting pipeline from several levels of cache reading from code pages that may have gone in and out to disk as threads and tasks switch.<p>'Place' might just mean somewhere. But probably somewheres.
From that, it's not too hard how people could think it was influenced by Go (though it apparently wasn't): <a href="http://play.golang.org/p/oWNRd0D2Zp" rel="nofollow">http://play.golang.org/p/oWNRd0D2Zp</a> looks superficially very similar
I put your code on npm: <a href="https://www.npmjs.org/package/quicksort.swift" rel="nofollow">https://www.npmjs.org/package/quicksort.swift</a><p>Edit: ...and then swiftly unpublished. It is unclear to me the legal issues involved in forking and publishing unlicensed gists.<p><a href="http://stackoverflow.com/questions/4007674/whats-the-default-license-of-code-published-at-github" rel="nofollow">http://stackoverflow.com/questions/4007674/whats-the-default...</a>
Wow... seems like a nightmare for several reasons:<p>>Naming Constants and Variables<p>>You can use almost any character you like for constant and<p>>variable names, including Unicode characters:<p>>let π = 3.14159<p>>let 你好 = "你好世界"<p>>let 🐶🐮 = "dogcow"<p><a href="https://developer.apple.com/library/prerelease/ios/documentation/Swift/Conceptual/Swift_Programming_Language/TheBasics.html#//apple_ref/doc/uid/TP40014097-CH5-XID_399" rel="nofollow">https://developer.apple.com/library/prerelease/ios/documenta...</a>