3.3.2 퀵 정렬 알고리즘 구현

2 장에서 만들었던 정렬 알고리즘과 같은 방법으로 시뮬레이션 코드를 작성합니다. 여기에서는 퀵 정렬 알고리즘만 구현할게요. 참고로 퀵 정렬 알고리즘을 내부 알고리즘을 별도의 함수로 구현하지 않고 직접 구현할게요. 정렬 알고리즘은 수행 속도가 중요한 이슈이므로 복잡하더라도 하나의 함수로 구현할게요.

 

먼저 교환에 사용할 임시 변수와 피벗의 위치와 피벗보다 큰 값과 작은 값의 위치를 기억하기 위한 변수를 선언합시다.

 

만약 원소의 개수가 1보다 작거나 같으면 함수를 종료합니다. 이 부분이 재귀 함수의 탈출 조건입니다.

 

피벗을 선택합니다. 여기에서는 맨 앞의 원소와 중간에 있는 원소, 맨 뒤에 있는 원소 중에 중간 값을 피벗으로 선택할게요. 먼저 맨 앞의 원소와 맨 뒤의 원소를 비교합시다.

 

만약 맨 앞의 원소가 크면 중간에 있는 원소와 다시 비교합니다.

 

이 때도 맨 앞의 원소가 크면 일단 제일 큰 값은 맨 앞에 있는 원소입니다. 이 때는 중간에 있는 원소와 맨 뒤에 있는 원소를 비교해야 중간 값을 알 수 있습니다. 이 둘을 비교하여 큰 값이 중간 값입니다.

 

만약 n-1번째 원소가 0번째 원소보다 크거나 같을 때의 피벗을 찾아봅시다.

 

중간에 있는 원소와 맨 뒤의 원소를 비교하여 중간에 있는 원소가 더 크면 맨 뒤의 원소가 중간 값입니다.

 

그렇지 않다면 맨 뒤에 있는 원소가 제일 큰 값입니다.

 

이 때는 다시 중간에 있는 원소와 맨 앞의 원소를 비교합니다. 이 둘 중에 큰 값이 중간 값입니다.

 

이제 피벗과 맨 앞의 요소를 교환합니다.

 

앞쪽부터 피벗보다 큰 값이 있는지 확인할 것입니다. 그리고 뒤쪽부터 작은 값이 있는지 확인할 것입니다. big을 0으로 초기화하고 small을 n으로 초기화하는 이유는 이전에 찾은 위치 다음으로 이동한 후에 찾는 작업을 할 것이기 때문입니다.

 

피벗보다 큰 값을 발견한 위치가 작은 값을 발견한 위치보다 앞이면 아직 피벗을 기준으로 작은 값들과 큰 값들을 배치하는 작업을 계속 해야 합니다.

 

먼저 피벗보다 큰 값을 찾습니다. 이전에 위치 뒤로 이동한 후에 마지막 요소까지 순차적으로 이동하면서 찾습니다.

 

만약 피벗보다 big위치의 원소가 더 크면 루프를 탈출합니다.

 

피벗보다 작은 값을 찾습니다. 이전에 위치 앞으로 이동한 후에 맨 앞까지 순차적으로 이동하면서 찾습니다. 그리고 피벗보다 small 위치의 원소가 더 작으면 루프를 탈출합니다.

 

 

만약 big 위치가 small 위치보다 앞이면 두 원소를 교환합니다.

 

이제 피벗과 small위치의 원소를 교환합니다. 이를 수행하면 피벗보다 작은 값들은 왼쪽에 존재하고 큰 값들은 오른쪽에 존재하고 피벗은 정렬을 완료한 상태에 있어야 할 위치에 존재합니다.

피벗보다 앞쪽을 재귀함수로 정렬합니다. 그리고 뒤쪽도 재귀함수로 정렬합니다.

 

재귀 함수의 깊이가 깊어지면 스택 메모리가 부족할 수 있습니다. 필요하면 프로젝트 속성 창을 열어 스택 크기를 설정하세요.

[그림 3.5] 프로젝트 스택 크기 설정

[그림 3.5] 프로젝트 스택 크기 설정

 

테스트를 해 보면 자료 개수가 10배 늘었을 때 20배 정도의 속도 차이가 나는 것을 알 수 있습니다.  하지만 피벗을 선택하여 맨 앞의 원소와 교환하는 부분을 주석 처리하고 정렬 상태의 배열이나 역순으로 정렬 상태의 배열을 정렬 요청하면 최악의 속도가 나오는 것을 확인할 수 있습니다.

[그림 3.6] 퀵정렬의 수행 속도 비교 화면

[그림 3.6] 퀵정렬의 수행 속도 비교 화면