[C-알고리즘] 버블정렬,선택정렬,삽입정렬

※ 밑의 내용들은 오름차순일 경우에 대한 설명입니다.

> 버블 정렬(Bubble sort) 

  첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 

 ... n 번 째 자료와 n+1 번째 자료를 비교하여 교환하면서 자료를 정렬한다.

1회전이 끝나면 가장 큰 자료가 맨 뒤로 이동하므로 

2회전에서는 맨 끝에 있는 자료는 정렬에서 제외된다.

2회전이 끝나면 끝에서 두 번째 자료까지 정렬에서 제외된다. 

이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

<버블정렬로 데이터 정렬>

 배열 [ 2 , 5 , 4 , 3 , 1 ]

다음은 회전이 끝날 때마다 위의 배열의 값들이 정렬되는 과정이다.

[빨간색 형광펜으로 표시된 자료는 정렬에서 제외되는 자료]

※ 1회전 ※

-----------

2 4 3 1 5

※ 2회전 ※

-----------

2 3 1 4 5

※ 3회전 ※

-----------

2 1 3 4 5

※ 4회전 ※

-----------

1 2 3 4 5

최종 : 1 2 3 4 5

> 선택 정렬(Selection sort)

 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교해서 

가장 작은 값을 찾아 첫 번째에 놓는다.

그리고 두 번째 자료를 세 번째 자료부터 마지막 자료까지 차례대로 비교해서 

그 중 가장 작은값을 찾아 두 번째 위치에 놓는 과정을 반복한다.

 

1회전이 수행되고 나면 가장 작은값의 자료가 맨 앞에 오게된다.

따라서 그 다음 회전에서는 두 번째 자료를 가지고 비교한다.

<선택정렬로 데이터 정렬>

 배열 [ 3 , 1 , 5 , 4 , 2 ]

다음은 회전이 끝날 때마다 위의 배열의 값들이 정렬되는 과정이다.

[빨간색 형광펜으로 표시된 자료는 정렬에서 제외되는 자료]

※ 1회전 ※

-----------

1 3 5 4 2

※ 2회전 ※

-----------

1 2 5 4 3

※ 3회전 ※

-----------

1 2 3 5 4

※ 4회전 ※

-----------

1 2 3 4 5

최종 : 1 2 3 4 5

> 삽입 정렬(Insertion sort)

삽입 정렬은 두 번째 자료부터 시작한다.

앞(왼쪽)들의 자료들과 비교하여

삽입할 위치를 지정 한 후에 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입한다.

즉,

자료[2]는 자료(1)

자료[3]은 자료(1,2)

자료[4]는 자료(1,2,3)

와 비교한 후 자료가 삽입될 위치를 찾게된다.

자료가 삽입될 위치를 찾게 되면 

그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.

<삽입정렬로 데이터 정렬>

 배열 [ 2 , 5 , 4 , 1 , 3 ]

다음은 회전이 끝날 때마다 위의 배열의 값들이 정렬되는 과정이다.

[빨간색 형광펜 : 이미 정렬된 자료의 그룹

 하늘색 형광펜 : 정렬되지 않은 자료의 그룹 ]

※ 1회전 ※

-----------

2 5 4 1 3

※ 2회전 ※

-----------

2 4 5 1 3

※ 3회전 ※

-----------

1 2 4 5 3

※ 4회전 ※

-----------

1 2 3 4 5

최종 : 1 2 3 4 5

위의 세 가지 정렬을 C로 작성했습니다.

※ ????_sort( int data[] , int order , int processing)

data는 자료가 저장된 배열,

order는 인자값이 ASC면 오름차순 정렬,

           DES면 내림차순으로 정렬.

processing은 인자값이 ON이면 해당 정렬의 회전하는 과정을 보여줍니다. 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define ARRAY_SIZE 5 // 배열크기 
#define SWAP(X,Y) int ntmp=X; X=Y; Y=ntmp; // 데이터 교환  
 
enum ORDER {ASC,DES}; // 오름차순(Ascending) , 내림차순(Descending) 
enum OFF_ON {OFF,ON}; // 정렬 처리과정 보기(off,on) 
 
void rand_num( int data[] ); // 난수 생성  
void bubble_sort( int data[] , int order , int processing ); // 버블정렬
void selection_sort( int data[] , int order , int processing ); // 선택정렬 
void insertion_sort( int data[] , int order , int processing ); // 삽입정렬 
void output( int data[] , char msg[] ); // 출력 
 
int main()
{    
    int data[ARRAY_SIZE];     
    
    rand_num(data);     
    bubble_sort(data,ASC,ON);    
//    selection_sort(data,DES,ON);
//    insertion_sort(data,ASC,OFF);
    
    output(data , "\n<< 정렬 후 >>");
    
    
}
 
 
void rand_num( int data[] )
{
    srand(time(NULL));
    
    int i,j;
    
    for(i=0; i<ARRAY_SIZE; i++) { 
 
        data[i] = rand() % ARRAY_SIZE +1; // 배열크기만큼의 난수값 발생 
    
        for(j=0; j<i; j++){ // 값중복체크 
            if (data[i] == data[j] ) {
            i--;
            break;
            }
        }
    }
    
    output(data , "<< 정렬 전 >>");
}
 
void bubble_sort( int data[] , int order , int processing )
{
    int i,j;
        
        
    for(i=0; i<ARRAY_SIZE-1; i++)
    {
         
        for(j=0; j<ARRAY_SIZE-1-i; j++)
        {    
            if (order == ASC) {     
                if ( data[j] > data[j+1] ) { SWAP(data[j],data[j+1]); }            
                }
            else {  
                if ( data[j] < data[j+1] ) { SWAP(data[j],data[j+1]); }
            }
        }
         if ( processing == ON ) {
         printf("\n※ %d회전 ※\n",i+1); 
         output(data,"-----------");
        }
    }
    
}
 
void selection_sort( int data[] , int order , int processing )
{
    int i,j;
    
    for(i=0; i<ARRAY_SIZE-1; i++)
    {
    
        for(j=i+1; j<ARRAY_SIZE; j++){
    
        if (order == ASC) {         
             if (data[i] > data[j]) {     SWAP(data[i],data[j]); }
        }
        else {
            if (data[i] < data[j]) {     SWAP(data[i],data[j]); }    
        }
        
        }
        if ( processing == ON ) {
         printf("\n※ %d회전 ※\n",i+1); 
         output(data,"-----------");
        }
    }
        
    
}
 
 
void insertion_sort( int data[] , int order , int processing )
{
    int i,j,key;
    
    for(i=1; i<ARRAY_SIZE; i++)
    {
        key = data[i];
        for(j=i-1; j>=0; j--)
        {    
            if (order == ASC) { 
                if( data[j] > key ) { data[j+1] = data[j]; }
                else break;
            } else {
                if( data[j] < key ) { data[j+1] = data[j]; }
                else break;
            }
            
        }    data[j+1] = key;
    
        if ( processing == ON ) {
         printf("\n※ %d회전 ※\n",i); 
         output(data,"-----------");
        }
        
    }
}
 
void output( int data[] , char msg[] ) 
{
    int i;
    
    puts(msg);
    for(i=0; i<ARRAY_SIZE; i++)
    {
        printf("%d ",data[i]);    
        if ( (i+1) % 5 == 0 ) putchar('\n'); // 5개의 데이터 단위로 개행한다. 
    }
    
}