퀵정렬 알고리즘 두 번째 코드로 준비했습니다.
퀵정렬 알고리즘은 최선의 시간 복잡도 O(nlogn)을 가지며, 최악은 O(n^2)을 갖는 경우로,
재귀함수를 이용한 알고리즘의 표준이라 생각하면 됩니다.
그렇다면, 재귀함수를 이용한다고 하였기 때문에 먼저 재귀적 디자인을 해야합니다.
함수의 역할을 직접 말로 표현해야하며, 기저조건으로 수렴하는지를 체크해야합니다.
또한, 함수가 여러번 돌기 때문에, 원활하게 진행될 것이라 생각하고 구현해야합니다.
퀵정렬을 구현할 함수의 역할을 우선 말로 표현하자면 아래와 같습니다.
1. 기준이 될 Pivot을 정한다.
2. Pivot 이하의 값을 갖는 요소들을 왼쪽 배열에, Pivot 초과의 값을 갖는 요소들을 오른쪽 배열에 저장한다.
3. 각 배열은 1과 2 과정을 반복한다 (재귀적 활동)
4. 기저조건은 각 배열은 1과 2 과정을 반복하다보면 더이상 나눌 요소가 없을 경우가 생긴다.
그런 경우가 기저조건이다.
코드는 아래와 같습니다.
void getLeft(int arr[],int s,int e,int pivot,int left[]){
// arr 배열에서 s부터 e까지의 값들 중 pivot 이하의 값을 갖는 것을 left 배열에 넣는다.
// left 배열은 포인터, 즉 주소 값을 가리키기 때문에 quickSort내의 left 배열과 일대일 매칭된다.
int inx = 0;
for(int i=s;i<=e;i++){
if(arr[i] <= pivot){
left[inx++] = arr[i];
}
}
return inx;
}
void getRight(int arr[],int s,int e,int pivot,int right[]){
int inx = 0;
for(int i=s;i<=e;i++){
if(arr[i] > pivot){
right[inx++] = arr[i];
}
}
return inx;
}
// arr이라는 배열을 s에서부터 e까지 퀵정렬을 진행한다.
void quickSort(int arr[],int s,int e){
if(s >= e)
return;
int pivot = arr[s]; // 피벗을 처음 시작점이라고 가정한다. (피벗은 어디에 두어도 상관이없다.)
int left[N]; // N은 arr 배열의 길이로, 전역변수로 정의되어있다.
int right[N];
// left배열과 right배열을 설정해서 pivot과 비교하여 요소 값을 각가 넣어줄 것이며, 이 두 배열을 퀵정렬할 것이다.
int left_cnt = getLeft(arr,s+1,e,pivot,left);
int right_cnt = getRight(arr,s+1,e,pivot,right);
for(int i=0;i<left_cnt;i++){
arr[s+i] = left[i];
}
arr[s+left_cnt] = pivot;
for(int i=0;i<right_cnt;i++){
arr[(s+left_cnt+1)+i] = right[i];
}
quickSort(arr,s,s+left_cnt-1);
quickSort(arr,s+left_cnt+1,end);
}
왼쪽 배열과 오른쪽 배열을 나눌 getLeft()함수와 getRight()함수를 각각 만들어서 구현하고
index값을 반환하면서 left배열에 몇 개의 값이 들어갔고, right배열에 몇 개의 값이 들어갔는지 체크합니다.
반환된 인덱스는 quickSort에서 재귀적 호출을 위해 사용될 것이며, left배열과 right배열은 인자로 연결되어 call by value 형태로
각 배열에 값이 들어가게 됩니다.
따라서 이를 arr 배열에 다시 적용하여 추가하고 피벗을 중간 지점으로 재설정한 뒤, quickSort를 재귀적으로 호출합니다.
전체 코드는 아래와 같습니다.
#include <stdio.h>
#include <cstdio>
int N;
int getLeft(int arr[],int start,int end,int pivot,int left[]){
int inx = 0;
for(int i=start;i<=end;i++){
if(arr[i] <= pivot){
left[inx++] = arr[i];
}
}
return inx;
}
int getRight(int arr[],int start,int end,int pivot,int right[]){
int inx = 0;
for(int i=start;i<=end;i++){
if(arr[i] > pivot){
right[inx++] = arr[i];
}
}
return inx;
}
void quicksort(int arr[],int start,int end){
// 기저 조건 : 더이상 그룹핑할 요소가 없을 때
if(start >= end)
return;
// 피벗 정하기
int pivot = arr[start];
int left[100];
int right[100];
// 피벗보다 작거나 같은 값은 왼쪽 배열
// 피벗보다 큰 값은 오른쪽 배열
int left_cnt = getLeft(arr,start+1,end,pivot,left);
int right_cnt = getRight(arr,start+1,end,pivot,right);
// 2 3 4 5 6(pivot) 8 9 10 이라 하면
// s p e s를 p까지 옮기면서 값을 넣기
// start부터 start+left_cnt까지의 값을 넣는것
for(int i=0;i<left_cnt;i++){
arr[start+i] = left[i];
}
arr[start+left_cnt] = pivot; // 피벗은 중간 지점에 넣어주기
// start + left_cnt + 1 위치부터 end까지 값을 넣어준다.
for(int i=0;i<right_cnt;i++){
arr[(start+left_cnt+1)+i] = right[i];
}
// 요소 정리 완료 --> 각 그룹을 퀵소트 돌리기
quicksort(arr,start,start+left_cnt-1);
quicksort(arr,start+left_cnt+1,end);
}
int main(){
scanf("%d",&N);
int arr[100];
for(int i=0;i<N;i++){
scanf("%d",&arr[i]);
}
// arr 배열을 처음 요소부터 끝 요소 까지 퀵정렬을 진행한다.
quicksort(arr,0,N-1);
for(int i=0;i<N;i++){
printf("%d ",arr[i]);
}
}
감사합니다.
'Algorithm' 카테고리의 다른 글
| NN단 알고리즘 문제 (0) | 2019.01.09 |
|---|---|
| 합병정렬 알고리즘 (0) | 2018.12.18 |
| 퀵정렬알고리즘 (0) | 2018.12.16 |
| Danji_알고리즘_sort (0) | 2018.12.06 |
| toBin_알고리즘 (0) | 2018.12.05 |
