quicksort.swift

//
//  main.swift
//  QuickSort
//
//  Created by ChristianEnevoldsen on 17/08/15.
//  Copyright © 2015 Reversebox. All rights reserved.
//

import Foundation

func quickSort<T: Comparable>(inout A: [T]) {
  quickSort(&A, p: 0, r: A.count - 1)
}

func quickSort<T: Comparable>(inout A: [T], p: Int, r: Int) {
  if p < r {
    let q = partition(&A, p: p, r: r)
    quickSort(&A, p: p, r: q - 1)
    quickSort(&A, p: q + 1, r: r)
  }
}

func partition<T: Comparable>(inout A: [T], p: Int, r: Int) -> Int {
  let x = A[r]
  var i = p - 1
  for j in p...r - 1 {
    if A[j] <= x {
      i = i + 1
      swap(&A[i], &A[j])
    }
  }
  swap(&A[i + 1], &A[r])

  return i + 1
}

var A = ["a", "c", "b"]
quickSort(&A)
print(A) // a, b, c