Quicksort is one of the advanced algorithms. It features a time complexity of O(n log n) and applies a divide & conquer strategy. This combination results in advanced algorithmic performance. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.
The steps are:
mutating func quickSort() -> Array<Element> {
func qSort(start startIndex: Int, _ pivot: Int) {
if (startIndex < pivot) {
let iPivot = qPartition(start: startIndex, pivot)
qSort(start: startIndex, iPivot - 1)
qSort(start: iPivot + 1, pivot)
}
}
qSort(start: 0, self.endIndex - 1)
return self
}
mutating func qPartition(start startIndex: Int, _ pivot: Int) -> Int {
var wallIndex: Int = startIndex
//compare range with pivot
for currentIndex in wallIndex..<pivot {
if self[currentIndex] <= self[pivot] {
if wallIndex != currentIndex {
swap(&self[currentIndex], &self[wallIndex])
}
//advance wall
wallIndex += 1
}
}
//move pivot to final position
if wallIndex != pivot {
swap(&self[wallIndex], &self[pivot])
}
return wallIndex
}