0x07.정렬 알고리즘:선택, 삽입 정렬

정렬 알고리즘

 

정렬 알고리즘은 실생활에서 아주 많이 사용된다. 내부 정렬, 외부 정렬, 비교 정렬, 분배 정렬등 아주 많은 종류가 있지만 아주 간단한 것부터 시작해보자.

 

가장 간단한 정렬방법은 오름차순과 내림차순일 것이다.

 

20, 28, 3, 41, 26, 6 

 

위와 같은 순서를 아래와 같이 정렬하는 것을 오름차순 정렬이라고 하고, 그 반대를 내림차순 정렬이라고 한다.(은근 헷갈림;;)

 

3, 6, 20, 26, 28, 41

 

아주 간단한 알고리즘이기에 아주 간단하게 구현할 수 있다.

 

void sort(){

int i, j;

for(i=1; i<n; i++){

for(j=i+1;j<=n;j++){

if(a[i]>a[j])

swap(a[i],a[j]);

}

}

}

 

void swap(){

int temp;

temp=p;

p=q;

q=temp;

}

 

swap 함수를 통해 temp라는 임시 변수를 활용하여 순서를 바꾸는 알고리즘이다.

 

다음과 같은 절차를 거쳐 완성이 된다.

 

 

1. 선택 정렬

 

위의 알고리즘을 살짝 변형한 방법으로 이 방식은 비교는 하지만 일일히 교환은 하지 않는다. 대신 minpos라는 값에 최솟값의 장소를 저장해 두었다가 모든 루프가 끝난 시점에서 최솟값을 활용하여 교환을 한다. 이는 레코드가 커서 데이터의 비교보다 교환에 걸리는 시간이 큰 경우에 활용할 수 있다.

 

void selectionsort(){

int i, j, minpos;

for(i=1;i<n;i++){

minpos=i;

for(j=i+1;j<=n;j++){

if(a[j]<a[minpos])

minpos=j;

}

}

}

 

 

 

그림에서 색으로 표시된 곳이 반복문이 끝나는 시점에 minpos가 가리키는 곳이다.

 

 

 

2. 삽입 정렬

 

삽입정렬의 핵심은 데이터를 삽입해도 값의 순서가 그대로 유지되도록 하는 것이다. 즉, 배열을 삽입하기 위해서 그 장소보다 오른쪽에 있는 데이터들을 오른쪽으로 한칸씩 시프트(shift)해야 한다. 물론 이진탐색법을 사용하면 빠르게 찾을 수 있겠지만, 삽입장소보다 오른쪽에 위치한 데이터들을 이동하는 시간이 오래 걸리는 경우가 대다수이므로 위 방법을 사용하여 삽입하는 장소를 찾는것이 일반적이다.

 

void insertionsort(){

int i, j;

int w;

for(i=2;i<=n;i++){

w=a[i];

a[0]=w;

while((w<a[j]&&(j>=0)){

a[j+1]=a[j];

j=j-1;

}

a[j+1]=w;

}

}

 

 

w가 바로 삽입할 데이터를 가리킨다. 이 알고리즘은 아래와 같은 순서로 실행된다.