@@ -7,7 +7,7 @@ Quicksort is one of the most famous algorithms in history. It was invented way b
77Here's an implementation in Swift that should be easy to understand:
88
99``` swift
10- func quicksort <T : Comparable a -> [T] {
10+ func quicksort <T : Comparable _ a : [T]) -> [T] {
1111 guard a.count > 1 else { return a }
1212
1313 let pivot = a[a.count / 2 ]
@@ -131,7 +131,7 @@ In the first example of quicksort I showed you, partitioning was done by calling
131131Here's an implementation of Lomuto's partitioning scheme in Swift:
132132
133133``` swift
134- func partitionLomuto <T : Comparable inout a : [T], low Int , high Int ) -> Int {
134+ func partitionLomuto <T : Comparable _ a : inout [T], low Int , high Int ) -> Int {
135135 let pivot = a[high]
136136
137137 var i = low
@@ -250,7 +250,7 @@ And we return `i`, the index of the pivot element.
250250Let's use this partitioning scheme to build quicksort. Here's the code:
251251
252252``` swift
253- func quicksortLomuto <T : Comparable inout a : [T], low Int , high Int ) {
253+ func quicksortLomuto <T : Comparable _ a : inout [T], low Int , high Int ) {
254254 if low < high {
255255 let p = partitionLomuto (& a, low : low, high : high)
256256 quicksortLomuto (& a, low : low, high : p - 1 )
@@ -277,7 +277,7 @@ This partitioning scheme is by Hoare, the inventor of quicksort.
277277Here is the code:
278278
279279``` Swift
280- func partitionHoare <T : Comparable inout a : [T], low Int , high Int ) -> Int {
280+ func partitionHoare <T : Comparable _ a : inout [T], low Int , high Int ) -> Int {
281281 let pivot = a[low]
282282 var i = low - 1
283283 var j = high + 1
@@ -318,7 +318,7 @@ The pivot is placed somewhere inside one of the two partitions, but the algorith
318318Because of these differences, the implementation of Hoare's quicksort is slightly different:
319319
320320``` swift
321- func quicksortHoare <T : Comparable inout a : [T], low Int , high Int ) {
321+ func quicksortHoare <T : Comparable _ a : inout [T], low Int , high Int ) {
322322 if low < high {
323323 let p = partitionHoare (& a, low : low, high : high)
324324 quicksortHoare (& a, low : low, high : p)
@@ -380,7 +380,7 @@ Another common solution is to choose the pivot randomly. Sometimes this may resu
380380Here is how you can do quicksort with a randomly chosen pivot:
381381
382382``` swift
383- func quicksortRandom <T : Comparable inout a : [T], low Int , high Int ) {
383+ func quicksortRandom <T : Comparable _ a : inout [T], low Int , high Int ) {
384384 if low < high {
385385 let pivotIndex = random (min : low, max : high) // 1
386386
@@ -412,7 +412,7 @@ But as you've seen with the Lomuto partitioning scheme, if the pivot occurs more
412412The code for this scheme is:
413413
414414``` swift
415- func partitionDutchFlag <T : Comparable inout a : [T], low Int , high Int , pivotIndex Int ) -> (Int , Int ) {
415+ func partitionDutchFlag <T : Comparable _ a : inout [T], low Int , high Int , pivotIndex Int ) -> (Int , Int ) {
416416 let pivot = a[pivotIndex]
417417
418418 var smaller = low
@@ -461,7 +461,7 @@ Notice how the two `8`s are in the middle now. The return value from `partitionD
461461Here is how you would use it in quicksort:
462462
463463``` swift
464- func quicksortDutchFlag <T : Comparable inout a : [T], low Int , high Int ) {
464+ func quicksortDutchFlag <T : Comparable _ a : inout [T], low Int , high Int ) {
465465 if low < high {
466466 let pivotIndex = random (min : low, max : high)
467467 let (p, q) = partitionDutchFlag (& a, low : low, high : high, pivotIndex : pivotIndex)
0 commit comments