선택 정렬(Selection Sort) 알고리즘 개념과 예제

선택 정렬

선택 정렬은 정렬 알고리즘 중에 하나로 무작위로 배치된 데이터에서 최솟값을 선택해 최솟값이 있어야 할 인덱스로 데이터를 변경하는 정렬방식이다.

선택 정렬 알고리즘의 진행방식은 아래와 같다. (오름차순 기준)

1.  무작위로 나열된 데이터에서 최솟값 X를 찾는다.
2.  X값 과 현재 데이터에서 첫번째에 있는 값의 위치를 변경한다.
3.  첫번째 데이터를 제외하고 나머지 데이터에서 1번 과정부터 다시 시작.

 

선택 정렬 예시

아래와 같이 무작위로 배치된 데이터가 있다고 가정하자.

33

8

10

6

5

25

1

16

 

이 데이터에서 최솟값 X를 찾아야 하고,  X는 1이 된다.

33

8

10

6

5

25

1

16

 

1을 현재 데이터의 첫번째에 해당하는 33과 자리 교체를 한다.

1

8

10

6

5

25

33

16

 

1은 자기 자리를 찾아갔기에 정렬 알고리즘에서 제외한다.

1

8

10

6

5

25

33

16

 

남아있는 데이터[8...16] 중 최솟값 X를 찾아야 하고, X는 5가 된다.

1

8

10

6

5

25

33

16

 

5를 현재 데이터의 두번째에 해당하는 8과 자리 교체를 한다.

1

5

10

6

8

25

33

16

 

5은 자기 자리를 찾아갔기에 정렬 알고리즘에서 제외한다.

1

5

10

6

8

25

33

16

 

남아있는 데이터[10...16] 중 최솟값 X를 찾아야 하고, X는 6이 된다.

1

5

10

6

8

25

33

16

 

6을 현재 데이터의 세번째에 해당하는 10과 자리교체를 한다.

1

5

6

10

8

25

33

16

 

6은 자기 자리를 찾아갔기에 정렬 알고리즘에서 제외한다.

1

5

6

10

8

25

33

16

 

이 다음 단계에도 전 단계와 똑같은 방법을 반복해서 정렬한다.

최솟값 8을 찾아 4번째 자리인 10과 자리교체 후 정렬 알고리즘에서 제외.

1

5

6

8

10

25

33

16

1

5

6

8

10

25

33

16

 

최솟값 10을 찾고 10이 5번째 자리에 위치해 있으니 정렬 알고리즘에서 제외.

1

5

6

8

10

25

33

16

 

최솟값 16을 찾아 6번째 자리인 25과 자리교체 후 정렬 알고리즘에서 제외

1

5

6

8

10

16

33

25

1

5

6

8

10

16

33

25

 

최솟값 25를 찾아 7번째 자리인 33과 자리교체 후 정렬 알고리즘을 끝낸다.

1

5

6

8

10

16

25

33

 

선택 정렬로 정렬 완료.

1

5

6

8

10

16

25

33

 

선택 정렬 C언어 예제 코드

위의 선택 정렬 예시를 C언어로 구현한 것이다.

selectionSort.c

#include <stdio.h>
#define ArrSize 8

int main()
{
	int array[ArrSize] = {33, 8, 10, 6, 5, 25, 1, 16};
	int num, numIndex;
	int minIndex = 0, temp = 0;
	
	while(minIndex < ArrSize){
		num = array[minIndex];
		
		for(int i = minIndex+1; i < ArrSize; i ++)
		{
			if(num > array[i])
			{
				num = array[i];
				numIndex = i;
			}
		}
		
		temp = array[minIndex];
		array[minIndex] = num;
		array[numIndex] = temp;
		
		minIndex++;
	}

	for(int i = 0; i < ArrSize; i++){
		printf("%d ", array[i]);
	}
	return 0;
}

 

int num, numIndex; // 데이터의 최솟값, 최솟값의 인덱스
int minIndex = 0, temp = 0; // 정렬될 데이터의 인덱스, 자리 교체에 사용

선언한 변수에서 num변수는 정렬되어있지 않은 공간에서 데이터의 최솟값을 저장하기 위해 사용한다.

numIndex변수는 데이터의 자리 교체에 사용하기 위해서 num변수의 인덱스를 저장한다.

minIndex변수는 while 반복문의 조건으로 사용하면서 동시에 데이터를 정렬하기 위해서 사용한다.

temp변수는 데이터의 자리 교체에서 임시로 변수를 저장하기 위해 사용한다.

while(minIndex < ArrSize){ // 데이터의 크기만큼 반복 진행
	num = array[minIndex]; // 정렬되지 않은 데이터의 첫번째 요소를 저장
	
	for(int i = minIndex+1; i < ArrSize; i ++) // num변수와 나머지 요소를 차례대로 비교하기 위한 조건
	{
		if(num > array[i]) 
		{
			num = array[i];
			numIndex = i;
		}
	}
	
	temp = array[minIndex]; // 데이터 자리 교체 과정
	array[minIndex] = num;
	array[numIndex] = temp;
	
	minIndex++;
}

이중 반복을 이용해 정렬을 하게 되는데, 그 중 while 반복문은 찾은 최솟값을 알맞는 위치에 넣는 역할을 하고,

for 반복문은 정렬되지 않은 데이터의 최솟값을 찾는 역할을 한다.

num변수에 정렬되지 않은 데이터의 첫번째 요소를 저장하고 for 반복문을 통해 num변수는 데이터의 최솟값으로 바뀌게 된다.

그리고 나온 최솟값을 현재 데이터의 첫번째 요소와 자리 교체를 하게 된다. 이 때 첫번째 요소는 최솟값이 있던 자리로 가게 된다.

이 과정을 반복하면서 데이터의 마지막까지 차례차례 정렬된다.

삽입 정렬을 함수로 구현하면 아래와 같다.

selectionSortFunction.c

#include <stdio.h>
#define ArrSize 8

int selectionSort(int array[], int arrsize);

int main()
{
	int array[ArrSize] = {33, 8, 10, 6, 5, 25, 1, 16};
	
	selectionSort(array, ArrSize);
	
	for(int i = 0; i < ArrSize; i++){
		printf("%d ", array[i]);
	}
	
	return 0;
}

int selectionSort(int array[], int arrsize)
{
	int num, numIndex;
	int minIndex = 0, temp = 0;
	
	while(minIndex < arrsize){
		num = array[minIndex];
		
		for(int i = minIndex+1; i < arrsize; i ++)
		{
			if(num > array[i])
			{
				num = array[i];
				numIndex = i;
			}
		}
		
		temp = array[minIndex];
		array[minIndex] = num;
		array[numIndex] = temp;
		
		minIndex++;
	}
}