[Algorithm] C++ Selection Sort (선택정렬)

선택정렬

• 주어진 리스트에서 최솟값을 맨 앞으로 보내는 방법이다.
• 원소들을 큰순이나, 작은순으로 정렬하는 알고리즘 중 하나이다.

 

선택정렬 알고리즘

• Selection Sort는 Bubble Sort와 유사한 알고리즘이다.
• 해당 순서에 원소를 넣을 위치는 정해져있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.
• 진행 Process는 다음과 같다.

 

1. 주어진 배열 중 최소값을 찾는다.

2. 그 값을 맨 앞에 위치한 값과 교체한다.

3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

 

예시

출처 - https://runestone.academy/ns/books/published/pythonds/SortSearch/TheSelectionSort.html

 

선택정렬 특징

• Bubble Sort와 마찬가지로 알고리즘이 단순하다.
• 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환횟수가 적기에 많은 교환이 일어나야하는 자료에서는 비효율적이다.
• 내부 배열에서 교환하는 방식으로, 다른 메모리 공간을 필요로 하지않는다.

 

시간복잡도

• 비교 횟수

- 두개의 for루프의 실행 횟수

- 외부 루프 : (n - 1) 번

- 내부 루프 : n-1, n-2, n-3 .... 2, 1번 (최솟값 찾기)

 

• 교환 횟수

- 외부 루프의 실행 횟수와 동일.

- 한번 교환을 위해 3번의 이동이 필요하므로 3(n - 1)번

 

즉

• T(n) = (n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1) / 2 = O(n^2)

 

관련 알고리즘 문제

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

https://www.acmicpc.net/problem/23900

23900번: 알고리즘 수업 - 선택 정렬 6

 

Code

#include <iostream>

using namespace std;

int main() {

	int arr[] = { 26, 54, 93, 17, 77, 31, 44, 55, 20 };
	int arrSize = 9;

	for (int i = 0; i < arrSize - 1; i++) 
	{
	
		for (int j = i + 1; j > 0 && arr[j - 1] > arr[j]; j--) {
			int temp = arr[j - 1];
			arr[j - 1] = arr[j];
			arr[j] = temp;
		}
		for (int a = 0; a < arrSize; a++)
			cout << arr[a] << ' ';
		cout << '\n';
	}

}