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)

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