Divide & Conquer , Rekursive 를 이용한 정렬 알고리즘입니다.
분할정복(Divide & Conquer)이란 상단에서 분할하고 중앙에서 정복하고 하단에서 조합(Combine)하는 형태입니다.
자세한 내용은 >> 분할정복 <<
java의 Arrays.sort(), python의 list.sort() 등이 퀵정렬을 기반으로 합니다.
퀵정렬을 이해하기 위해 정렬되지 않은 정수 배열을 보겠습니다.
[5,2,3,4,6,9,7,1,8]
Quick Sort는 병합정렬과 달리 pivot이라는 임의의 기준값을 사용합니다.
피벗값을 설정하는 방법은 여러가지이지만 pivot값을 임의로 6이라고 설정
하겠습니다.
[5,2,3,4,1] < 6 < [9,7,8]
pivot = 6일 떄 pivot을 기준으로 나누어져 있기 때문에 각각 정렬을 하면 됩니다.
[5,2,3,4,1] 의 pivot값=4
[2,3,1] < 4 < [5]
[1,2] < 3
[1] < 2
[1,2,3,4] 로 정렬이 됩니다.
우측 정렬
[9,7,8] pivot = 7
7 < [8,9]
[8,9] p=9
8 < 9
[7,8,9]
양쪽 배열을 합쳐주면
[1,2,3,4,5,6,7,8,9]
즉 퀵정렬은 임의의 pivot값을 기준으로 divide하고 정렬한후 합쳐줌으로써
정렬해나가는 방식입니다.
알고리즘 :
배열의 시작 인덱스를 left, 마지막 인덱스를 right라고 할 때,
pl은 left부터 시작하여 피벗보다 크거나 같은 값이 있을 때까지 오른쪽으로 이동한다.
(단, pl이 right보다 작거나 같을때까지만 이동)
pr은 마지막부터 시작하여 피벗보다 작거나 같은 값이 있을 때까지 왼쪽으로 이동한다.
(단, pr이 left보다 크거나 같을때까지만 이동)
pl과 pr 이 이동을 멈추면, pl<=pr 이면 arr[pl] 과 arr[pr] 을 서로 교환(swap)한다.
교환이 끝나면 pl은 오른쪽으로 하나 이동, pr은 왼쪽으로 하나 이동한다.
pl 과 pr이 교차하면,
시작 인덱스를 left, 끝 인덱스를 pr로 하는 그룹으로 쪼개어서 1,2,3번 과정을 반복한다.
(단, left < pr 조건을 만족해야 함)
마찬가지로, 시작 인덱스를 pl, 끝 인덱스를 right로 하는 그룹으로 쪼깨어서 1,2,3번 과정을 반복한다.
(단, pl < right 조건을 만족해야 함)
참고링크텍스트