[알고리즘 C언어] 3.3.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)

먼저 두 개의 값을 교환하는 매크로 함수를 작성합니다.

여기에서는 정렬하는 과정을 출력하는 부분이 있습니다. 이를 위해 정렬을 수행하는 배열의 시작 주소와 원소 개수를 기억하는 전역 변수를 선언하세요. 만약 정렬 과정을 출력할 필요가 없다면 주석 처리하세요.

이 책에서는 정수 형식 배열을 정렬하는 함수를 만들기로 할게요. 원소 형식에 관계없이 정렬하는 방법은 디딤돌 정렬 알고리즘 (C언어)를 참고하세요.

정렬해 나가는 과정을 출력하기 위한 목적으로 배열 주소와 원소 개수를 전역 변수에 설정합니다. 만약 테스트 과정을 출력할 필요가 없다면 주석 처리하세요.

피벗 위치를 기억하는 변수와 피벗보다 큰 값과 작은 값의 위치를 찾기 위한 변수를 선언하세요.

재귀 함수의 탈출 조건은 원소 개수가 1보다 작거나 같을 때입니다.

피벗보다 큰 값은 앞에서 부터 뒤로 이동하면서 찾을 것입니다. 그리고 피벗보다 작은 값은 뒤에서부터 앞으로 이동하면서 찾을 것입니다. 반복문 내부에서 이전에 찾은 위치 다음부터 진행하므로 초기값을 0과 n으로 설정합니다.

이전에 찾은 위치를 변경한 후에 뒤로 이동하면서 피벗보다 큰 값을 만날 때까지 left를 이동합니다.

이전에 찾은 위치를 변경한 후에 앞으로 이동하면서 피벗보다 작은 값을 만날 때까지 left를 이동합니다.

만약 left가 right보다 작다면 피벗과 비교하였을 때 작은 값이 큰 값보다 뒤에 있으니 교환합니다.

정렬 과정을 보여주기 위해 출력하는 것입니다. 만약 정렬 과정을 보여줄 필요가 없다면 주석 처리하세요.

left가 right보다 작지 않다면 피벗을 중심으로 작은 값들과 큰 값들을 분리하는 것이 끝났습니다. 따라서 반복문을 탈출합니다.

이제 피벗을 작은 값들과 큰 값들 사이로 보냅니다.

정렬 과정을 보여주기 위해 출력하는 것입니다. 만약 정렬 과정을 보여줄 필요가 없다면 주석 처리하세요.

피벗보다 작은 값들이 있는 앞쪽을 재귀 호출로 정렬합니다.

피벗보다 큰 값들이 있는 뒤쪽을 재귀 호출로 정렬합니다.

출력 과정을 표시하기 위해 제공하는 합수입니다. 먼저 재귀 과정에서 자신의 위치 앞쪽을 공백을 출력하기 위한 함수를 작성하세요.

테스트 목적으로 배열의 내용을 출력하는 함수입니다.

인덱스 0에서 마지막 요소까지 값을 출력합니다.

전체 요소 값을 출력한 후에 개행 문자를 출력합니다.

퀵 정렬 알고리즘
퀵 정렬 알고리즘

학습에 도움이 되시면 ebook을 구입(판매가 3000원, ebook)하여 소장하시면 감사하겠습니다.