[알고리즘] 퀵 정렬 (Java)

퀵 정렬 정렬 알고리즘의 한 종류인 퀵 정렬입니다. 리스트 가운데서 하나의 값을 고릅니다.

이를 피벗(Pivot)이라고 하며 보통 제일 처음이나 마지막 값을 선택합니다. 피벗을 기준으로 왼쪽에는 작은 값을 오른쪽에는 큰 값이 오도록 교환합니다.

이렇게 나누어진 왼쪽 값들과 오른쪽 값들을 다시 정렬합니다. 정렬할 때 동일하게 다시 피벗을 정하고 피벗을 기준으로 양쪽을 나눕니다.

최종적으로 나누어진 값의 크기가 0이나 1이 될 때까지 반복합니다. 버블 정렬의 최악 시간 복잡도는 O(n^2)이지만 평균 시간 복잡도는 O(nlogn)입니다.

기준 피벗에서 오른쪽으로 높은 값을 찾고 왼쪽으로 낮은 값을 찾습니다. 4 1 9 2 6 8 3 5 7 피벗 -> High <-Low 높은 값 9의 인덱스보다 낮은 값 3의 인덱스가 높으므로 교체합니다. 4 1 3 2 6 8 9 5 7 피벗 -> High <-Low 다음을 보면 높은 값 6의 인덱스가 낮은 값 2의 인덱스 보다 높으므로 교체하지 않습니다...

원문링크 : [알고리즘] 퀵 정렬 (Java)