코딩테스트 - 패스트캠퍼스 챌린지 13일차

수강한 강의
Chapter 15 고급 정렬 알고리즘
- 퀵 정렬

학습 후기
퀵 정렬
기준(pivot)을 정해서 기준보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 사용하여 왼쪽과 오른쪽을 동일 함수를 사용하는 재귀 용법으로 반복하여 정렬된 데이터를 리턴하는 알고리즘

퀵 정렬

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

퀵 정렬 - 위키백과, 우리 모두의 백과사전

퀵 정렬은 매 단계에서 적어도 1개의 원소(pivot)가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다. 그리고 정렬하려는 데이터 중 같은 값을 가지는 데이터가 있는 경우 정렬 이후 순서가 초기 순서와 달라질 수 있어 불안정 정렬에 속한다.

Quick Sort는 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.
1. 리스트 가운데서 하나의 원소를 고른다. 이를 피벗(pivot)이라 한다.
- 강의에서는 제일 첫 번째 원소를 골라서 알고리즘을 구현하였다. 맨 처음 or 마지막 값
2. 피벗 앞에는 정렬하려는 데이터들 중에서 피벗보다 작은 값들이 모이고, 피벗 뒤에는 피벗보다 큰 값이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할(divide)이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1일 때까지 반복된다.
재귀 호출이 한번 진행될 때마다 최소 하나의 데이터는 최종적으로 위치가 정해 지므로, 이 알고리즘은 반드시 끝난다는 것을 보장한다.

Quick Sort 복잡도
 시간 복잡도: 최악 O(n^2), 평균 O(n log n)
 모든 데이터가 정렬되어 있는 경우 제일 첫 번째 데이터부터 피벗을 선택하면 나머지는 전부 오른쪽 리스트(피벗 뒤)에 담기게 된다. 이 과정을 재귀로 계속 반복하게 되면 n개의 데이터를 모두 한 번씩 피벗으로 잡고 나머지 데이터를 비교하는 상황이 되기 때문에 O(n^2)의 시간 복잡도를 가지게 된다.
 공간 복잡도: 최악 O(n), 평균 O(log n)
 공간 복잡도 역시 시간 복잡도와 마찬가지로 최악의 경우는 재귀 호출을 n번 호출하는 경우이며, 평균적으로는 피벗을 중심으로 left, right 리스트로 나누어 지기에 O(log n)의 공간 복잡도를 보인다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.