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

선택 정렬(Selection Sort)이란?

주어진 리스트에서 최솟값을 찾아(선택) 맨 앞으로 보내는 방법으로

원소들을 작은 순, 혹은 큰 순으로 정렬하는 알고리즘 중 하나이다.

선택 정렬(Selection Sort)의 특징

1. 주어진 배열(입력 배열)이외에 다른 추가 메모리를 요구하지 않는 제자리 정렬(in-place sorting) 알고리즘이다.

  //주어진 배열만으로 정렬을 할 수 있다.

  //메모리가 제한적인 경우에 이점이 있다.

 

2. 코드가 직관적이며 정렬 알고리즘 중에 난이도가 쉬운 편이다.

 

3. 중복된 값은 입력 순서와 동일하게 유지된다는 보장을 할 수 없는 불안정 정렬(Unstable Sort)이다.

// 짜기 나름이다. 아래 코드는 stable하다.

 

4. 시간 복잡도는 최선, 평균, 최악의 경우 모두 O(N^2)로 비효율적인 정렬 방법이다.

 

선택 정렬(Selection Sort) 결과

주어진 배열을 오름차순 혹은 내림차순으로 정렬

 

선택 정렬(Selection Sort) 구현 방법

// i = 0~last

1. 주어진 리스트의 0+i번째 값부터 마지막 값 중에 최솟값을 찾는다.

2. 최솟값을 0+i번째 값과 교체한다.

 

1.

{3, 1, 5, 2, 4}

0번째 자리에 올 최솟값을 찾는다.

 

2.

{1, 3, 5, 2, 4}

0번째 자리의 값과 최솟값을 swap한다.

 

3.

{1, 3, 5, 2, 4}

1번째 자리에 올 최솟값을 찾는다.

 

4.

{1, 2, 5, 3, 4}

1번째 자리의 값과 최솟값을 swap한다.

 

5.

{1, 2, 5, 3, 4}

2번째 자리에 올 최솟값을 찾는다.

 

6.

{1, 2, 3, 5, 4}

2번째 자리의 값과 최솟값을 swap한다.

 

7.

{1, 2, 3, 5, 4}

3번째 자리에 올 최솟값을 찾는다.

 

8.

{1, 2, 3, 4, 5}

3번째 자리의 값과 최솟값을 swap한다.

 

9.

{1, 2, 3, 4, 5}

값이 하나 남았으니 마지막 4번째 자리에 그대로 두고 정렬을 종료한다.

 

코드(c++)

#include <iostream>
#define INF 987654321
using namespace std;

int main() {
	
	int arr[5] = { 3,1,5,2,4 };
	int arrSize = 5;
	for (int i = 0; i < arrSize; i++) {
		int min_num = INF; //초기값을 배열에서 나올 수 없는 큰 수로 초기화하여 배열 내의 초기값을 찾는다.
		int temp,min_index; 
		for (int j = i; j < arrSize; j++) {
			if (arr[j] < min_num) {
				min_num = arr[j]; //최소값을 저장한다.
				min_index = j; //찾은 최솟값의 인덱스를 저장한다.
			}
		}
		//현재 인덱스의 값을 최솟값으로 바꾸어준다.
		temp = arr[i]; 
		arr[i] = min_num;
		arr[min_index] = temp;
		for (int j = 0; j < arrSize; j++) {
			cout << arr[j] << ' ';
		}
		cout << '\n';
	}



	return 0;
}