본문 바로가기
C++ 200제/코딩 IT 정보

C언어 힙, 선택, 삽입, 버블, 쉘, 합병, 퀵 정렬 소스 코드 (7종류)

by vicddory 2017. 5. 1.

C언어 힙, 선택, 삽입, 버블, 쉘, 합병, 퀵 정렬 소스 코드 (7종류)


7개의 정렬법

7개의 정렬이란, 선택정렬, 삽입정렬, 버블정렬, 쉘정렬, 합병정렬, 퀵정렬, 힙정렬입니다. 정수 20만개 까지만 받도록 설정해 놨고, 아래의 그림은 18만개의 정수를 입력받아 정렬시킨 결과입니다.


7개의 정렬법 - 선택 삽입 버블 쉘 합병 퀵 힙[C언어 선택정렬, 삽입정렬, 버블정렬, 쉘정렬, 합병정렬, 퀵정렬, 힙정렬] 예제 소스 코드


C언어 정렬 예제 소스 코드 - c.zip [클릭]


7개 정렬 소스 공통 부분 (선택정렬, 삽입정렬, 버블정렬, 쉘정렬, 합병정렬, 퀵정렬, 힙정렬)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_SIZE 1000000 
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )
//x와 y의 위치를 temp값을 이용해 서로 바꿈
 
#define MAX_ELEMENT 200000 //히프 정렬 최대값
 
typedef struct {
    int key;
} element;
 
typedef struct {
    element heap[MAX_ELEMENT];
    int heap_size;
} HeapType;
 
int sorted[MAX_SIZE]; //합병정렬을 사용하기 위한 추가공간
cs

1. C언어 선택정렬 소스


