[알고리즘] 선택 정렬(Selection Sort) 의 개념 with c++

선택 정렬(Selection Sort)

선택 정렬은 제자리 정렬 알고리즘의 하나로 정렬되지 않은 데이터들 중에서 가장 작은 값을 추출하여 가장 맨 앞으로 정렬해나가는 알고리즘이다. 

 

1. 배열 중에 최솟값을 찾는다.

2. 최솟값을 맨 앞으로 정렬시킨다.(swap)

3. 나머지 값들도 동일한 방식으로 정렬해나간다.

 

알고리즘이 단순하고 사용할 수 있는 메모리가 제한적인 경우 사용하기에 용이하며,

구현이 간단하지만 비효율적인 방법인 알고리즘이다.

 

선택 정렬 알고리즘 예제

 

 

 

📌시간 복잡도

기준값과 비교값들 중 최솟값을 찾기 위해 이중 for문 필요
- 첫 번째 회전 비교 횟수 : 1 부터 (n-1) = n-1
- 두 번째 회전 비교 횟수 : 2 부터 (n-1) = n-2
               ...
=> 최솟값 찾기 : n-1, n-2, ..., 2, 1 번
T(n) = (n-1)+(n-2)+...+2+1=n(n-1)/2 = O(n^2)

 

 

📌선택 정렬 c++ 코드 구현

#include<stdio.h>

using namespace std;

int main(){

	//선택정렬- 오름차순 
	int a[100], n, idx, i, j, tmp;
	scanf("%d", &n);
    //n개의 숫자를 배열에 저장
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
	}
	
	for(i=0; i<n-1; i++){
		idx=i;
		//제일 작은 값 찾기
		for(j=i+1; j<n; j++){
			if(a[j]<a[idx]) idx=j;
		}
		//swap- 최솟값 앞으로 이동
		tmp=a[i];
		a[i]=a[idx];
		a[idx]=tmp;
	}
	
	return 0;	
}