[Algorithm] 퀵 정렬(Quick Sort)란? (feat. Swift)

안녕하세요 Foma 💻  입니다!

 

오늘은 드디어 정렬 알고리즘에서 말 그대로 매우 빠른 수행시간을 가진 퀵 정렬에 대해서 알아보려고 합니다!

 

바로 시작할게요~

---

퀵 정렬(Quick Sort)이란? 🧐

 

퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. - 위키 백과 -

 

(참고로 리처드 호어가 퀵 정렬을 개발했을 당시 나이는 26살이라고 하네요...)

 

합병 정렬과 같이 분할 정복 알고리즘에 속하고 평균적으로 매우 빠른 수행속도를 자랑합니다.

---

퀵 정렬 과정 🔨

 

퀵 정렬을 하기 위해선 피봇(Pivot)이 핵심이 되는데요.

 

여기서 피봇은 어떤 것일까요?

 

피봇은 바로 기준입니다.

 

피봇을 가장 첫 번째 인덱스를 선택할 수도 있고 가장 마지막 인덱스를 선택할 수도 있고 중간에 있는 인덱스를 선택할 수도 있습니다.

 

피봇을 어떤 것을 선택하냐에 따라서 수행 시간이 달라지는데요.

 

이번 시간에는 중간 지점을 피봇으로 잡는 퀵 정렬 방식으로 진행하겠습니다.

 

아래와 같은 배열이 있다고 가정하겠습니다.

 

 

10개의 원소가 있으므로 중간값은 5번째인 2가 되겠죠?

 

가장 왼쪽과 가장 오른쪽에 포인터를 달아줍니다.

 

왼쪽 포인터는 피봇의 값보다 더 크거나 같은 값이 나올 때까지 오른쪽으로 진행하고

 

오른쪽 포인터는 피봇의 값보다 더 작거나 같은 값이 나올 때까지 왼쪽으로 진행할거에요.

 

 

왼쪽 포인터를 오른쪽으로 옮기려는데 이미 피봇값보다 더 큰 값이 있죠?

 

이 때는 피봇과 포인터의 값을 서로 바꿔줍니다.

 

 

그 다음엔 오른쪽 포인터를 왼쪽으로 움직여주려는데 이미 피봇값보다 작아져있죠?

 

피봇값과 오른쪽 포인터 값을 바꿔줍니다.

 

 

이제 또 다시 왼쪽에 있는 포인터를 피봇값보다 더 크거나 같을 때까지 오른쪽으로 움직여 줍니다.

 

피봇 값이 6이므로 8에서 멈추겠죠? 8과 6을 스왑해줍니다.

 

 

오른쪽 포인터를 피봇 값보다 더 작을 때까지 왼쪽으로 움직여줍니다.

 

바로 옆인 5에서 멈추겠죠? 5와 8을 스왑해줍니다.

 

 

 

이런 식으로 진행해주면 왼쪽과 오른쪽이 겹치는 순간이 옵니다.

 

 

이 땐 겹치는 인덱스를 기준으로 나눠줍니다.

 

나눠진 원소들을 위와 같은 방식으로 진행해줍니다.

 

 

오른쪽의 빨간박스부터 진행해주면 아래와 같이 7,6,9로 나눠지고 9,10으로 나눠집니다.

 

또 9,10을 퀵 정렬 방식으로 진행하면 9와 10으로 나눠지고 1개씩 원소가 남았다면 합쳐줍니다. (이래서 분할정복 방식입니다.)

 

이번엔 왼쪽의 빨간 박스를 퀵정렬 방식으로 진행해주면 6,7 그리고 8이 남게될 것 입니다.

 

6과 7을 퀵정렬 방식으로 나눠주고 합쳐줍니다. 

 

그리고 이미 합쳐진 원소들을 모두 합쳐줍니다.

 

 

이번엔 작은 값들이었던 파란 박스를 진행하면

 

 

2,1,3과 4,5로 나눠지고

 

 

1,2와 3으로 나눠지고 4와 5가 합쳐지겠죠?

 

 

이젠 왼쪽에 모든 값을 합쳐줍니다.

 

 

 

마지막으로 전에 합쳐뒀던 오른쪽의 값들과 왼쪽 값들을 모두 합쳐줍니다.

 

이렇게 하면 오름차순으로 모든 원소가 정렬됩니다.

 

 

퀵 정렬 과정을 이미지로 보면 아래와 같습니다.

 

출처: 위키백과

---

시간 복잡도 ⏰

 

퀵 정렬은 어떤 것을 피봇으로 선택하는지에 따라서 시간복잡도가 달라집니다.

 

만약 1,2,3,4,5,6,7,8,9,10이 있고 가장 오른쪽의 10을 피봇으로 선택했다면 최악의 경우인 O(n²) 입니다.

 

하지만 평균적인 수행시간은 nlogn 입니다.

---

코드 구현 👨🏻‍💻

 

먼저 분할하는 방법을 코드로 구현하겠습니다.

 

먼저 피봇,왼쪽,오른쪽 인덱스 값을 정해줍니다.

 

그리고 현재 움직여야할 포인터가 왼쪽인지 오른쪽인지 알려줄 변수도 정해줍니다.

 

만약 원소가 1개만 남았다면 원소들을 그대로 반환해줍니다.

 

func divide(_ list:[Element]) -> [Element] {
        if list.count < 2 { return list }
        var newList:[Element] = list
        let pivotIndex:Int = newList.count/2-1
        var leftIndex:Int = 0
        var rightIndex:Int = newList.count-1
        var isLeft:Bool = true
        
	...

 

위에서 구현했던대로 왼쪽 포인터와 오른쪽 포인터랑 겹칠 때까지 포인터를 움직여줍니다.

 

움직여야할 포인터가 왼쪽이라면 피봇의 값과 비교해서 더 작다면 포인터를 +1 해주고 더 크다면 피봇값과 왼쪽 값을 바꿔줍니다.

 

오른쪽 포인터라면 피봇의 값과 비교해서 더 크다면 포인터를 +1 해주고 더 작다면 피봇값과 오른쪽 값을 바꿔줍니다.

 

그리고 마지막에 움직여야할 포인터를 toggle로 바꿔줍니다.

 

 while leftIndex < rightIndex {
            if isLeft {
                if newList[leftIndex] < newList[pivotIndex] {
                    leftIndex += 1
                }else {
                    newList.swapAt(pivotIndex, leftIndex)
                }
            }else {
                if newList[rightIndex] > newList[pivotIndex] {
                    rightIndex -= 1
                }else {
                    newList.swapAt(pivotIndex, rightIndex)
                }
            }
            isLeft.toggle()
        }

 

마지막으로 겹친 포인터를 기준으로 나눠준 뒤 재귀함수로 반복해줍니다.

 

  	let left:[Element] = Array(newList[0...leftIndex])
  	let right:[Element] = Array(newList[leftIndex+1..<newList.count])
  	return merge(divide(left),divide(right))
  }

 

원소가 1개가 남을 때지 모두 분할했다면 왼쪽과 오른쪽을 합쳐줍니다.

 

func merge(_ left:[Element],_ right:[Element]) -> [Element] {
        return left + right
    }

---

Source Code