[sort] 선택정렬(selection sort)

1학기 자료구조 수업을 더 열심히 들을 걸..이라는 생각을 했다

개인공부이므로 오류가 있을 수 있습니다!

 

우선 정렬을 위해선 작은 수를 찾기 위한 규칙이 필요하며 선택정렬은 그 규칙에 대한 알고리즘이다.

 

1. 정의

선택 정렬은 무작위로 나열되어 있는 데이터를 오름차순으로 정리하는 정렬의 방법 중 하나이다.

배열의 가장 작은 요소부터 알맞은 자리로 swap 하며 정리한다.

 

2. 방법

첫 번째 자료를 두 번째 자료부터 마지막 자료까지 비교하며 가장 작은 요소를 배열의 제일 첫번째 자리에 위치시킨다.

(1회전이 끝나면 첫 번째 자리에는 배열 내 가장 작은 요소가 첫 번째 자리에 위치)

 

두 번째 자료를 세 번째 자료부터 마지막 자료까지 비교하며 가장 작은 요소를 배열의 두 번째 자리에 위치 시킨다.

(2회전이 끝나면 첫 번째 자리에는 배열 내 가장 작은 요소가, 두 번째 자리에는 배열 내 두 번째로 작은 요소가 위치)   

.

.

.

위와 같은 과정을 N번(자료의 개수) 반복한다.

 

3. 코드

위와 같은 내용을 코드로 구현하면 다음과 같다.

#include <stdio.h>

int main() {
	int i, j, min, index, temp;
	int array[10] = { 1,11, 55, 7, 8, 10, 63, 3, 97, 9 };

	
	for (i = 0; i < 10; i++) {
		//초기화를 위해 적당히 큰 수를 min에 저장해준다
		min = 99999;
		for (j = i; j < 10; j++) {
			//배열 내 정렬되지 않은 부분의 가장 작은 원소를 찾는 과정이다
			if (min > array[j]) {
				min = array[j];
				index = j;
			}
		}
		//해당 위치의 원소와 찾은 원소를 swap해준다
		temp = array[i];
		array[i] = array[index];
		array[index] = temp;
	}
	//선택 정렬의
	//O(N*N)

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

	return 0;
}