Swift) 분할 정복 :: 퀵 정렬(Quick Sort) 구현 해보기

 

 

안녕하세요!!!! 소들입니다 :)

이번 포스팅에선 퀵 정렬에 대해 알아보고, Swift로 구현해보려고 합니다!!! 🌝

흠...... 전에 Swift 언어에서 꽃은 옵셔널이다!! 라고 말한 적 있는데,

정렬 알고리즘의 꽃은 퀵 정렬이라고 해요 :) 🌸

 

이전에 배웠던 버블, 삽입, 선택 정렬과는 무언가 차이점이 있기 때문이겠죠?

한번 알아보러 가봅시다!!!

 모든 포스팅은 편의 말투로 합니다~!!

 

 

 

 

1. 분할 정복이란?

 

먼저, 퀵 정렬은 분할 정복이란 알고리즘 기법에 속함!!

분할 정복이 머나면

 

문제를 나눌 수 없을 때까지 나누어서 풀고,

나누어서 푼 문제를 다시 합병하여 답을 얻는 알고리즘

하양식 접근법으로, 일반적으로 재귀 함수로 구현

 

인데.. 우리가 공부할 퀵 정렬, 합병

정렬이 모두 이 분할 정복에 속함!

그럼 일단 잘 모르겠지만,

퀵 정렬은 배열을 나눌 수 없을 때까지 나누어서 정렬 후 합병 하는 것이고, 재귀함수로 짜겠군!

정도는 생각해볼 수 있을 것 같음!!! 이제 퀵정렬에 대해 알아보자!!

 

 

 

 

2. 퀵 정렬이 모야?

 

퀵 정렬의 방법에 대해 설명해 드리겠음

먼저, 퀵 정렬은 위에서 말했듯 재귀 함수를 이용함

 

ⓛ 기준점(pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right)으로 모음

② 위에서 모은 왼쪽(left), 오른쪽(right)의 갯수가 1개 이하가 될 때까지 위 작업을 재귀로 반복함

③ 재귀 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 을 리턴함

 

 

훔 위 글만 보고 이해를 하면 좋겠다만,

아직 이해를 못했을 분(혹은 미래의 나)를 위해 그림을 첨부 하겠음

자, 만약 [7, 10, 3, 9, 1] 이란 배열을 퀵 정렬로 정렬하고 싶다면,

 

 

 

 

가장 첫 번째 Index를 pivot(기준점)으로 잡음!!

그리고 pivot보다 작은 놈은 왼쪽(left)이란 배열에, 큰 놈은 오른쪽(right)란 배열로 모음

 

 

 

 

이렇게!!!

(0번 인덱스부터 비교하며 순서대로 모으기 때문에 당연히 정렬되지 않은 채 모임)

그럼 이제 나눠놓은 이 left, right를 재귀시키는 것임

언제까지? 나눠진 left, right의 갯수가 1개 이하가 될 때까지!

 

left에 대해서 다시 pivot을 잡고 작은놈은 왼쪽, 큰놈은 오른쪽,

right에 대해서도 다시 pivot을 잡고 작은놈은 왼쪽, 큰놈은 오른쪽

 

 

 

 

자, 이제 각각의 left의 모음이 갯수가 1개가 되었기 때문에,

재귀를 다시 실행하지만, 탈출 조건에 의해 더 이상 재귀하지 않을 것임!!

때문에, 이제 재귀가 불린 순서대로 left + pivot + right가 return 됨!

 

 

 

 

이렇게 리턴한다는 말임! (예제에서 right는 없으니 생략)

그럼 한 칸 위에서 실행된 재귀 함수(pivot이 7이었던 함수)는

이 결과값을 받아 자신도 left + pivot + right를 return 함

 

 

 

 

이렇게 차례대로 재귀함수가 return 되며,

맨 마지막엔 최종적으로 정렬된 배열이 return되는 것임 :)

 

 

 

 

3. 코드로 구현 해보기

 

자, 이제 Swift로 이 퀵 정렬을 구현해볼 것임 :)

코드만 던져두고 사라질 것인데 혹시 이해가 안 가거나 피드백할 부분이 있으면

언제든 댓글 주세요!!!

 

 

func quickSort(_ array: [Int]) -> [Int] {
    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)
}

 

 

Swift는 filter란 고차함수를 지원하기 때문에 위와 같이 간편하게 짤 수 있음! :)

음.. 근데 for 반복문을 이용해서 left, right를 나눌 경우 n번 걸리지만,

filter를 이용할 경우 2n번 걸림..! 근데 시간복잡도 상으로 둘은 같은 n이지만...

아주 조금의 낭비?도 허용하고 싶지 않다면 for문으로 돌리면 될듯~~

 

 

 

 

4. 퀵 정렬의 시간 복잡도

 

퀵 정렬의 시간 복잡도는 

 

O(n log n)

 

임!! 근데 만약 첫 번째 index인 pivot이 가장 크거나 가장 작으면,

모든 데이터를 비교해야 해서 이땐 O(n^2)이라고 함

 

근데 빅오표기법은 원래 최악의 시간을 표시하지 않나...

가끔보면 생각보다 되게 후한 것 같다... ;;;;;

어쨌거나 이전에 공부한 선택, 버블, 삽입보단 훨씬 빠른 정렬 알고리즘이다:)

 

 

 

 

 

 

 

 

.

.

.

 

분할 정복 중에서도 퀵 정렬 끝!

이해 안가는 부분이나 피드백은 언제나 댓글 주세요 :)