[ 알고리즘 ] Divide and Conquer : Quick Sort

1. Quick Sort

 

Quick Sort의 알고리즘을 한번 보겠다.

 

1. 배열에서 하나를 pivot으로 설정한다.

2. 배열의 가장 앞을 가르키는 i와 가장 뒤를 가르키는 j로 설정한다.

3. i와 j가 만날때까지 아래의 과정을 반복한다.

3-1. i가 가르키는 값과 pivot이 가르키는 값을 비교해서 i가 더 작다면 pivot보다 더 큰 숫자를 만날때까지 i를 증가시킨다.

3-2. j가 가르키는 값과 pivot이 가르키는 값을 비교해서 j가 더 크다면 pivot보다 더 작은 숫자를 만날때까지 j를 증가시킨다.

3-3. 둘다 적절한 값을 찾는다면 i가 가르키는 값과 j가 가르키는 값을 바꾼다. 

4. 반복문을 나왔다면 pivot값과 j가 가르키는 값을 교환한다.

5. 처음부터 j까지, j 다음부터 끝까지 각각 재귀적으로 정렬한다.

 

Quick Sort code

 

 

2. 성능

 

• Worst Case

Pivot이 max거나 min일 때 최악의 결과가 나온다.

이 때에는 하나하나 다 비교하는 것과 똑같아진다.

 

T(n)=T(n−1)+n=...=O(n^2)

 

• Best Case

Pivot이 가운데 있을 때 가장 이상적은 Quick Sort가 된다.

 

T(n)=2T(n/2)+n=...=O(nlogn)

 

• Average Case

Average Case 계산

평균을 계산해보면 O(nlogn) 정도가 나오게된다.

평균이 Best Case에 가까운 것을 보면 Worst Case의 확률이 적다고 볼 수 있다.