java로 QuickSort 구현하기.

QuickSort는 분할정복법으로 정렬하는 알고리즘 중 한 방법이다.

 

QuickSort의 시간복잡도

[최악의 경우]

[평균의 경우]

 

QuickSort 과정

 

1.정렬할 원소 중 하나를 골라 이를 pivot으로 지정한다.

(나는 배열에 원소들을 저장 후 가장 마지막 인덱스의 값을 pivot으로 지정해주었다.)

2.pivot을 기준으로 pivot이전엔 pivot보다 작은 값들이, pivot이후에는 pivot보다 큰 값들이 오도록 분할한다.

3.pivot을 기준으로 분할된 두 부분을 재귀적으로(Recursive) 위 과정을 반복한다.

 

QuickSort 과정

 

다음은 java소스와 결과이다.

quicksort java

결과