[정렬 알고리즘] - 퀵 정렬 O(NlogN | N²)

퀵정렬

기준값(pivot)을 선정하여 해당 값보다 작은 데이터와 큰 데이터로 분류하는것을 반복하여 정렬한다.

기준 값이 어떻게 선정되는지에 따라 시간복잡도에 많은 영향을 미친다.

• 평균 시간복잡도 : O(NlogN)
  (ex: 병합정렬)
• 최악 시간복잡도: O(n²)
  (ex: 버블, 선택, 삽입 정렬)

 

핵심이론

pivot을 중심으로 데이터를 2개의 집합으로 나누며 정렬을 반복

 

 

퀵정렬 과정

ⓐ 데이터를 분할하는 pivot(기준데이터)을 설정

 

ⓑ pivot을 기준으로 아래의 과정을 거쳐 데이터를 2개의 집합으로 분리한다.

1. (start < pivot) start의 데이터 보다 pivot의 데이터가 더 클 경우
   → start 포인터 우측 1칸 이동
   
   
2. (end > pivot)  end의 데이터가 pivot의 데이터 보다 클 경우
   → end 포인터 좌측 1칸 이동
   
   
3. (start > pivot && end < pivot) start데이터가 pivot보다 크고 end데이터가 pivot보다 작은경우
   1) start, end 서로 swap
   2) start 포인터 우측 1칸 이동 
   3) end 포인터 좌측 1칸 이동
   
   
4. start와 end가 만날 때 까지 1 ~ 3을 반복한다.
   
   
5. start와 end가 만났을 때 만난 지점(meet)에서 가리키는 데이터와 pivot 데이터를 비교
   1) meet < pivot → meet [삽입] : meet 우측에 pivot을 삽입한다.
   2) meet < pivot → [삽입] meet : meet 좌측에 pivot을 삽입한다.
   • 이때 pivot(미포함)을 기준으로 좌,우측으로 분리된다.
   • 좌측 분리 집합 : pivot보다 작음
   • 우측 분리 집합 : pivot보다 큼

 

ⓒ 각각의 분리 집합에서 다시 pivot 선정

 

ⓓ 분리 집합이 1개가 될 때까지 ⓐ ~ ⓒ를 반복한다

 

 

 

N² 시간복잡도 이유

1번째 Loop에서 ⓐ - 1이 계속 실패한다면 Data에 N번 access하게된다. (N-1번 이지만 상수는 무시하므로 N)

2번째 Loop에서도 똑같이 계속 실패한다면 N - 2 이므로 N
N번째 Loop에서도 N - N 이므로 N이다. N-1부터 N-N까지 N번 반복했으므로 N * N 즉 N²의 시간복잡도가 나온다.
ex) N이 8일때 N-1 / N-2 / N-3 / N-4 / N-5 / N-6 / N-7 / N-8 = 8N - 39
즉 '8번 Access' * '8회' =  =  8 * 8