6.2.2 퀵 정렬 알고리즘 구현

이번에는 퀵 정렬 알고리즘을 구현해 보기로 해요.

퀵 정렬(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)

 

참고로 2.1.2에서 공통으로 사용할 코드를 이용하세요.

퀵 정렬의 탈출 조건은 정렬할 원소 개수가 1보다 작거나 같을 때입니다.

피벗을 선택합시다. 여기에서는 맨 앞, 중간, 마지막 원소 중에 중간 값을 갖는 원소를 피벗으로 선택할 것입니다.

피벗을 선택하였으면 맨 앞의 원소와 피벗에 있는 요소를 교환하세요.

이제 피벗을 중심으로 큰 값은 왼쪽으로 작은 값들은 오른쪽으로 배치할 것입니다. 이를 위해 앞에서부터 피벗보다 큰 값을 찾고 뒤에서부터 피벗보다 작은 값을 찾는 과정을 반복할 것입니다. 만약 큰 값이 작은 값보다 앞에 있으면 둘을 교환하는 것을 반복할 거예요.

이제 피벗을 중심으로 작은 값들은 왼쪽에 큰 값은 오른쪽에 배치하였습니다. 작은 값들 중에 맨 뒤에 있는 요소와 피벗을 교환하세요.

재귀함수로 피벗보다 작은 값들이 있는 배열을 정렬합니다.

재귀함수로 피벗보다 큰 값들이 있는 배열을 정렬합니다.

테스트 코드도 2.1.3에서 작성한 코드에서 sequential_sort 부분을 quick_sort로 변경하세요.

다음은 실행 결과예요.

▷실행 결과

퀵 정렬의 결과를 보면 자료 개수가 MAX_DATA일 때 MAX_DATA/10일 때보다 130배 정도 느린 것을 알 수 있습니다. 앞에서 알고리즘 성능을 분석할 때 O(nlogn)과 비슷하죠. 이제까지 구현했던 순차, 거품, 선택, 삽입 정렬 알고리즘보다 수행 성능이 뛰어난 것을 알 수 있습니다.


테스트 코드를 포함한 실습 결과물은 언제나 휴일 프로그램 소스 사이트에 있습니다.