출처: 카연갤 다크시니




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
typedef struct Record {
    int key; //key
    int index; //마지막에 출력시 필요함.
}Record;
 
 
//left, right, mid는 모두 인덱스다.
void descendingMergeSort(Record recArr[], int left, int right)
{
    if(left < right) {
        int mid = (left + right) / 2;
        descendingMergeSort(recArr, left, mid);    //앞쪽
        descendingMergeSort(recArr, mid+1, right);//뒤쪽
        descendingMerge(recArr, left, mid, right);
    }
}
// recArr는 수정된다.
void descendingMerge(Record recArr[], int left, int mid, int right)
{
    int ifront    = left; 
    int iback    = mid + 1;
    Record* tmpRecArr = (Record*)malloc( sizeof(Record) * (right-left+1) );
    int index; //임시배열 인덱스
    int j;
    
    for(index = 0; index <= right; index++){
        if(ifront > mid) {    //앞쪽이 완료됨: 뒷쪽 모두 복사
            for(j = iback; j <= right; j++) {
                tmpRecArr[index] = recArr[j];
                index++;
            }
            break;
        } 
        else if(iback > right) {    //뒷쪽이 완료됨: 앞쪽 모두 복사
            for(j = ifront; j <= mid; j++) {
                tmpRecArr[index] = recArr[j];
                index++;
            }
            break;
        }
        else {    //앞뒤 모두 원소가 남음: 비교 가능한경우                    
            if(recArr[ifront].key > recArr[iback].key) {
                tmpRecArr[index] = recArr[ifront];
                ifront++;
            } else {
                tmpRecArr[index] = recArr[iback];
                iback++;
            }
        }
    }    
 
    //마지막으로 원본 배열 수정
    index = 0;
    for(j = left; j <= right; j++) {
        recArr[j] = tmpRecArr[index];
        index++;
    }
 
    free(tmpRecArr);
}
cs


네 뭐지소트 입니다. 



전에 만든 힙소트와 함께

32768개의 양수 배열로 테스트 해보았습니다.

1
2
3
4
5
6
7
8
9
10
11
12
heapSortRecordArr 함수를 수행하는 걸린 시간(초) :       0.0239764 seconds
heapSortRecordArr 함수를 수행하는 걸린 시간(초) :       0.0320179 seconds
heapSortRecordArr 함수를 수행하는 걸린 시간(초) :       0.0240015 seconds
heapSortRecordArr 함수를 수행하는 걸린 시간(초) :       0.0240023 seconds
heapSortRecordArr 함수를 수행하는 걸린 시간(초) :       0.0290036 seconds
 
descendingMergeSort 함수를 수행하는 걸린 시간(초) :     0.0530072 seconds
descendingMergeSort 함수를 수행하는 걸린 시간(초) :     0.0310047 seconds
descendingMergeSort 함수를 수행하는 걸린 시간(초) :     0.0410024 seconds
descendingMergeSort 함수를 수행하는 걸린 시간(초) :     0.0410024 seconds
descendingMergeSort 함수를 수행하는 걸린 시간(초) :     0.0280011 seconds
descendingMergeSort 함수를 수행하는 걸린 시간(초) :     0.0469852 seconds
cs


뭐지? 왜 저렇게 오래 걸리지? 뭐지소트는 병신인가?

그렇지 않습니다. 코드를 쓱 봐도 알겠지만 동적할당을 오지게 많이 해서 그렇읍니다

즉 제가 병신입니다 


하지만 귀찮으므로 더이상의 최적화는 생략한다