1
2
3
4
5
6
7
8
9
10
11
12
13
//선택정렬
void selection_sort(int* list[], int n)
{
int i, j, least, temp;
 
for(i = 0; i < n-1 ; i++) { 
    least = i;
    for (j = i + 1; j < n; j++//j값은 항시 i가 가리키는 다음값부터 반복한다.
        if(list[j] < list[least]) 
            least = j; //이전값이 지금 가리키는 값보다 작다면
        SWAP(list[i], list[least], temp); //SWAP함수를 이용해 바꾸어준다.
    }
}
cs


C언어 정렬 소스 코드 퀵[C언어 선택정렬, 삽입정렬, 버블정렬, 쉘정렬, 합병정렬, 퀵정렬, 힙정렬] 예제 소스 코드


2. C언어 삽입정렬 소스


1
2
3
4
5
6
7
8
9
10
11
12
13
14
//삽입정렬
void insertion_sort(int* list[], int n)
{
    int i=0, j=0, key;
    for (i = 1 ; i < n ; i++
    {
        key = list[i]; 
 
        for(j = i-1 ; j >= 0 && list[j]>key ; j--
            list[j+1= list[j];
 
        list[j+1= key;
    }
}
cs


3. C언어 버블정렬 소스


1
2
3
4
5
6
7
8
9
10
11
12
13
//버블정렬
void bubble_sort(int* list[], int n)
{
    int i, j, temp;
    for (i = n-1 ; i > 0 ; i--
    {
        for (j = 0 ; j < i ; j++)
                //j의 값은 0부터 시작하여 i값과 마주칠때까지 반복한다.
            
            if (list[j] > list[j+1])
                SWAP (list[j], list[j+1], temp);
    }
}
cs

4. C언어 쉘정렬 소스


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//쉘 정렬
inc_insertion_sort(int* list[], int first, int last, int gap)
{
    int i, j, key;
    for (i = first+gap; i <= last; i = i + gap){
        key = list[i];
        for(j = i - gap ; j >= first && key < list[j] ; j = j - gap)
            list[j+gap] = list[j];
        list[j+gap] = key;
    }
}
 
void shell_sort( int* list[], int n )
{
    int i, gap;
    for (gap = n/2 ; gap > 0 ; gap = gap / 2 ) { 
        if( (gap%2== 0 )
            gap++
 
        for(i=0; i<gap; i++)
            inc_insertion_sort(list, i, n-1, gap);
    }
}
cs


C언어 정렬 소스 예제 정수[C언어 선택정렬, 삽입정렬, 버블정렬, 쉘정렬, 합병정렬, 퀵정렬, 힙정렬] 예제 소스 코드


5. C언어 합병정렬 소스


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
//합병정렬
void merge(int list[], int left, int mid, int right)
{
    int i, j, k, l;
    i = left;
    j=mid+1;
    k=left;
 
    while(i<=mid && j<=right){
        if(list[i]<=list[j])
            sorted[k++= list[i++];
        else
            sorted[k++= list[j++];
    }
 
    if (i>mid)
        for(l=j ; l<=right; l++)
            sorted[k++= list[l];
    else
        for(l=i ; l<=mid ; l++)
            sorted[k++= list[l];
 
    for(l=left ; l<=right ; l++)
        list[l] = sorted[l];
}
 
void merge_sort(int list[], int left, int right)
{
    int mid;
    if(left<right){
        mid = (left+right)/2;
        merge_sort(list, left, mid);
        merge_sort(list, mid+1, right);
        merge(list, left, mid, right);
    }
}
cs


6. C언어 퀵정렬 소스


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
//퀵정렬
int partition(int* list[], int left, int right)
{
    int pivot, temp;
    int low, high;
    low = left;
    high = right+1;
    pivot = list[left];
    
    do{
        do
        low++;
        while(low <= right && list[low] < pivot);
        do
        high--;
        while(high >= left && list[high] > pivot);
        if(low    } while(low
    SWAP(list[left], list[high], temp);
 
    return high;
}
 
void quick_sort(int* list[], int left, int right)
{
    if(left<right){
        int q=partition(list, left, right);
        quick_sort(list, left, q-1);
        quick_sort(list, q+1, right);
    }
}
cs

7. C언어 힙정렬 소스


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
//히프정렬
void insert_max_heap(HeapType *h, element item)
{
    int i;
    i = ++(h->heap_size);
 
    while((i != 1&& (item.key > h->heap [i/2].key)) {
        h->heap[i] = h -> heap[i/2];
        i /= 2;
    }
    h->heap[i] = item;
}
 
element delete_max_heap(HeapType *h)
{
    int parent, child;
    element item, temp;
 
    item = h->heap[1];
    temp = h->heap[(h->heap_size)--];
 
    parent = 1;
    child = 2;
 
    while(child <= h->heap_size) {
        if( ( child < h->heap_size ) &&
            (h->heap[child].key) < h->heap[child+1].key)
            child++;
        if( temp.key >= h->heap[child].key ) break;
 
        h->heap[parent] = h->heap[child];
 
        parent = child;
        child *= 2;
    }
    h->heap[parent] = temp;
    return item;
}
 
init (HeapType *h)
{
    h->heap_size = 0;
}
 
void heap_sort(element list[], int n)
{
    int i;
    HeapType h;
 
    init(&h);
    for(i = 0; i < n ; i++)
        insert_max_heap(&h, list[i]);
    for(i=(n-1) ; i >= 0 ; i--){
        list[i] = delete_max_heap(&h);
    }
}
cs


C언어 힙, 선택, 삽입, 버블, 쉘, 합병, 퀵 정렬 소스 코드 (7종류)[C언어 선택정렬, 삽입정렬, 버블정렬, 쉘정렬, 합병정렬, 퀵정렬, 힙정렬] 예제 소스 코드


마지막, 시간 확인 소스 코드. Main() 함수


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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
void main()
{
    int *jung; 
    element *jung2; 
    int i, rn;
    double timeu = 0, timen = 0;
    double timeSel, timeIns, timeBub, timeShe;
        double timeMar, timeQui, timeHeap, timeRad;
 
    int count = 0;
    FILE *fp; //data.txt에 입력받을 파일포인터 
    FILE *fo; //data.txt에서 값을 받아올 파일포인터
 
    srand( (unsigned)time(NULL) );
    fp = fopen("data.txt" ,"w");
    
    printf("몇 개의 랜덤한 정수를 입력받겠습니까 : ");
    scanf("%d"&count);
 
    for(i=0 ; i < count ; i++)
    {
        rn=rand()%count;
        fprintf(fp, "%d ", rn);
    }
 
    fclose(fp);
    fo = fopen("data.txt" ,"r");
 
    jung = (int *)malloc(sizeof(int)*count); //동적메모리 할당
 
    for (i = 0 ; i < count ; i++)
    {
        fscanf(fo, "%d"&jung[i]);
    } 
 
//선택정렬 시간체크
    timeu = clock()/1000.0;
    selection_sort(jung, count);
    timen = clock()/1000.0;
    timeSel = timen-timeu;
 
    rewind(fo); //파일포인터를 처음으로
    
    for (i = 0 ; i < count ; i++)
    {
        fscanf(fo, "%d"&jung[i]);
    }
 
//삽입정렬 시간체크
    timeu = clock()/1000.0
    insertion_sort(jung, count);
    timen = clock()/1000.0;
    timeIns = timen-timeu;
 
    rewind(fo);
 
    for (i = 0 ; i < count ; i++)
    {
        fscanf(fo, "%d"&jung[i]);
    }
 
//버블정렬 시간체크
    timeu = clock()/1000.0;
    bubble_sort(jung, count);
    timen = clock()/1000.0;
    timeBub = timen-timeu;
 
    rewind(fo);
 
    for (i = 0 ; i < count ; i++)
    {
        fscanf(fo, "%d"&jung[i]);
    }
 
//쉘정렬 시간체크
    timeu = clock()/1000.0;
    shell_sort(jung, count);
    timen = clock()/1000.0;
    timeShe = timen-timeu;
 
    rewind(fo);
 
    for (i = 0 ; i < count ; i++)
    {
        fscanf(fo, "%d"&jung[i]);
    }
 
//합병정렬 시간체크
    timeu = clock()/1000.0;
    merge_sort(jung, 0, count-1);
    timen = clock()/1000.0;
    timeMar = timen-timeu;
 
    rewind(fo);
 
    for (i = 0 ; i < count ; i++)
    {
        fscanf(fo, "%d"&jung[i]);
    }
 
//퀵정렬 시간체크
    timeu = clock()/1000.0;
    quick_sort(jung, 0, count-1); 
    timen = clock()/1000.0;
    timeQui = timen-timeu;
 
    rewind(fo);
 
//히프정렬 시간체크
    jung2 = (int *)malloc(sizeof(int)*count);
 
    for (i = 0 ; i < count ; i++)
    {
        fscanf(fo, "%d"&jung2[i].key); 
    }
 
    timeu = clock()/1000.0
    heap_sort(jung2, count);
    timen = clock()/1000.0;
    timeHeap = timen-timeu;
 
//기수정렬 시간체크
    printf("\n\n\n%d개의 정수를 정렬하는데에 걸리는 시간은.
         \n\n선택정렬 : %lf초\n삽입정렬 : %lf초\n버블정렬 : %lf초\n
         쉘  정렬 : %lf초\n합병정렬 : %lf초
         \n퀵  정렬 : %lf초\n히프정렬 : %lf초\n",
         count, timeSel, timeIns, timeBub, timeShe, timeMar, timeQui, timeHeap);
 
    fclose(fo);
    free(jung);
}
cs


C언어 힙, 선택, 삽입, 버블, 쉘, 합병, 퀵 정렬 소스 코드 (7종류)

댓글