quicksort (inplace, swift3)

quickSort.swift

/*
46319725 를 정렬해본다.

46319725 : pivot = 4
>      <

46319725
>     < -> 교환! (교환후에는 무조건 1칸씩 전진한다)

26319745
 >   <  -> 교환

21369745
  <>    -> 두 포인터가 교차했으므로 종료. 이 때의 파티션 위치는 2

array[0...2]
213 : pivot=2
213
><  : 교환
123 
<>  : 끝 파티션 위치는 0

arrary[0...0]
1   : left == right 이므로 종료

array[1...2]
23
><
23
X  --> 교환 없이 종료. 2, 3은 각각 1개짜리 원소이므로 종료.


array[3...7]
69745 : pivot = 6
>   < : 교환
59746
 > <  : 교환
54796
 <>   : 파티션 위치는 4 (3+1)

array[3...4]
54
45

array[5...7]
796 : pivot = 7
796
> < : 교환
697
<>  : 파티션 위치는 5
96
69  : 파티션 위치는 6

*/



func quickSort<T: Comparable> (_ arr: inout [T]) {
  func partition(of arr: inout [T], from start: Int, to end: Int) -> Int {
    let pivot = arr[start]
    var left = start - 1, right = end + 1
    while left < right {
      repeat { left += 1 } while arr[left] < pivot && left < end
      repeat { right -= 1 } while arr[right] > pivot && right > start
      if left < right {
        (arr[left], arr[right]) = (arr[right], arr[left])
      }
    }
    return right
  }
  func helper(_ a: inout [T], from start: Int, to end: Int) {
    guard start < end else { return }
    let p = partition(of:&a, from:start, to:end)
    helper(&a, from:start, to:p)
    helper(&a, from:p+1, to:end)
  }
  helper(&arr, from:0, to:arr.count-1)
}

var a = [4,6,3,1,9,7,2,5]
quickSort(&a)
print(a)