[C언어 알고리즘] 3.3 퀵 정렬(Quick Sort) 알고리즘

[C언어 알고리즘] 3.3 퀵 정렬(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보다 작거나 같을 때입니다.

---

[C언어 알고리즘] 3.3.1 퀵 정렬 알고리즘 성능 분석

[C언어 알고리즘] 3.3.2 퀵 정렬 알고리즘 구현

[C언어 알고리즘] 3.3.3 퀵 정렬 알고리즘 소스 코드