[정렬 알고리즘] 선택정렬

🏆 목차.

1. 선택정렬이란?
2. 선택정렬 코드
3. 결론

 

🛒 선택정렬이란?

 

정렬 중 가장 기본인 선택정렬은 간단하면서 비효율적인 정렬 알고리즘입니다.

하나의 숫자와 나머지 숫자를 비교해서 가장 작은 숫자를 앞으로 정렬하고 이것을 반복합니다.

그림으로 설명하자면 다음과 같습니다.

 

선택정렬 그림설명

 

위 설명과 같이 최솟값을 먼저 높은 값으로 지정하고 배열에 저장되어 있는 값을 차례대로 비교해서 최솟값에 저장합니다.

모든 비교가 끝나면 저장되어있는 최솟값을 가장 앞에 있는 숫자와 위치를 교체합니다.

 

이런 식으로 반복이 끝나면 1~10까지 정렬이 완료됩니다.

 

🎨 선택정렬 코드

 

#include <iostream>

using namespace std;


int main() {
	
	int n[10] = {4,5,3,7,8,1,9,2,6,1};
	int temp, minValue, index;
	for(int i = 0; i < 10;i++)
	{
		minValue = 9999;
		for(int j = i; j < 10;j++ ){
			if(n[j] <minValue)
			{
			minValue = n[j];
			index = j;
			}
		}
		temp = n[i];
		n[i] = n[index];
		n[index] = temp;
	}
	for(int i = 0 ; i <10 ; i++)
	{
		cout<<n[i]<<" ";	
	}	
}

 

2번의 반복문을 통해 최솟값을 비교합니다.

두번째 반복문에서 int j = i를 한 이유는 한 번의 반복문이 끝나면 한 번의 정렬이 끝났다는 뜻으로 두 번째 요소부터 다시 정렬을 해야 하기 때문입니다.

최솟값과 인덱스가 구해지면 반복문이 끝날 때

	temp = n[i];
	n[i] = n[index];
	n[index] = temp;

 

위 코드를 통해 요소를 서로 변경합니다.

 

🎯 결론

 

선택정렬은 두 번의 반복문으로 인해  시간복잡도는 O(n^2)로, 비효율적인 정렬 알고리즘입니다.