6.2 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort) 알고리즘은 재귀적인 방법으로 문제를 해결하는 정렬 알고리즘입니다.

퀵 정렬 알고리즘은 피벗 값을 선택하여 피벗 값보다 작은 값들은 왼쪽으로 보내고 큰 값들은 오른쪽으로 보낸 후에 이들 사이에 피벗을 위치시키는 원리를 이용합니다. 이후 피벗보다 작은 값들을 재귀 호출로 정렬하고 피벗보다 큰 값들도 재귀 호출로 정렬하는 방식입니다.

“퀵 정렬 알고리즘은 피벗 값을 선택하여 피벗 값보다 작은 값들은 왼쪽으로 보내고 큰 값들은 오른쪽으로 보낸 후에 이들 사이에 피벗을 위치시키는 원리를 이용합니다. 이후 피벗보다 작은 값들을 재귀 호출로 정렬하고 피벗보다 큰 값들도 재귀 호출로 정렬하는 방식입니다.”

그런데 퀵 정렬은 어떠한 요소를 피벗으로 선택하냐에 따라 성능에 차이가 납니다. 만약 전체 요소의 중간 순위의 요소를 선택하면 재귀 호출에서 반씩 나누어 정렬하여 좋은 성능을 발휘합니다. 하지만 가장 작은 값이나 가장 큰 값을 피벗으로 선택하면 최악의 성능을 발휘합니다.

여기에서는 맨 앞과 맨 뒤, 그리고 중간 위치의 요소를 비교해 세 값 중에 중간 값을 피벗으로 선택할게요.

퀵 정렬(base:컬렉션,n: 원소 개수, compare:비교 논리)

조건(n<=1)

종료

피벗을 선택한다.

피벗과 맨 앞의 요소를 교환한다.

    big:=0

    small:=n

반복(big<small)

반복(big:=big+1; big<n; big:=big+1)

조건(compare(base[0],base[big])<0)

루프 탈출

반복(small:small-1;small>0;small:small-1)

조건(compare(base[0],base[small])>0)

루프 탈출

조건(big<small)

교환(base [big], base [small])

교환(base [0], base [small])

퀵 정렬(base,small, compare)

퀵 정렬(base+big, n-big, compare)

퀵 정렬 알고리즘의 탈출 조건은 n이 1보다 작거나 같을 때입니다.