Skip to content

Instantly share code, notes, and snippets.

@Vaberer
Last active August 29, 2015 14:27
Show Gist options
  • Save Vaberer/0193ee0b72c3c8b9a1ac to your computer and use it in GitHub Desktop.
Save Vaberer/0193ee0b72c3c8b9a1ac to your computer and use it in GitHub Desktop.
Implementing Quick Sort with array of Integers
func quickSort(inout array: [Int], var leftIndex: Int = 0, var rightIndex: Int = -1) {
// O(n*log(n))
if rightIndex == -1 { //we can call quickSort without start and end index in the beginning so first time we will assign last index of the array to the variable
rightIndex = array.count - 1
}
var startLeftIndex = leftIndex
var startRightIndex = rightIndex
var pivot = array[leftIndex] //our pivot is the most left element
while leftIndex < rightIndex {
while array[rightIndex] >= pivot && leftIndex < rightIndex { //moving right if elements on the right are >= than the pivot
rightIndex--
}
if leftIndex != rightIndex {
array[leftIndex] = array[rightIndex] //switch elements bacause element on the left has to be less or equal than the pivot
leftIndex++
}
while array[leftIndex] <= pivot && leftIndex < rightIndex {
leftIndex++
}
if leftIndex != rightIndex {
array[rightIndex] = array[leftIndex]
rightIndex--
}
}
array[leftIndex] = pivot//put pivot to the position where left index finished
var pivotIndex = leftIndex
leftIndex = startLeftIndex
rightIndex = startRightIndex
if leftIndex < pivotIndex {
//recursive call
self.quickSort(&array, leftIndex: leftIndex, rightIndex: pivotIndex-1)
}
if rightIndex > pivotIndex {
//recursive call
self.quickSort(&array, leftIndex: pivotIndex + 1, rightIndex: rightIndex)
}
}
/* QUICK SORT TESTING START */
var testArray = [9,2,5,10,6,45,12]
var myArray = [Int]()
myArray = testArray
println("\(myArray) before sorting")
quickSort(&myArray)
println("\(myArray) after sorting")
if sorted(myArray) == myArray {
println("Quick Sort works")
} else {
println("QuickSort failed")
}
println("\n")
/* QUICK SORT TESTING END */
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment