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

안녕하세요 지코딩입니다.

오늘은 선택정렬을 이용해서 오름차순으로 정렬하는 방법에 대해 알아보겠습니다.

 

오름차순으로 정렬하기 위해서는 정렬되지 않은 배열 인덱스 중 가장 작은 값을 선택해서 정렬되지 않은 부분의 맨 앞의 값과 자리를 바꾸면서 진행하면 됩니다. 

 

정렬되지 않은 부분은 하늘색, 정렬된 부분은 보라색으로 표시하겠습니다.

처음에는 배열의 모든 인덱스가 정렬되지 않은 상태입니다.

정렬되지 않은 인덱스 중 가장 작은 값을 찾고 정렬되지 않은 배열 부분의 맨 앞의 값과 자리를 바꿉니다.

 

위의 과정을 반복하면 다음과 같습니다.

마지막 남아있는 수는 전체 배열 중 가장 큰 수 이면서 정렬되지 않은 배열 인덱스 중 가장 작은 수 이기 때문에 따로 정렬을 하지 않아도 됩니다.

 

 

이제 전체 코드를 공유하겠습니다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

void selectionSort(int* arr, int len) {
	for (int i = 0; i < len - 1; i++) {
		int min = arr[i];
		int min_idx = i;
		for (int j = i + 1; j < len; j++) {
			if (min > arr[j]) {
				min = arr[j];
				min_idx = j;
			}
		}
		int temp = arr[i];
		arr[i] = min;
		arr[min_idx] = temp;
	}
}
int main() {
	int num[5] = { 4,2,1,5,3 };
	selectionSort(num, 5);
	
	for (int i = 0; i < 5; i++) {
		printf("%d\n", num[i]);
	}

	return 0;
}