import Foundation

/*

Easy to understand but not very efficient.

You can find more swift algorithms on https://github.com/raywenderlich/swift-algorithm-club

*/

func quicksort<T: Comparable>(_ a: [T]) -> [T] {

guard a.count > 1 else { return a }

let pivot = a[a.count/2]

let less = a.filter { $0 < pivot }

let equal = a.filter { $0 == pivot }

let greater = a.filter { $0 > pivot }

return quicksort(less) + equal + quicksort(greater)

// MARK: - Lomuto

/*

Lomuto's partitioning algorithm.

This is conceptually simpler than Hoare's original scheme but less efficient.

The return value is the index of the pivot element in the new array. The left

partition is [low...p-1]; the right partition is [p+1...high], where p is the

return value.

The left partition includes all values smaller than or equal to the pivot, so

if the pivot value occurs more than once, its duplicates will be found in the

left partition.

*/

func partitionLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int {

// We always use the highest item as the pivot.

let pivot = a[high]

// This loop partitions the array into four (possibly empty) regions:

// [low ... i] contains all values <= pivot,

// [i+1 ... j-1] contains all values > pivot,

// [j ... high-1] are values we haven't looked at yet,

// [high ] is the pivot value.

var i = low

for j in low..<high {

if a[j] <= pivot {

(a[i], a[j]) = (a[j], a[i])

i += 1

}

}

// Swap the pivot element with the first element that is greater than

// the pivot. Now the pivot sits between the <= and > regions and the

// array is properly partitioned.

(a[i], a[high]) = (a[high], a[i])

return i

/*

Recursive, in-place version that uses Lomuto's partioning scheme.

*/

func quicksortLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) {

if low < high {

let p = partitionLomuto(&a, low: low, high: high)

quicksortLomuto(&a, low: low, high: p - 1)

quicksortLomuto(&a, low: p + 1, high: high)

}

// MARK: - Hoare partitioning

/*

Hoare's partitioning scheme.

The return value is NOT necessarily the index of the pivot element in the

new array. Instead, the array is partitioned into [low...p] and [p+1...high],

where p is the return value. The pivot value is placed somewhere inside one

of the two partitions, but the algorithm doesn't tell you which one or where.

If the pivot value occurs more than once, then some instances may appear in

the left partition and others may appear in the right partition.

Hoare scheme is more efficient than Lomuto's partition scheme; it performs

fewer swaps.

*/

func partitionHoare<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int {

let pivot = a[low]

var i = low - 1

var j = high + 1

while true {

repeat { j -= 1 } while a[j] > pivot

repeat { i += 1 } while a[i] < pivot

if i < j {

a.swapAt(i, j)

} else {

return j

}

}

/*

Recursive, in-place version that uses Hoare's partioning scheme. Because of

the choice of pivot, this performs badly if the array is already sorted.

*/

func quicksortHoare<T: Comparable>(_ a: inout [T], low: Int, high: Int) {

if low < high {

let p = partitionHoare(&a, low: low, high: high)

quicksortHoare(&a, low: low, high: p)

quicksortHoare(&a, low: p + 1, high: high)

}

// MARK: - Randomized sort

/* Returns a random integer in the range min...max, inclusive. */

public func random(min: Int, max: Int) -> Int {

assert(min < max)

return min + Int(arc4random_uniform(UInt32(max - min + 1)))

/*

Uses a random pivot index. On average, this results in a well-balanced split

of the input array.

*/

func quicksortRandom<T: Comparable>(_ a: inout [T], low: Int, high: Int) {

if low < high {

// Create a random pivot index in the range [low...high].

let pivotIndex = random(min: low, max: high)

// Because the Lomuto scheme expects a[high] to be the pivot entry, swap

// a[pivotIndex] with a[high] to put the pivot element at the end.

(a[pivotIndex], a[high]) = (a[high], a[pivotIndex])

let p = partitionLomuto(&a, low: low, high: high)

quicksortRandom(&a, low: low, high: p - 1)

quicksortRandom(&a, low: p + 1, high: high)

}

// MARK: - Dutch national flag partitioning

/*

Swift's swap() doesn't like it if the items you're trying to swap refer to

the same memory location. This little wrapper simply ignores such swaps.

*/

public func swap<T>(_ a: inout [T], _ i: Int, _ j: Int) {

if i != j {

a.swapAt(i, j)

}

/*

Dutch national flag partitioning

Partitions the array into three sections: all element smaller than the pivot,

all elements equal to the pivot, and all larger elements.

This makes for a more efficient Quicksort if the array contains many duplicate

elements.

Returns a tuple with the start and end index of the middle area. For example,

on [0,1,2,3,3,3,4,5] it returns (3, 5). Note: These indices are relative to 0,

not to "low"!

The number of occurrences of the pivot is: result.1 - result.0 + 1

Time complexity is O(n), space complexity is O(1).

*/

func partitionDutchFlag<T: Comparable>(_ a: inout [T], low: Int, high: Int, pivotIndex: Int) -> (Int, Int) {

let pivot = a[pivotIndex]

var smaller = low

var equal = low

var larger = high

// This loop partitions the array into four (possibly empty) regions:

// [low ...smaller-1] contains all values < pivot,

// [smaller... equal-1] contains all values == pivot,

// [equal ... larger] contains all values > pivot,

// [larger ... high] are values we haven't looked at yet.

while equal <= larger {

if a[equal] < pivot {

swap(&a, smaller, equal)

smaller += 1

equal += 1

} else if a[equal] == pivot {

equal += 1

} else {

swap(&a, equal, larger)

larger -= 1

}

}

return (smaller, larger)

/*

Uses Dutch national flag partitioning and a random pivot index.

*/

func quicksortDutchFlag<T: Comparable>(_ a: inout [T], low: Int, high: Int) {

if low < high {

let pivotIndex = random(min: low, max: high)

let (p, q) = partitionDutchFlag(&a, low: low, high: high, pivotIndex: pivotIndex)

quicksortDutchFlag(&a, low: low, high: p - 1)

quicksortDutchFlag(&a, low: q + 1, high: high)

}