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

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

7개의 정렬법

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

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

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

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

#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]; //합병정렬을 사용하기 위한 추가공간

1. C언어 선택정렬 소스

//선택정렬
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함수를 이용해 바꾸어준다.
    }
}

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

2. C언어 삽입정렬 소스

//삽입정렬
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;
    }
}

3. C언어 버블정렬 소스

//버블정렬
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);
    }
}

4. C언어 쉘정렬 소스

//쉘 정렬
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);
    }
}

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

5. C언어 합병정렬 소스

//합병정렬
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);
    }
}

6. C언어 퀵정렬 소스

//퀵정렬
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);
    }
}

7. C언어 힙정렬 소스

//히프정렬
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);
    }
}

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

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

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);
}

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