Instantly share code, notes, and snippets.

# fjcaetano/gist:b0c00a889dc2a17efad9 Created Jun 5, 2014

Quicksort in Swift
 var randomNumbers = [42, 12, 88, 62, 63, 56, 1, 77, 88, 97, 97, 20, 45, 91, 62, 2, 15, 31, 59, 5] func partition(v: Int[], left: Int, right: Int) -> Int { var i = left for j in (left + 1)..(right + 1) { if v[j] < v[left] { i += 1 (v[i], v[j]) = (v[j], v[i]) } } (v[i], v[left]) = (v[left], v[i]) return i } func quicksort(v: Int[], left: Int, right: Int) { if right > left { let pivotIndex = partition(v, left, right) quicksort(v, left, pivotIndex - 1) quicksort(v, pivotIndex + 1, right) } } quicksort(randomNumbers, 0, randomNumbers.count-1)

### rabuf commented Jun 5, 2014

 Just starting with reading the language book, but wouldn't `...` be useful instead of `..`? Then you could omit the `+ 1` in `right + 1`.

### sahat commented Jun 5, 2014

 @rabuf What is the difference between `...` and `..`?

### Shahn-Auronas commented Jun 5, 2014

 .. Up to and excluding "<" ... Is up to and including "<="

### tibbon commented Jun 5, 2014

 `````` “Use .. to make a range that omits its upper value, and use ... to make a range that includes both values.” `````` Excerpt From: Apple Inc. “The Swift Programming Language.” iBooks. https://itun.es/us/jEUH0.l

### SnakeDoc commented Jun 5, 2014

 Jeeze... I have to download and install iTunes just to view their ebook about their programming language... really Apple?

### rabuf commented Jun 5, 2014

 @sahat, I should've mentioned that, but @Shahn-Auronas and @tibbon both covered it. `..` goes to one below the right hand value, `...` includes the right hand value. For the math inclined, if the lower bound is `x` and the upper bound is `y`, it's the difference between `[x,y)` and `[x,y]`. In this instance I'm not sure that `...` is better, but dropping the extra `+ 1` might aid readability, and it reduces the locations where an error can occur in the code. On the other hand, `..` and `...` are so close to each other it leaves the possibility of a typo open if you find yourself using both. Perhaps sticking with `..` or `...` as a convention makes sense. I was informed of Perl6's notation for ranges (range operators), I rather like it. Though Swift might be too far along to change now, reducing the chance of an error by adding or omitting a single `.` would be nice. Plus it adds 2 more range generator features. This particular case would be represented by `left ^.. right`.

### rabuf commented Jun 5, 2014

 @SnakeDoc - Here you go, The Swift Programming Language.

### SnakeDoc commented Jun 5, 2014

 @rabuf much appreciated :)

### vpdn commented Jun 5, 2014

 Why not just filter? ``````func sort(var list:Int[]) -> (Int[]) { if (list.count<=1) { return list } let pivot = list[0] list.removeAtIndex(0) let smaller = sort(list.filter { return \$0 <= pivot }) let larger = sort(list.filter { return \$0 > pivot }) var list = smaller list += pivot list += larger return list } ``````

### kmikael commented Jun 5, 2014

 @vpdn's method, but compacter and using the fact that `list.removeAtIndex` returns the removed element, Swift's implicit closure returns and the fact that the list doesn't need to be sorted if it has a count of one either. ``````func quicksort(var list: Int[]) -> Int[] { if list.count <= 1 { return list } let pivot = list.removeAtIndex(0) return quicksort(list.filter { \$0 <= pivot }) + [pivot] + quicksort(list.filter { \$0 > pivot }) } ``````

### vpdn commented Jun 5, 2014

 @kmikael Sweet! This reads like a declaration, just as it should be. Kinda non intuitive that removeAtIndex(i) returns the object at i, good to know. Thanks!

