Instantly share code, notes, and snippets.

Embed
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

This comment has been minimized.

Show comment
Hide comment
@rabuf

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

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

This comment has been minimized.

Show comment
Hide comment
@sahat

sahat Jun 5, 2014

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

sahat commented Jun 5, 2014

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

@Shahn-Auronas

This comment has been minimized.

Show comment
Hide comment
@Shahn-Auronas

Shahn-Auronas Jun 5, 2014

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

Shahn-Auronas commented Jun 5, 2014

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

@tibbon

This comment has been minimized.

Show comment
Hide comment
@tibbon

tibbon 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

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

This comment has been minimized.

Show comment
Hide comment
@SnakeDoc

SnakeDoc Jun 5, 2014

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

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

This comment has been minimized.

Show comment
Hide comment
@rabuf

rabuf 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

@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

This comment has been minimized.

Show comment
Hide comment
@rabuf

rabuf commented Jun 5, 2014

@SnakeDoc

This comment has been minimized.

Show comment
Hide comment
@SnakeDoc

SnakeDoc Jun 5, 2014

@rabuf much appreciated :)

SnakeDoc commented Jun 5, 2014

@rabuf much appreciated :)

@vpdn

This comment has been minimized.

Show comment
Hide comment
@vpdn

vpdn 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
}

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

This comment has been minimized.

Show comment
Hide comment
@kmikael

kmikael 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 })
}

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

This comment has been minimized.

Show comment
Hide comment
@vpdn

vpdn 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!

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

This comment has been minimized.

Show comment
Hide comment
@kmikael

kmikael 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)

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)
@harlanhaskins

This comment has been minimized.

Show comment
Hide comment
@harlanhaskins

harlanhaskins 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<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))

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

This comment has been minimized.

Show comment
Hide comment
@jkleiser

jkleiser 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 ...?

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

This comment has been minimized.

Show comment
Hide comment
@vpdn

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

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

This comment has been minimized.

Show comment
Hide comment
@jkleiser

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

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

This comment has been minimized.

Show comment
Hide comment
@m4rr

m4rr Jul 4, 2014

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

m4rr commented Jul 4, 2014

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

@WyattZhang

This comment has been minimized.

Show comment
Hide comment
@WyattZhang

WyattZhang 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)

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

This comment has been minimized.

Show comment
Hide comment
@KaanPoyraz

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment