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

선택 정렬(Selection Sort)

선택 정렬 애니메이션 

선택 정렬은 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다.

해당 순서 뒤에  주어진 리스트 중에 최솟값을 찾아 해당 해당 순서에 위치한 값과 교체한다.

애니메이션으로 선택 정렬 알고리즘을 쉽게 이해할 수 있다.

 

시간 복잡도 & 공간 복잡도

• 시간 복잡도 : O(n^2)
• 공간 복잡도 : O(n) 

 

장점

• 버블 정렬(bubble sort)과 마찬가지로 알고리즘이 단순하다.
• 정렬을 위한 비교 횟수는 많지만, 버블 정렬에 비해 실제로 교환하는 횟수가 적으므로 버블 정렬보다 항상 우수하다.
• 배열 안에서 교환하는 방식으로 다른 메모리 공간을 필요로 하지 않는다. 제자리 정렬이다.

 

단점

• 탐색 횟수가 많고 시간 복잡도가 크다. 
• 불안정 정렬이다. (불안정 정렬 : 정렬 후 원래의 순서가 유지되지 않는 정렬, 유지될 수 있지만 무조건이라는 보장을 할 수 없음)

 

 

코드(C++) - 백준 2750

//2750 선택정렬
#include<iostream>
#include<vector>

using namespace std;
int main() {
	//입출력 속도 향상
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//입력
	int N;
	cin >> N;
	int arr[1001];
	int num;
	for (int i = 0; i < N; i++) {
		cin >> num;
		arr[i] = num;
	} 

	for (int i = 0; i < N; i++) {
		int min = 1001;
		int index = 0;
		for (int j = i; j < N; j++) {
			if (min > arr[j]) {
				min = arr[j]; //가장 작은수
				index = j;
			}
		}

		//swap
		int temp = arr[i];
		arr[i] = min;
		arr[index] = temp;
		
	}

	//출력
	for (int i = 0; i < N; i++) {
		cout << arr[i] << "\n";
	}

	return 0;
}

 

선택 정렬 알고리즘

 

참고 - 위키 백과

https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

선택 정렬 - 위키백과, 우리 모두의 백과사전

블로그 - https://gyoogle.dev/blog/algorithm/Selection%20Sort.html