정렬(sort) 관련

insertion sort (삽입정렬)

- 주로 top N을 구할때 만들어 두고 사용한다. 32개 이하의 갯수일때는 제일 빠르다

// top10을 뽑으려면 12개 정도 여유있게
// 들어간 갯수를 관리하기 위한 변수
int trr[12] = { 0 }, an = 0;
int i = 0, j = 0;
 
// 들어간 갯수 뒤에서부터 앞으로 체크
for (i = 0; i < 10; ++i) {
    for (j = an - 1; j >= 0; --j) {
        // 현재 위치와 나를 비교해서 내가 더 좋으면
        // 뒷자리로 하나 보내고, 아니면 break;
        // 내가 들어갈 자리는 j+1자리 (j는 나보다 좋으니까)
        if (trr[j] > arr[i])
            trr[j + 1] = trr[j];
        else break;
    }
    // j+1 자리에 나를 넣어준다.
    trr[j + 1] = arr[i];
    an++;
}

 

merge sort

- 가장 일반적으로 쓰인다. 무조건 외워야 한다.

 
 
// arr원배열, trr새배열
int arr[10], trr[10];
 
void mergesort(int s, int e)
{
    // 1. base condition
    // [1,1] 처럼 하나남으면 리턴
    if (s >= e)    return;
 
    // 2. devide
    // 반씩 나눠서 재귀
    int m = (s + e) / 2;
    mergesort(s, m);
    mergesort(m + 1, e);
 
    // 3. merge
    // a는 s에서 m까지니 다 돌면 m+1이 되어있고
    // b는 m+1에서 e까지니 다 돌면 e+1이 된다.
    // 임시 배열에 넣을 t 셋팅
    int a = s;
    int alast = m + 1;
    int b = m + 1;
    int blast = e + 1;
    int t = 0;
 
    while (1)
    {
        // a도 끝까지, b도 끝까지 가면 끝
        if (a == alast && b == blast)    break;
 
        // a가 끝나면 b를 끝까지 담고
        if (a == alast)    trr[t++] = arr[b++];
        // b가 끝나면 a를 끝까지 담고
        else if (b == blast)    trr[t++] = arr[a++];
        // a가 크면 a를 담고
        else if (arr[a] > arr[b])    trr[t++] = arr[a++];
        // b가 크면 b를 담고
        else trr[t++] = arr[b++];
    }
 
    // 4. copy
    // 임시배열에 있는걸 옮겨 담는다
    for (int i = 0; i < t; ++i)    {
        arr[i + s] = trr[i];
    }
}

 

mergesort struct일 경우 조건문을 아래처럼 처리한다.

while (1)
{
    // struct일 경우에는 비교 조건문을 아래처럼
    if (a == alast) trr[t++] = arr[b++];
    else if (b == blast) trr[t++] = arr[a++];
    else if (arr[a].id < arr[b].id) trr[t++] = arr[a++];
    else if (arr[a].id == arr[b].id) {
        // 반드시 양쪽 다 체크할 수 있는 조건문이 있어야 한다.
        if (arr[a].time < arr[b].time)    trr[t++] = arr[a++];
        else trr[t++] = arr[b++];
    }
    else trr[t++] = arr[b++];
}