[알고리즘] 단순 정렬 알고리즘 & 선택 정렬 알고리즘

단순 정렬 알고리즘

for(i=1 ; i<n ; i++) {
    for(j=i+1; j<=n ; j++) {
        if( a[i] > a[j]) swap( a[i], a[j] );
    }
}

 

i가 1부터 n-1까지 반복하고 j가 그 다음 데이터부터 n까지 반복하면서 a[i]이 a[j]보다 크면 서로의 값을 바꿔주어 가장 작은 값이 앞에 올 수 있도록 정렬하는 알고리즘이다.

초기 상태가 [ 21  34  4  54  29  17 ]인 데이터 배열이 있을 때 위 알고리즘을 실행한다면

[ 4  34  21  54  29  17 ]

[ 4  17  34  54  29  21 ]

...

[ 4  17  21  29  34  54 ]로 오름차순으로 잘 정렬된 것을 확인할 수 있다.

 

선택 정렬 알고리즘 

데이터 중에서 가장 작은 값을 찾아 오름차순으로 정렬될 수 있도록 순서를 바꿔주는 알고리즘

전체 코드는 아래와 같다.

int i,j,min;
 
for(i=1 ; i<n ; i++) {
    min =i;
    for(j=i+1; j<=n ; j++) {
        if(a[min] > a[j]) min = j;
    }
    swap(a[i], a[min])
}

 

i가 1 부터 n까지 a라는 배열에 들어있는 데이터 갯수만큼 반복문을 돌면서 가장 작은 최소 값을 찾아 swap 해주는 것이다.

먼저 첫번째 배열의 인덱스를 최소값 인덱스로 설정한다. min = i

그 후 i+1 번째 데이터부터 n까지 반복문을 돌아 a[min] 값보다 작은 값이 있다면 min 값을 수정해준다. 반복문이 끝나 최소값을 찾고난 뒤에는 오름차순 정렬을 위해 a[i]와 swap 해준다. 

예시를 보자면 다음과 같다.

초기 상태로 [ 21  34  4  54  29  17 ]인 데이터 배열이 있을 때 위 코드를 실행하면 먼저 min=i이기 때문에 a[i]와 a[min] 값 모두 21이다. 두번째 반복문을 실행하면  21과 34를 비교하고 21과 4을 비교하고 21과 54를 비교하고....17까지 비교를 마치게 된다.

이 과정에서 21과 비교했을 때 더 작은 값은 4이기 때문에 4의 인덱스인 2가 min에 들어가게 된다. 4보다 작은 데이터는 없으니 반복문을 종료하고 swap(a[i], a[min]) 즉, swap( 21, 4 )를 하게 된다.

이 첫번째 과정을 마치면 데이터 배열은 [ 4  34  21  54  29  17 ]의 상태가 된다. 모든 반복이 끝난 뒤에는 [ 4  17  21  29  34  51 ]로 정렬된 데이터 배열을 볼 수 있다.

 

 

 

참고 : C언어로 작성하는 컴퓨터 알고리즘 / 이한출판사