[Data Structure / Algorithms] Quick Sort

전성훈·2023년 11월 11일

Algorithms swift

Data Structure-Algorithm

목록 보기

24/35

주제: 대표적인 정렬 알고리즘

Quick Sort

퀵 정렬은 비교 기반 정렬 알고리즘입니다. Merge Sort와 마찬가지로 분할 정복 방법을 활용합니다.
퀵 정렬의 중요한 특징 중 하나는 피벗 지점을 선택하는 것이며, 피벗은 배열을 세 부분으로 나눕니다.

<피벗보다 작은 요소 | 피벗 | 피벗보다 큰 요소>

구현

Naive partitioning

피벗을 배열의 가운데 요소로 선정합니다.

public func quicksortNaive<T: Comparable>(_ a:[T]) -> [T] { 
	guard array.count >= 2 else { 
		return array
	}
	let pivot = array[a.count / 2]
	let less = array.filter { $0 < pivot}
	let equal = array.filter { $0 == pivot}
	let greater = array.filter { $0 > pivot}
	return quicksortNaive(less) + equal + quicksortNaive(greater)
}

위 구현은 배열을 세 개의 파티션으로 나눠서 재귀적으로 필터링합니다.
배열은 두 개 이상의 요소가 있어야하며, 그렇지 않으면 배열은 정렬된 것으로 간주됩니다.

장점

구현이 매우 단순하고 이해하기 쉽습니다.
동일한 요소의 상대적 순서가 유지됩니다.

단점

추가 배열을 사용하기 때문에 메모리 사용량이 많습니다.
필터링 과정에서 추가적인 시간이 소요됩니다.

Lomuto's partitioning

Lomuto의 파티셔닝 알고리즘은 항상 마지막 요소를 피벗으로 선택합니다.

private func partitionLomuto<T: Comparable>(_ a: inout[T], low: Int, high: Int) -> Int { 
	let pivot = a[high]
	
	var i = low
	for j in low..<high { 
		if a[j]<= pivot { 
			a.swapAt(i, j)
			i += 1 
		}
	}
	a.swapAt(i, high)
	return i 
}

public func quicksortLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) { 
	if low < high { 
		let pivot = partitionLomuto(&a, low: low, high: high) 
		quicksortLomuto(&a, low: low, high: pivot - 1)
		quicksortLomuto(&a, low: pivot + 1, high: high)
	}
}

위 구현은 항상 마지막 요소를 피벗으로 선택합니다. 변수 i는 피벗보다 작은 요소의 수를 나타내며, 요소가 피벗보다 작으면 인덱스 i의 요소와 교환하고 i를 증가시킵니다.
현재 요소가 피벗보다 작거나 같은지 확인하고 그렇다면 인덱스 i의 요소를 교환하고 i를 증가시킵니다.
루프가 끝나면, i의 요소를 피벗과 교환합니다. 피벗은 항상 피벗보다 작은 수와 피벗보다 큰 수 사이에 있습니다.
피벗의 인덱스를 반환합니다.

장점

이해하고 구현하기 쉬운 방식입니다.
파티셔닝 과정이 직관적이고 단순합니다.

단점

평균적으로 Hoare 방식보다 느립니다. 특히, 피벗 선택이 좋지 않을 경우 성능이 크게 저하됩니다.
동일한 요소의 상대적 순서가 바뀔 수 있습니다.

Hoare's partitioning

Hoare의 파티셔닝은 항상 첫 번째 요소를 pivot으로 선택합니다.

private func partitionHoare<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int { 
	let pivot = a[low]
	var i = low - 1
	var j = high + 1
	
	while true { 
		repeat { j -= 1 } while a[j] > pivot
		repeat { i += 1 } while a[i] < pivot
		
		if i < j { 
			a.swapAt(i, j)
		} else { 
			return j 
		}
	}
}

public func quicksortHoare<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
	if low < high { 
		let pivot = partitionHoare(&a, low: low, high: high)
		quicksortHoare(&a, low: low, high: pivot)
		quiclsortHoare(&a, low: pivot +1, high: high)
	}
}

첫 번째 요소를 pivot으로 선택합니다.
인덱스 i와 j를 정의하고, i 이전의 모든 인덱스는 pivot 보다 작거나 같습니다. j 이후의 모든 인덱스는 pivot보다 크거나 같습니다.
j를 감소시켜 pivot보다 크지 않은 요소를 찾을 때까지 반복합니다.
i를 증가시켜 pivot보다 작지 않은 요소를 찾을 때까지 반복합니다.
i와 j가 겹치지 않으면 요소를 교환합니다.

장점

Lomuto 방식보다 일반적으로 더 빠릅니다. 평균적으로 더 적은 비교와 교환을 수행합니다.
추가적인 메모리를 사용하지 않습니다.

단점

Lomuto 방식보다 구현이 복잡합니다.
동일한 요소의 상대적 순서가 바뀔 수 있습니다.

Effects of a bad pivot choice

bad pivot을 선택하게 되었을 때 거의 insertion sort와 같이 수행하게 되어서, 최악의 성능 $O(n^2)$ 을 보입니다.
이 문제를 해결하는 방법 중 하나는 median of three pivot 선택 전략을 사용하는 것입니다.
여기서는 배열의 첫 번째, 중간, 마지막 요소의 median을 찾아 pivot으로 사용하며, 이 선택 전략은 배열에서 가장 높거나 낮은 요소를 선택하지 않도록 방지합니다.

public func medianOfThree<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int { 
	let center = (low + high) / 2
	
	 if a[low] > a[center] {
	    a.swapAt(low, center)
	  }
	 if a[low] > a[high] {
	    a.swapAt(low, high)
	  }
	  if a[center] > a[high] {
	    a.swapAt(center, high)
	  }
	return center
}

Dutch national flag partitioning

Lomuto와 Hoare 알고리즘의 문제점 중 하나는 중복을 처리하는 데 효과적이지 않다는 것입니다.
Lomuto 알고리즘에서는 중복 항목이 작은 값 분활에 들어가며 서로 그룹화되지 않습니다.
Hoare 알고리즘에서는 중복 항목이 어디든 있을 수 있습니다.
중복 요소를 정리하는 해결책은 Dutch national flag을 활용하는 것입니다.

private func partitionDutchFlag<T: Comparable>(
    _ a: inout [T],
    low: Int,
    high: Int,
    pivotIndex: Int
) -> (Int, Int) {
    let pivot = a[pivotIndex]
    var smaller = low
    var equal = low
    var larger = high
    
    while equal <= larger {
        if a[equal] < pivot {
            a.swapAt(smaller, equal)
            smaller += 1
            equal += 1
        } else if a[equal] == pivot {
            equal += 1
        } else {
            a.swapAt(equal, larger)
            larger -= 1
        }
    }
    
    return (smaller, larger)
}

public func quicksortDutchFlag<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
    if low < high {
        let pivot = medianOfThree(&a, low: low, high: high)
        let (middelFirst, middelLast) = partitionDutchFlag(
            &a,
            low: low,
            high: high,
            pivotIndex: pivot
        )
        
        quicksortDutchFlag(&a, low: low, high: middelFirst - 1)
        quicksortDutchFlag(&a, low: middelLast + 1, high: high)
    }
}

var list3 = [4,123,14,2,33,12,1,42,11,67,8,84,9]

quicksortDutchFlag(&list3, low: 0, high: list3.count - 1)

print(list3)

[1, 2, 4, 8, 9, 11, 12, 14, 33, 42, 67, 84, 123]