자료구조 :: 정렬(1) ;정의, 선택정렬, 삽입정렬

# 정렬(Sorting)

■ 정렬이란?
정렬은 물건을 크기순으로 오름차순, 내림차순으로 나열 하는 것을 의미한다.
지금까지 개발된 정렬 알고리즘은 매우 많지만 모든 경우에 있어서 최상의 성능을 보여주는 최적 알고리즘은
존재하지 않는다. 따라서 이들 방법들 중에서 현재의 프로그램 수행환경에서 가장 효율적인 정렬 알고리즘을
선택하여야 한다.

■ 정렬의 분류
(1) 단순하지만 비효율적인 방법 : 삽입정렬, 선택정렬, 버블정렬
(2) 복잡하지만 효율적인 방법　 : 퀵정렬, 힙정렬, 합병정렬, 기수정렬

또한 내부 정렬과 외부정렬로도 구분하며 안정성 측면에서도 구분할 수 있다.


# 선택 정렬(selection sort)

선택정렬은 안정성이 좋지 않고 성능 또한 좋지 않다.
선택 정렬의 복잡도 : O(n²) (평균)

# 삽입 정렬(insertion srot)

삽입정렬은 비교적 많은 레코드들의 이동이 이루어지기 때문에 레코드가 많은 경우 적합하지 않다.
반면에 안정적이며 대부분의 레코드가 이미 정렬되어 있는 경우에는 매우 효율적이다.
삽입 정렬의 복잡도 : O(n²) (평균)

SelectSort_InsertSort.cpp

코드의 간결함을 위해 SWAP,random 매크로를 사용하였다. 오히려 지저분해졌다.

#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 SelectionSort(int *list, int n) 
{ 
int i,j,temp,least; 

for(i=0;i<n-1;i++)  
    { 
        least=i; // list[i]를 최소값으로 함

for(j=i+1;j<n;j++) 
        { 
if(list[least]>list[j]) 
                least=j; // 기준값보다 작은값으로 인덱스 변경
        } 

if(least != i) // 최소값 변경이 없으면 SWAP하지 않는다
            SWAP(list[i],list[least],temp); 
    }     
} 

void InsertSort(int *list, int n) 
{ 
int i,j,temp,item; 

for(i=1;i<n;i++) 
    { 
        item=list[i]; // list[i]를 기준값으로 함

for(j=i-1;j>=0;j--) // j는 기준을 제외하고 0보다 크거나 같을때까지
        { 
if(list[j] > item) // 정렬이 된 곳 중에서 item보다 작은값을 찾음
                list[j+1]=list[j]; 
else
break;  
        } 
        list[j+1]=item; // 작은값을 찾은 자리에 대입
    } 
} 

void ScreenOut(int *pList, int n) 
{ 
int i; 
for(i=0;i<n;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); 

    InsertSort(list,input); 

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

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

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

    SelectionSort(list,input); 

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

    free(list); 

return0; 
}