[알고리즘] 퀵 정렬

퀵정렬 (Quick Sort)

• 재귀용법을 이용한 정렬 알고리즘

방법

1. pivot(기준)을 잡고 원소들을 pivot과 비교
2. pivot 보다 작으면 left, 크면 right
3. left, right에 대하여 재귀를 사용해서 반복
4. [left] + [pivot] + [right] 을 return

구현

Python

def quick_sort(data):
	if len(data) <= 1:
    	return data
        
    left, right = list(), list()
    
    pivot = data[0]
    
    for i in range(1, len(data):
    	if pivot > data[i]:
        	left.append(data[i])
        else:
            right.append(data[i])
    return quick_sort(left) + [pivot] + quick_sort(right)

Swift

func quickSort(_ data: [Int]) -> [Int] {
    
    if data.count <= 1 {
        return data
    }
    
    var left: [Int] = []
    var right: [Int] = []
    
    let pivot = data[0]
    
    for i in 1..<data.count {
        if pivot > data[i] {
            left.append(data[i])
        } else {
            right.append(data[i])
        }
    }
    return quickSort(left) + [pivot] + quickSort(right)
}