퀵 정렬 quicksort with swift

퀵 정렬은 pivot을 기준으로 큰 숫자와 작은 숫자를 나누어줍니다.

 

코드를 살펴봅시다.

 

pivot을 array의 중간인 array.count / 2로 잡아주고 

less는 pivot보다 작은 것

equal은 pivot이랑 같은 것

greater은 pivot보다 큰 것들로 나누어줍니다.

각 less, equal, greater은 스위프트의 고차함수filter를 사용해줍니다.

 

간단하게 나뉘는 흐름을 살펴봅니다.

array의 count가 1보다 작으면 return해주고

less, equal, greater을 분리하면 최종적으로 정렬된 배열을 얻을 수 있습니다.

 

단점은 피봇 값에 따라 편향되게 분할될 가능성도 있습니다.

예를들어 이미 정렬할 데이터가 정렬되어 있거나 역으로 정렬되어 있는경우 피봇이 한쪽으로 치우쳐 

N개의 원소를 피봇 기준으로 나누는 작업을 N번 실행하므로 O(n^2)의 시간복잡도를 가지기도 합니다.

 

기본적으로 퀵 소트의 시간 복잡도는 O(nlogn)이지만, 최악으로는 O(n^2)도 나옵니다.