+) [JAVA] 퀵정렬 알고리즘 정리 - quick sort

퀵정렬

퀵정렬( Quick Sort )이란,

입력된 배열을 더 작은 하위 배열로 나누고 독립적으로 정렬한 다음 결합하여 정렬된 출력 배열을 형성하는 것이다.

기준점(피봇, pivot)을 기준으로 두 개의 비균등한 크기로 배열을 분할하고, 분할된 부분 리스트를 정렬한 뒤, 두 개의 정렬된 부분리스트를 합쳐서 정체가 정렬된 리스트가 되도록 한다.

 

정렬 단계를 나눠서 설명해보겠다.

1. 분할:

입력 배열을 2개의 부분배열로 분할하는데, 피봇을 중심으로 왼쪽에는 피봇보다 작은 요소들을, 오른쪽에는 피봇보다 큰 요소들을 배치.

 

2. 정복:

분할배열을 정렬할텐데, 분할배열의 크기가 충분히 작지 않다면 재귀의 방법으로 다시 분할,정복 과정을 적용.

 

3. 결합: 정렬된 분할 배열들을 하나의 배열로 합침.

 

재귀(순환호출)를 한 번씩 진행할때마다 피봇의 위치는 최종위치로 정해지게 되므로, 이 과정을 반복하다보면 언젠가 정렬이 완성된다.