### kmikael commented Jun 5, 2014

 And finally, with generics :) This sorts lists of anything that implement `<` ``````func quicksort(var list: T[]) -> T[] { if list.count <= 1 { return list } let pivot = list.removeAtIndex(0) return quicksort(list.filter { \$0 <= pivot }) + [pivot] + quicksort(list.filter { \$0 > pivot }) } let list: Int[] = [1, -5, 9, 8, 110, 42, -70, 0, 3, 4, 5, 2, 2, 1, 0, 1] let sortedList = quicksort(list) let strings = ["a", "c", "d", "a", "e", "b", "a", "f", "e"] let sortedStrings = quicksort(strings) struct Vector: Comparable { var x: Double = 0.0, y: Double = 0.0 } func <(p: Vector, q: Vector) -> Bool { return p.x < q.x && p.y < q.y } func ==(p: Vector, q: Vector) -> Bool { return p.x == q.x && p.y == q.y } let vectors = [Vector(x: 1.0, y: 2.0), Vector(x: 0.0, y: 1.0)] let sortedVectors = quicksort(vectors) ``````

### harlanhaskins commented Jun 5, 2014

 Filtering makes this way less efficient. You're doing an `O(n)` operation through the list multiple times, which dramatically slows down execution. You can accomplish the same thing by using a switch statement and traversing the list one time. That way you cut down on list traversals. ```func quicksort(var list: T[]) -> T[] { if list.count <= 1 { return list } let pivot = list[0] var smallerList = T[]() var equalList = T[]() var biggerList = T[]() for x in list { switch x { case let x where x < pivot: smallerList.append(x) case let x where x == pivot: equalList.append(x) case let x where x > pivot: biggerList.append(x) default: break } } return quicksort(smallerList) + equalList + quicksort(biggerList) }``` Plus, if we maintain a list of equal values, then the complexity becomes `O(n * log(unique n's))`

### jkleiser commented Jun 6, 2014

 Thanks for these nice examples! I wanted to see what kind of error messages I would get if I inserted a string item in the randomNumbers array, like var randomNumbers = [42, "x", 12, ...]. I then tried to run using 'xcrun swift -i quicksort.swift' or compile using 'xcrun swift quicksort.swift', but none of these gave me any response at all. I waited a few seconds, then typed Ctrl-C. I did the same with Flávio's and Harlan's versions. Maybe there are other ways to get a reasonable error message from Swift ...?

### vpdn commented Jun 6, 2014

 Tried to quantify @harlanhaskins's "dramatically": The overhead seems to be quite considerable, given a larger list of arcr4andom UInt32s. At 1M entries, the filter variant is roughly 26% slower (40.078sec vs 31.734sec), at 10M roughly 35% (456.69sec vs 337.18sec). For 1k entries, both implementations are in the tens of milliseconds.

### jkleiser commented Jun 10, 2014

 I tried a simpler example involving a bad array (string/number combination), like this one: `let myArr = [42, 12, "foo", 88]` `println("Hello Swift World ", myArr)` ... and when I do the `xcrun swift bad.swift` I get a proper error message: `error: cannot convert the expression's type 'Array' to type 'ArrayLiteralConvertible'` ... but when I do the same with Flávio's or Harlan's quicksort, I get no response at all, as far as I can see.

### m4rr commented Jul 4, 2014

 Just `quickSort(&a, 0..a.count)`

### WyattZhang commented Nov 16, 2014

 little bit improved with new swift grammar ```func partition(inout dataList: [Int], low: Int, high: Int) -> Int { var pivotPos = low var pivot = dataList[low] for var i = low + 1; i <= high; i++ { if dataList[i] < pivot && ++pivotPos != i { (dataList[pivotPos], dataList[i]) = (dataList[i], dataList[pivotPos]) } } (dataList[low], dataList[pivotPos]) = (dataList[pivotPos], dataList[low]) return pivotPos } func quickSort(inout dataList: [Int], left: Int, right: Int) { if left < right { var pivotPos = partition(&dataList, left, right) quickSort(&dataList, left, pivotPos - 1) quickSort(&dataList, pivotPos + 1, right) } } var dataList = [42, 12, 88, 62, 63, 56, 1, 77, 88, 97, 97, 20, 45, 91, 62, 2, 15, 31, 59, 5] quickSort(&dataList, 0, dataList.count - 1)```

### KaanPoyraz commented Aug 16, 2018

 iOS 12 & Swift: The Complete Developer Course (Project base) https://www.99udemycoupon.com/2018/08/100-off-udmy-free-coupon-ios-12-swift.html