[Algorithm] 선택 정렬(Selection Sort)

 

선택 정렬(Selection Sort)

가장 작은 것을 선택해서 제일 앞으로 보내고 자리를 바꾸는 정렬법(반복)

 

- 비효율적인 정렬 알고리즘

- 데이터의 개수가 조금만 많아지더라도 아주 많은 연산을 해야하기때문에 시간이 오래걸림

 

 

---

예제) 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.

1 10 5 8 7 6 4 3 2 9

 

- 코딩하기 전 정렬 해보기 -

1 10 5 8 7 6 4 3 2 9

1 2 5 8 7 6 4 3 10 9

1 2 3 8 7 6 4 5 10 9

1 2 3 4 7 6 8 5 10 9

1 2 3 4 5 6 8 7 10 9

1 2 3 4 5 6 7 8 10 9

1 2 3 4 5 6 7 8 9 10

 

#include <stdio.h>
int main(void){
	
	int i,j,min,index,temp;
	
	int array[10] = {1,10,5,8,7,6,4,3,2,9};

	for(i =0; i<10 ;i++){
		min=9999; //모든 원소들보다 큰 값
		
		for(j=i;j<10;j++){
			if(min>array[j]){
				min=array[j];
				index=j; // 해당 위치값 
			}
		} 
		
		// 스와핑 = 두 개의 원소값을 바꿔줌 
		temp=array[i];
		array[i]=array[index];
		array[index]=temp;
	}
	
	for(i=0;i<10;i++){
		printf("%d ",array[i]);
	}
	
	return 0;
}

 

---

선택 정렬의 시간 복잡도는 O(N^2) -> 최대한 피해야하는 시간 복잡도

 

선택 정렬은 얼마나 많은 시간을 잡아먹을까?

10 + 9 + 8 + ... + 2 + 1

-> 등차수열 

-> 10*(10+1)/2=55

-> 10개를 계산하기 위해 최소한 55번의 연산 필요 

-> 굉장히 비효율적인 알고리즘 정렬.....

 

=> N*(N+1)/2

=> N*N

 

 

빅오표기법 : 특정한 알고리즘의 수행시간 표기

O(N*N) = O(N^2)

 

 

---

출처 및 참고

https://blog.naver.com/ndb796/221226800661

https://m.blog.naver.com/PostView.nhn?blogId=justant&logNo=20203018572&proxyReferer=https:%2F%2Fwww.google.com%2F