Last active
August 29, 2015 14:27
-
-
Save Vaberer/0193ee0b72c3c8b9a1ac to your computer and use it in GitHub Desktop.
Implementing Quick Sort with array of Integers
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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