Quicksort in Swift

gistfile1.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)

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

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

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

@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

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

@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 - Here you go, The Swift Programming Language.

@rabuf much appreciated :)

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

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

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

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.

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)

This is your solution with a bit modification for Swift 5:

var randomNumbers = [42, 12, 88, 62, 63, 56, 1, 77, 88, 97, 97, 20, 45, 91, 62, 2, 15, 31, 59, 5]

// MARK: - Solution 1 : Naive
func quicksort1<T: Comparable>(_ list: [T]) -> [T] {
	if list.count <= 1 {
		return list
	}

	let pivot = list.randomElement() ?? 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 quicksort1(smallerList) + equalList + quicksort1(biggerList)
}
quicksort1(randomNumbers)

// solution 1 with array extension
extension Array where Element: Comparable {
	func quicksort1() -> [Element] {
		let list = self
		if list.count <= 1 {
			return list
		}

		let pivot = list.randomElement() ?? list[0]

		var smallerList = [Element]()
		var equalList = [Element]()
		var biggerList = [Element]()

		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 smallerList.quicksort1() + equalList + biggerList.quicksort1()
	}
}
randomNumbers.quicksort1()