▪ 문제 요약
k번째 큰 원소를 찾기
▪ 문제 풀이
1. 크기가 5인 배열으로 나눈다
2. *원소 5개중 중간값을 찾는다.
3. 그 중간값들 끼리 sorting을 한다.
4. 중간값들의 중간값을 pivot으로 설정한다.
5. pivot을 기준으로 pivot앞은 pivot보다 큰 원소, pivot뒤는 pivot보다 작은 원소가 되도록 정렬한다.
6. pivot의 index가
6-1. k와 같으면 pivot을 retrun
6-2. k보다 작으면 배열의 맨 앞~pivot바로 앞 까지 중간값의 중간값 다시 구해서 4번부터 다시
6-3. k보다 크면 pivot바로 뒤 ~ 배열의 맨 끝 까지 중간값의 중간값 다시 구해서 4번부터 다시
* 원소가 5개인 이유 : 5개 중에 중간값을 6번만에 찾을 수 있어서(더 좋은 효율을 내는 수도 있지만 가장 쉽다.)
* 5개중 중간값 구하는법
① 랜덤으로 2쌍을 지어서 비교한다.(1쌍당 1번 : 비교 (2))
② 2쌍 중 이긴 것 끼리 비교한다.(3)
③ ②에서 이긴 것은 적어도 2등이므로 중간인 3보다 크기 때문에 비교에서 제외한다.
④ 제외된 것에게 ①에서 진 것과, 비교하지 않은 나머지 하나를 비교한다(4)
⑤ 그 둘 중에 이긴 것과 ②에서 진 것과 비교한다.(5)
⑥ 둘 중 큰 것은 마찬가지의 이유로 비교대상에서 제외한다.
⑦ 제외된 것에게 진 것과 ②에서 진 것을 비교한다.(6)
⑧ 둘 중 큰 값이 mid 값!
▪ 소스코드
#include <stdio.h>
#include <stdlib.h>
#define SWAP(x, y, t) t=x, x=y, y=t
int find_MM(int *ary, int low, int high);
int QSMM(int *ary, int low, int high, int k);
int part(int *ary, int low, int high, int pivotpoint);
int execute = 0;
int fir;
int main() {
FILE *f;
char filename[30];
int *ary, pivot;
//scanf("%s", filename);
f = fopen(filename, "r");
int size, k, i;
scanf("%d %d", &size, &k);
ary = (int *)malloc(sizeof(int) * size);
for(i = 0; i < size; i++){
scanf("%d", &ary[i]);
}
pivot = QSMM(ary, 0, size-1, k);
printf("%d\n", pivot);
printf("%d\n", fir);
}
int find_MM(int *ary, int low, int high){
int i, j, *mid, mid_count;
int n;
n = high - low;
mid = (int *)malloc(sizeof(int) * ((n/5)+1));
i = low; j = 0;
while(1){//배열을 5씩 나눠서 중간값 찾기
if(i+4 > high)
break;
int group1[2], group2[2]; // 0이긴것 1진것
int **WinGroupP; //이겼던 그룹을 가리키는 포인터 (3개보다 큰 것은 제거, 비교대상 추가를 위해)
WinGroupP = (int **)malloc(sizeof(int *));
*WinGroupP = (int *)malloc(sizeof(int) * 2);
// 첫번째 쌍 비교 (1)
if(ary[i] > ary[i+1]) { group1[0] = i; group1[1] = i+1; }
else { group1[0] = i+1; group1[1] = i; }
// 두번째 쌍 비교 (2)
if(ary[i+2] > ary[i+3]) { group2[0] = i+2; group2[1] = i+3; }
else { group2[0] = i+3; group2[1] = i+2; }
// 이긴 것들 끼리 비교 (3)
if(ary[group1[0]] > ary[group2[0]]) *WinGroupP = group1;
else *WinGroupP = group2;
// (이긴 그룹의 이긴것은 자기가 이긴것, 이긴 것은 진그룹의 진 것, 진그룹의 이긴 것보다 큼. 밑에3개있으므로 mid X)
// 이긴그룹의 이긴것이 제외되었고, 이긴그룹의 진 것과 비교하지 않은 것을 비교 (4)
// 이긴group[0]에 이긴그룹의 진 것과, 비교하지 않았던 것 중에 큰 것이 들어가고 [1]엔 작은것이 들어감.
if(ary[(*WinGroupP)[1]] > ary[i+4])
{ (*WinGroupP)[0] = (*WinGroupP)[1]; (*WinGroupP)[1] = i+4; }
else
{ (*WinGroupP)[0] = i+4; }
// 또 두 쌍의 winner중에 큰 것을 비교대상에서 제외함(5)
if(ary[group1[0]] > ary[group2[0]]) group1[0] = group1[1];
else group2[0] = group2[1];
// 이겼던 그룹의 진 것과 진 그룹의 이긴 것을 비교함(6)
// 둘 중 큰 것이 mid값 (자기가 이긴것이 두개) or (자기가 이긴 것과 자기가 이긴 것이 이긴 것)
if(ary[group1[0]] > ary[group2[0]]) mid[j] = group1[0];
else mid[j] = group2[0];
i += 5;
j++;
}
int id = high-i;
switch (id) { // 5로 나누어 떨어지지 않는 인덱스 처리
case 4:
case 3:
mid[j] = ary[i] > ary[i+1]? i : i+1;
j++;
break;
case 2:
case 1:
mid[j] = i;
j++;
break;
default:
break;
}
mid_count = j;
int min, temp;
for(i = 0; i < mid_count-1; i++){
min = i;
for(j = i+1; j < mid_count; j++){
if(ary[mid[j]] < ary[mid[min]])
min = j;
}
SWAP(mid[i], mid[min], temp);
}
if (!execute){
fir = ary[mid[mid_count/2]];
execute = 1;
}
int index = mid[mid_count/2];
free(mid);
return index; // index
}
int QSMM(int *ary, int low, int high, int k){
int pivotpoint;
if(low >= high) return ary[low];
else{
pivotpoint = find_MM(ary, low, high);
pivotpoint = part(ary, low, high, pivotpoint);
if(pivotpoint+1 == k) return ary[pivotpoint];
else if(k < pivotpoint+1)
return QSMM(ary, low, pivotpoint-1, k);
else
return QSMM(ary, pivotpoint+1, high, k);
}
}
int part(int *ary, int low, int high, int pivotpoint){
int temp, i, j, pivot = ary[pivotpoint];
SWAP(ary[low], ary[pivotpoint], temp);
i = low+1;
j = high;
while(i<=j){
while(ary[i] > pivot && i<=j) i++;
while (ary[j] < pivot && i<=j) j--;
if(i<=j){
SWAP(ary[i], ary[j], temp);
i++; j--;
}
}
SWAP(ary[low], ary[j], temp);
return j;
}
댓글 없음:
댓글 쓰기