[Algorithm] 정렬 - 선택 정렬 (Selection Sort)

선택 정렬(Selection Sort)이란?

가장 작은 값을 찾아 앞으로 차례로 옮기는 방식이다.

 

예)

1)  배열의 첫번째 값을 min값으로 설정한다.

 

2)  두번째 값부터 마지막 값까지 비교하여, min보다 작은 값이면 그 값을 min값으로 설정한다.

 

3)  min값을 가장 첫번째 값과 교체한다.

 

4)  배열의 두번째 값을 min값으로 설정한다.

 

5)  세번째 값부터 마지막 값까지 비교하여, min보다 작은 값이면 그 값을 min값으로 설정한다.

 

6)  두번째 값과 min값을 교체한다.

 

이 작업을 반복하게 되면 작은 값부터 차례로 정렬이 된다.

 

소스코드

#include <iostream>

using namespace std;

void selectionSort(int* arr, int len);

int main() {
	int N;
	cin >> N;

	int* arr = new int[N];
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	selectionSort(arr, N);

	for (int i = 0; i < N; i++) {
		cout << arr[i] << endl;
	}

	delete[] arr;

	return 0;
}

void selectionSort(int* arr, int len) {
	for (int i = 0; i < len; i++) {
		int min = arr[i];
		int min_idx = i;
		for (int j = i + 1; j < len; j++) {
			if (arr[j] < min) {
				min = arr[j];
				min_idx = j;
			}
		}

		int temp = arr[i];
		arr[i] = min;
		arr[min_idx] = temp;
	}
}

 

 

시간복잡도

평균의 경우 : O(n²)

최선의 경우 : O(n²)

최악의 경우 : O(n²)

 

거품 정렬과 마찬가지로, 데이터 정렬 여부와 상관없이 비교 횟수가 동일하다.

데이터 총 개수가 n개라고 하면, 비교 횟수는 아래와 같다.

(n-1) + (n-2) + ... + 2 + 1

= n(n-1) / 2

= O(n2)