[Algorithm] 선택정렬

선택정렬(Selection Sort)

맨 앞에서부터 제일 작은 원소를 배치하게 만들어나가는 알고리즘이다. 

정렬 알고리즘은 입력 인자로 정렬할 자료들이 있는 배열 시작 주소, 원소 개수, 비교 알고리즘이 필요하다.

1) 확정되지 않은 원소와 뒤쪽에 있는 원소를 비교하여, 최솟값을 발견할시 확정되지 않은 원소와 교환한다.

EX)

2,7,1,5 [i=0, j=1]

2,7,1,5 [i=0, j=2]

1,7,2,5 [교환] 

1,7,2,5 [i=0, j=3]

1,7,2,5 [i=1, j=2]

1,2,7,5 [교환]

.

.

.

예시 코드 1

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main() {
	int arr[10] = { 1,4,5,7,2,12,65,23,78,44 };
	int temp;
	for (int i = 0; i < 10 - 1; i++) {
		for (int j = i + 1; j < 10; j++) {
			if (arr[i] > arr[j]) {
				temp = arr[j];
				arr[j] = arr[i];
				arr[i] = temp;
			}
		}
	}
	for (int i = 0; i < 10; i++) {
		printf("[%d]", arr[i]);
	}
}

순차정렬의 시간 복잡도는 O(n²)