퀵소트

Swift

import Foundation

extension Array where Element: Comparable {
  private mutating func partition(_ left: Int, _ right: Int) -> Int {
    var low = left
    var high = right + 1
    let pivot = self[left]
    print("partition(\(left), \(right))")
    
    repeat {
      repeat {
        low += 1
      } while low <= right && self[low] < pivot
      
      repeat {
        high -= 1
      } while high >= left && self[high] > pivot
      print("low: \(low), high: \(high)")
      
      if low < high {
        swapAt(low, high)
        print("swapAt(\(low), \(high))")
      }
    } while low < high
    
    swapAt(left, high)
    print("swapAt(\(left), \(high))")
    return high
  }
  
  private mutating func qsort(_ left: Int, _ right: Int) {
    print("qsort(\(left), \(right))")
    if left < right {
      let pivotIndex = partition(left, right)
      print("pivotIndex: \(pivotIndex)")
      qsort(left, pivotIndex - 1)
      qsort(pivotIndex + 1, right)
    }
  }
  
  mutating func qsort() {
    qsort(0, count - 1)
  }
}