버블 정렬

func bubbleSort(_ array : inout [Int]){
		for i in 0..<(array.count - 1){
				var isSwap = false
				for j in 0..<((array.count - i) - 1) {
						if array[j] > array[j + 1]{
								array.swapAt(j, (j + 1))
								isSwap = true
						}
				}
				if isSwap == false {return}
		}
}

시간 복잡도 : O(N^2)

선택 정렬

func selectionSort(_ array : inout [Int]){
		for i in 0..<(array.count - 1){
				var minIndex = i
				for j in (i + 1)..<array.count {
						if array[j] < array[minIndex]{
								minIndex = j
						}
				}
				array.swapAt(i , minIndex)
		}
}

시간 복잡도 : O(N^2)

삽입 정렬

func insertionSort(_ array : inout [Int]){
		for i in 1..<(array.count){
				for j in stride(from: i , to : 0 , by: -1){
						if array[j] > array[j - 1]{
								array.swapAt(j, (j - 1))
						} else {
								break
						}
				}
				if isSwap == false {return}
		}
}

시간 복잡도 : O(N^2)

퀵 정렬

func quickSort(_ array: [Int]) -> [Int] {
		// base case
		guard let first = array.first, array.count > 1 else {return array}
		
		let pivot = first
		let _left = array.filter {$0 < pivot}
		let _right = array.filter {$0 > pivot}
 
		return quickSort(_left) + [pivot] + quickSort(_right)		

}

시간 복잡도 : O(N log N)

병합 정렬

func mergeSort(_ array: [Int]) -> [Int] {
		if array.count <= 1 {return array}
		let center = array.count / 2
		let _left = Array(array[0..<center])
		let _right = Array(array[center..<array.count])

		func merge(_ _left: [Int], _ _right: [Int]) -> [Int]{
				var _left = _left
				var _right = _right
				var result = [Int]()
				
				while !_left.isEmpty && !_right.isEmpty {
						if _left[0] < right[0] {
								result.append(_left.removeFirst())
						} else {
								result.append(_right.removeFirst())
						}
				}
				
				if !_left.isEmpty {
						result.append(contentsOf: _left)
				}
				
				if !_right.isEmpty{
						result.append(contentsOf: _right)
				}
				
				return result
		}
		
		return merge(mergeSort(_left),mergeSort(_right))
}

시간 복잡도 : O(N log N)