자료구조 :: 정렬(2) 버블 정렬, 쉘 정렬

# 버블 정렬(bubble sort)

버블 정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 과정을
리스트의 왼쪽부터 시작하여 오른쪽 끝까지 진행하는 정렬이다.
버블 정렬은 단순하지만 데이터의 교환작업이 정렬된 위치에 있더라도 일어나기 때문에 비효율적이다.
데이터의 교환이 없다면 정렬이 완성되었음을 의미하기때문에 종료하는 코드를 삽입하였다.

버블정렬의 성능 : O(n²) (평균)


# 쉘 정렬(shell sort)

쉘 정렬은 1959년 Donald Shell이란 사람에 의해 개발된 정렬 방법이다.
원래의 리스트를 여러개의 부리스트로 분할하고, 이 분할된 부리스트들에서 정렬을 행하는 방법이다.
원래 이스트를 여러개의 부리스트로 분할할 때 서로 멀리 떨어져 있는 레코드들로 구성을 하는데 이 레코드는
일정한 간격을 가지게 된다. 이러한 간격은 매 정렬 단계마다 줄어들게 되며 마지막 단계에서는 1이 되어 전체의
레코드가 하나의 부리스트가 되어 인접한 레코드 사이에 비교 교환이 이루어지게 된다.
각 정렬 단계에서 부리스트를 만들기 위해 적용될 간격들은 증분 순서(increment sequence)라고 한다.
여기서 증분 순서로는 D. E. Knuth에 의해 제안된 순서인 1, 4, 13, 40, 121, 364, ... 를 사용한다.

쉘정렬의 성능 : 최악의 경우 O(n²) 평균적으로 O(n^1.5)

BubbleSort_ShellSort.cpp

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

#define random(n) (rand()%n) 
#define SWAP(x,y,t) ((t) = (x),(x) = (y),(y) = (t)) 

void BubbleSort(int *list, int n) 
{ 
int i,j,temp,flag; 

for(i=n-1;i>0;i--) 
    { 
        flag=0; 
for(j=0;j<i;j++) 
        { 
if(list[j] > list[j+1]) 
            { 
                SWAP(list[j],list[j+1],temp); 
                flag=1; 
            } 
        } 
if(!flag) 
break; 
    } 
} 

void ShellSort(int *list, int n) 
{ 
int i,j,temp,gap; 

for(gap=1;gap<n/3;gap=3*gap+1); // 최적의 간격을 찾는다

while(gap > 0) 
    { 
for(i=gap;i<n;i++) // gap을 간격으로 하여 삽입정렬
        { 
for(j=i-gap;j>=0;j=j-gap) 
            { 
if(list[j]>list[j+gap]) 
                    SWAP(list[j],list[j+gap],temp); 
else
break; 
            } 
        } 
        gap/=3; // 간격을 줄인다 
    } 
} 

void ScreenOut(int *pList, int count) 
{ 
int i; 
for(i=0;i<count;i++) 
        printf("%d ",pList[i]); 

    puts(""); 
} 

int main() 
{ 
int i,input; 
int *list; 

    srand(time(NULL)); 

    printf("Input Data Count : "); 
    scanf("%d",&input); 

    list=(int *)malloc(sizeof(int)*input); 

for(i=0;i<input;i++)     
        list[i]=random(100); 

    printf("Insert Data : "); 
    ScreenOut(list,input); 

    BubbleSort(list,input); 

    printf("Sorting Data : "); 
    ScreenOut(list,input); 

for(i=0;i<input;i++)     
        list[i]=random(100); 

    printf("Insert Data : "); 
    ScreenOut(list,input); 

    ShellSort(list,input); 

    printf("Sorting Data : "); 
    ScreenOut(list,input); 

    free(list); 

return0; 
}