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

0. 목차

 

1. 선택정렬의 개념
2. 선택정렬의 과정 정리
3. 선택정렬의 시간복잡도
4. 선택정렬 코드

---

1. 선택정렬의 개념

 

 우리는 여러개의 데이터를 가지고 있을때, 탐색이 용이하려고, 또는 작업을 편리하게 하기 위해, 특정 조건을 기준으로 데이터들을 "정렬" 한다. 

 정렬을 하는 방법중 선택정렬이 있다. 말 그대로 선택을 하며 정렬을 하는 방법이다.

 오름차순으로 정렬을 하기위해선, 맨앞에서부터 제일 작은것, 그다음 작은것, 그다음 작은것 을 차례대로 나열을 해야하는데, 이를 정렬되지않은 배열을 탐색하며 최솟값을 찾은 뒤, 앞에다가 놓음으로써 정렬을 시키는 방법이다.

 

 예를들어 배열에 5 1 4 7 2 가 있고, 이것을 오름차순으로 정렬하고싶다고 해보자. 편의상 인덱스를 1부터 시작한다고 하자.

STEP 0 RESULT	인덱스	1	2	3	4	5
	데이터	5	1	4	7	2

 이때 먼저 정렬되지않은 배열 중 제일 작은 수를 탐색하며 찾아야한다. 그 결과로 2번 인덱스에있는 1이 최솟값이다.

최솟값을 찾았다면, 이 최솟값이 제일 앞에 와야하므로, 1번 인덱스와 SWAP을 해준다.

 

 

STEP 1 RESULT	인덱스	1	2	3	4	5
	데이터	1	5	4	7	2

 

 빨간색으로 칠한것은 정렬이 완료된 데이터라고 하자. 그럼 이제 정렬이 되지않은 배열은 2번~5번 인덱스에있는 데이터이다.

 정렬되지 않은 데이터중 최솟값을 탐색을하며 찾아보니 5번 인덱스에 있는 2가 최솟값이 된다. 그럼 이 2를 정렬되지않은 배열의 맨 앞인 2번 인덱스와 SWAP을 해준다.

 

STEP 2 RESULT	인덱스	1	2	3	4	5
	데이터	1	2	4	7	5

 위의 과정을 반복하면

STEP 3 RESULT	인덱스	1	2	3	4	5
	데이터	1	2	4	7	5

STEP 4 RESULT	인덱스	1	2	3	4	5
	데이터	1	2	4	5	7

STEP 5 RESULT	인덱스	1	2	3	4	5
	데이터	1	2	4	5	7

 사실 5번 페이즈는 할 필요가 없긴하다. 왜냐면 앞의 4개의 데이터가 오름차순으로 정렬이 된 후, 남은 한개이므로, 이것은 이미 정렬이 되어있다고 생각해도 되기 때문이다. 

 이렇게 총 5개의 단계(실제로는 4단계) 만에 정렬이 끝난다. 물론 코딩으로 하면

1) 정렬되지않은 데이터중, (최솟값/최댓값)을 교환할 자리를 선택하는 단계

2) 정렬되지않은 데이터를 탐색하며 (최솟값/최댓값)을 찾아내는 단계

3) 찾아낸 (최솟값/최댓값)을 1번단계에서 정한 자리의 데이터와 교환하는 단계

로 나누어져서 시간이 좀 걸린다.

---

2. 선택정렬 과정 정리

 

1. 정렬되지않은 데이터중, 맨 앞의 위치를 선정한다.
2. 정렬되지않은 데이터들을 탐색하며 ( 최솟값 / 최댓값 ) 을 찾는다.
3. 2번에서 찾은 인덱스의 값과, 1번에서 선정한 인덱스의 값을 SWAP한다.
4. 정렬되지 않은 데이터의 개수가 1개가 남을때까지 1~3을 반복한다.

---

3. 선택정렬 시간복잡도

 

 N개의 데이터를 정렬한다고 한다면,

(최댓값/최솟값)을 찾는 시간복잡도는 모든 STEP마다 정렬되지 않은 데이터를 모두 탐색해야하므로 O(N)이 된다.

(최댓값/최솟값)을 찾은 뒤 SWAP은 데이터의 값만 바꾸면 되는 일이므로 O(1)이 된다.

이 과정을 데이터가 1개가 남을때까지 해야하므로, 총 N-1번을 실행해야 한다.

따라서 선택정렬의 시간복잡도는 총 O(N²)이 된다.

---

4. 선택정렬 코드

 

#include<iostream>
using namespace std;

int main() {
	int arr[5] = { 5,1,4,7,2 };
	int size = 5;
	int temp;

	cout << "정렬 전 :\t";
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	cout << "\n";

	for (int i = 0; i <  size- 1; i++) {
		//먼저 최솟값과 최솟값의 인덱스를 초기화해준다.
		int minValue = arr[i];
		int minIndex = i;
		for (int j = i+1; j < size; j++) {
			//최솟값을 찾으면 값과 인덱스를 갱신해준다.
			if (minValue > arr[j]) {
				minValue = arr[j];
				minIndex = j;
			}
		}
		//최솟값과 정렬되지 않은 배열의 맨 앞부분을 swap
		temp = arr[i];
		arr[i] = arr[minIndex];
		arr[minIndex] = temp;

		//중간결과
		cout << i + 1 << "번째 결과 :\t";
		for (int j = 0; j < 5; j++) {
			cout << arr[j] << " ";
		}
		cout << "\n";
	}

	cout << "정렬 결과:\t";
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	cout << "\n";
	return 0;
}