Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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 ..?

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

tibbon commented Jun 5, 2014

@sahat -

 “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.

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<T: Comparable>(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)

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<T: Comparable>(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.

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)

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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment