퀵 정렬에는 재귀함수가 사용됩니다.
재귀함수란
함수가 자기 자신을 호출하는 프로그래밍 기법입니다. 재귀는 문제를 더 작은 문제로 나누어 해결하는 데 유용하며, 주로 분할 정복, 동적 프로그래밍 등 다양한 알고리즘에서 사용됩니다.
예시 A() { A();} // 이 예시에는 원리 중 하나가없습니다.
이제 재귀함수에서 중요한 요소들입니다.
기저 사례(Base Case): 재귀 호출을 멈추게 하는 조건입니다. 기저 사례가 없으면 함수는 무한히 호출되어 스택 오버플로우가 발생할 수 있습니다.
재귀 호출(Recursive Call): 함수가 자기 자신을 호출하는 부분입니다. 이 호출은 문제를 더 작은 하위 문제로 나누어 해결합니다.
#include <iostream>
using namespace std;
// 팩토리얼을 계산하는 재귀 함수
int factorial(int n) {
if (n == 0) { // 기저 사례
return 1;
}
return n * factorial(n - 1); // 재귀 호출
}
int main() {
int number = 5;
cout << number << "! = " << factorial(number) << endl; // 5! 계산
return 0;
}
글쓴이 풀이
해당 함수는 자연수 n의 곱
으로 n * n - 1*...1; 으로 n부터 1까지 전부 곱하는 함수입니다.
일단 처음조건은 해당안하므로 마지막 반환값을 보면
매개변수 * 재귀함수 (n-1)로 나뉘었습니다.
즉 5 * ( 4 * (... 이런식으로 되는겁니다.
왜 4 * ( 이렇게 될가요
재귀함수에도 0이안되니 4 * 재귀 (4-1)이런식으로 계속 값을 구하는겁니다
조건에 해당할때 까지 - 기저 사례가 여기서 나옵니다 조건에 해당해야 재귀함수가 끝날 수있습니다.
이제 0까지 줄어들었으면
조건에서 매개변수가 0인지 체크합니다.
값을 1리턴 해줍니다.
이제 맨끝 재귀가 끝났으니 앞에있던 함수들을 순서대로 도달하면 이런식이됩니다.
1* 재귀함수(1-1) ; 1*1 == 1
2 * 재귀함수(n-1) ; 2 * 1 == 2
3 * 재귀함수(n-1) ; 3 * 2 == 6
4 * 재귀함수(n-1); 4 * 6 == 24
5 * 재귀함수(n-1); 5 * 24 = 120
결국 factorial(5) 는 120의 값을 나타냅니다
이런 식으로 재귀함수는 기저사례 , 재귀 호출을 사용해서 사용합니다.
퀵 정렬은
분할 정복(divide and conquer) 알고리즘의 일종으로, 배열을 여러 부분으로 나누고, 각 부분을 재귀적으로 정렬하는 방식입니다. 주어진 배열을 기준값(pivot)을 기준으로 나누어 정렬합니다.
#include <iostream>
using namespace std;
// 파티션 함수
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 기준값 선택
int i = low - 1; // 작은 요소의 인덱스
for (int j = low; j < high; j++) {
if (arr[j] < pivot) { // 기준값보다 작은 요소 찾기
i++;
swap(arr[i], arr[j]); // 교환
}
}
swap(arr[i + 1], arr[high]); // 기준값을 올바른 위치로 이동
return i + 1; // 기준값의 최종 위치 반환
}
// 퀵 정렬 함수
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // 파티션 함수 호출
// 재귀 호출
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// 배열 출력 함수
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {10, 80, 30, 90, 40, 50, 70};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "정렬된 배열: ";
printArray(arr, n);
return 0;
}
- 기준값 선택: 배열에서 하나의 요소를 기준값(pivot)으로 선택합니다. 일반적으로 첫 번째 요소, 마지막 요소, 중간 요소 등을 선택할 수 있습니다.
- 분할: 기준값을 기준으로 배열을 두 부분으로 나눕니다.
기준값보다 작은 요소는 왼쪽 부분에, 큰 요소는 오른쪽 부분에 위치시킵니다. - 재귀 호출: 왼쪽 부분과 오른쪽 부분을 각각 퀵 정렬로 정렬합니다.
- 종료 조건: 배열의 크기가 1 이하인 경우, 이미 정렬된 상태로 간주합니다.
글쓴이의 해석
// 파티션 함수
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 기준값 선택
int i = low - 1; // 작은 요소의 인덱스
for (int j = low; j < high; j++) {
if (arr[j] < pivot) { // 기준값보다 작은 요소 찾기
i++;
swap(arr[i], arr[j]); // 교환
}
}
swap(arr[i + 1], arr[high]); // 기준값을 올바른 위치로 이동
return i + 1; // 기준값의 최종 위치 반환
}
기준 값을 정해주는 함수
low 부터 high 숫자중에서 중간 선택
int pivot = arr[high]; // 기준값 선택
먼저 인덱스에서 원하는 인덱스에 있는 값으로 기준을 잡습니다. 맨끝이니
70
i = low - 1; // 작은 요소의 인덱스
-1로 만들어주고
반복문은 최소값 과 최대값
조건은 arr[j] < pivot 즉 10 < 70 으로 기준보다 작으면
i++;
swap(arr[i], arr[j]); // i ==0 ; j == 0;
}
다음 반복
//i == 0; j == 1; 인상황
조건은 arr[j] < pivot // 80 < 70 성립안됨
//i == 0; j == 2;
조건은 arr[j] < pivot // 30 < 70 성립
i++;
swap(arr[i], arr[j]); // i ==1 ; j == 2; // 80 30 위치 변경
//i == 1 j == 3 ( 10 30 80 90 40 50 70)
조건은 arr[j] < pivot // 90 70 성립안됨.
//i == 1; j == 4;
조건은 arr[j] < pivot // 40 < 70 성립
i++;
swap(arr[i], arr[j]); // i ==2 ; j == 4; // 80 40 위치 변경\
//i == 2; j == 5; ( 10 30 40 90 80 50 70)
조건은 arr[j] < pivot // 50 < 70 성립
i++;
swap(arr[i], arr[j]); //i == 3 ; j == 5 // 90 50 위치변경
j== 6으로 반복문 벗어남
//i == 3;( 10 30 40 50 80 90 70)
swap(arr[i + 1], arr[high]); // 기준값을 올바른 위치로 이동
arr [3 + 1 ] , arr [ 6]; // arr[4] , arr[6] // 80 70 위치 변경
(10 30 40 50 70 90 80 )
return i + 1; //4
배열의 변경은 원래 배열의 메모리 주소를 직접 수정하는 것이기 때문에, 해당 배열의 값이 실제로 변경된 것입니다.
거의 정렬이 되긴했지만 70을 기준으로 미만과 초과를 정할 수 있는 함수입니다...
퀵 정렬 함수
if (low < high) {
int pi = partition(arr, low, high); // 파티션 함수 호출 // 4
여기서 기준 받아서
//(10 30 40 50 70 90 80 )
재귀 시작
quickSort(arr , 0 , 3);
quickSort(arr, 5, 6);
재귀를 두개로 나뉨 여기서 위의 함수 먼저 끝내고 아래함수 시작이라는점!! 기억
0 < 3 이니 다시 파티션 시작
50을 기준으로 하고
arr[j] < pivot 조건 확인하면 50보다 적음
i ++; i ++; i ++; 이고
i == j가 되니
스왑 은따로 되지않음. 리턴값 3
그러고 quickSort(arr , 0 , 3); 내부에서 줄여서 2Sort에 조건(arr, , 3, 0), (arr, 3, 3)으로 다음 재귀는 없음!
이제 남은 재귀
quickSort(arr, 5, 6);
90 80
arr[j] < pivot 조건 확인하면 80보다 많음
i == 4;
swap(arr[i + 1], arr[high]); // 5 6 // 90 80 위치 변경
return 4 + 1 ; //5
// 재귀 호출
quickSort(arr, 5, 4);
quickSort(arr, 6, 6); 으로 재귀 종료!
장점과 단점
장점:
평균적으로 O(n log n)의 시간 복잡도를 가집니다.
공간 복잡도가 O(log n)으로, 추가적인 메모리를 적게 사용합니다.
정렬이 제자리에서 이루어지므로 메모리 사용이 효율적입니다.
단점:
최악의 경우 O(n²)의 시간 복잡도를 가질 수 있습니다. (예: 이미 정렬된 배열에서 첫 번째 또는 마지막 요소를 기준으로 선택할 때)
불안정 정렬(unstable sort)입니다. (동일한 값의 상대적인 순서가 유지되지 않을 수 있습니다)
최적화
기준값을 선택할 때, 랜덤 선택이나 중앙값을 사용하는 등의 방법으로 최악의 경우를 피할 수 있습니다.
작은 배열에 대해서는 삽입 정렬과 같은 다른 정렬 알고리즘을 사용하는 것이 더 효율적일 수 있습니다.
요약하면
퀵 정렬은 대규모 데이터셋에서 매우 효율적인 정렬 알고리즘이지만, 작은 배열에서는 삽입 정렬이 더 나을 수 있습니다.
이러한 이유로 퀵 정렬과 삽입 정렬을 결합한 하이브리드 정렬 알고리즘이 자주 사용됩니다.