Sort 선택 정렬(Selection Sort) 알고리즘

[Sort] 선택 정렬(Selection Sort) 알고리즘

 

선택 정렬은 원리가 간단한 정렬 알고리즘 중 하나다.

배열[A ··· n] 에서 가장 큰 원소를 마지막 원소와 자리를 바꾸거나, 가장 작은 원소를 제일 앞 원소와 자리를 바꾸는 것이다.

자리 바꾸기가 완료되면 그 원소가 있는 자리는 신경쓰지 않아도 된다.

 

배열 { 3, 5, 1, 4, 2} 가 있을 때, 뒤에서 부터 오름차순 정렬하는 모습은 다음과 같다.

*보통 프로그래밍 언어에서 인덱스는 0번 부터 시작한다.

{ 3, 5, 1, 4, 2} 중 가장 큰 수 '5'를 찾는다. ('5'는 인덱스 1번에 있다.)

{ 3, 2, 1, 4, 5} '5'를 가장 뒤에 있는 '2'와 자리를 바꾼다. (1번 인덱스와 4번 인덱스 자리 바꿈)

{ 3, 2, 1, 4, 5} 중 가장 큰 수 '4'를 찾는다. ('5'는 정렬이 완료된 상태이므로 0번 인덱스 ~ 3번 인덱스 까지만 검사한다.)

                       자리를 바꿀 필요가 없다.

{ 1, 2, 3, 4, 5} 중 가장 큰 수 '3'을 찾아 바꾼다. ('3'과 '1'을 바꾸었다.)

{ 1, 2, 3, 4, 5} 중 가장 큰 수 '2'를 찾았지만 자리를 바꿀 필요가 없다.

 

배열 { 3, 5, 1, 4, 2} 가 있을 때, 앞에서 부터 오름차순 정렬하는 모습은 다음과 같다.

{ 3, 5, 1, 4, 2} '1'을 찾아 앞과 바꿈

{ 1, 5, 3, 4, 2} '2'를 찾아 바꿈

{ 1, 2, 3, 4, 5} '3', '4' 를 찾아 바꿈

이번에는 앞에서 부터 정렬했으므로 한 번 반복될 때 마다. 가장 앞에 있는 인덱스는 검사에서 제외한다.

 

아래는 참고용 코드이다.

// 가장 작은 수를 앞으로 보내는 선택 정렬 (배열 안 숫자 A[]>0)
SeletionSort(A[], n) // 배열 A와 배열 A의 크기를 받는다.
{
	for(int i = 0; i < n-1; i++)
    {
    	int largestNumber = A[0];	// 가장 큰 수를 담을 공간
        int index = i; 		// 가장 큰 수의 인덱스를 담을 공간
        
    	for(int j = i+1; j < n; j++)
        {
        	if(largestNumber < A[j])	// 큰 수 비교
            {
            	largestNumber = A[j];	// 큰수 교체
                index = j;				// 인덱스 교체
            }
        }
        // 자리 바꿈
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

 

 

정확성, 효율성을 고려하지 않고 적은 검증되지 않은 코드이다. 참고용으로만 보길 바란다.