[허언증/Algorithm] 선택정렬(Selection Sort)

안녕하세요! 허언증입니다.

선택정렬에 대해 공부 하도록 하겠습니다.

 

---

 

 

선택정렬(Selection Sort)? 

 

가장 작은 것을 앞으로 이동시키면 어떨까?

 

생각에서 만들어지게 된 알고리즘 입니다.

곧 바로 예시로 한 번 알아보도록 하겠습니다.

 

 

 

1, 5, 3, 10, 4, 7, 9, 2, 6, 8

(정렬되지 않은 숫자 1~10까지의 나열 된 상태입니다)

선택정렬의 방식으로 나열을 시작하면

 

 

 

첫 번째 자리에 있는 1을 기준으로 2~10번 자리까지 비교를 하고 

제일 작은 수와 자리를 바꿔줍니다.

1은 이미 제일 작은 수 이기도 하고 첫 번째자리에 있으니 변화가 없습니다.

 

 

이젠 첫 번째 자리를 제외하고 

두 번째 자리에 있는 5를 가지고 비교를 시작합니다.

1, 5, 3, 10, 4, 7, 9, 2, 6, 8

3~10번 자리까지 비교를 하면

2가 제일 작은 수이니 5와 2의 자리를 바꿔 줍니다.

1, 2, 3, 10, 4, 7, 9, 5, 6, 8

 

 

그 다음으로 세 번째 자리수인 3을 4~10번 자리수 마다 비교를 하고 

작은수가 있으면 교환 & 그렇지 않으면 유지를 합니다.

지금의 경우 3이 3번째로 작은수 이면서 제자리에 있기 때문에 

교환은 일어 나지 않고 그대로 유지하고 다음 단계로 넘어갑니다.

 

이젠 네 번째 자리 수인 10을 기준으로 5~10번째 자리 수와 비교를 합니다.

비교를 하면 이젠 감이 오셨을 텐데 4와 자리 바꿈이 일어납니다

1, 2, 3, 4, 10, 7, 9, 5, 6, 8

 

계속 이러한 과정을 통해 숫자를 정렬을 하게 됩니다.

 

 

 

---

 

이러한 과정을 소스코드로 작성하면

j=i 인 이유!!! 생각해보기!!!!

위와 같이 만들 수 있습니다. (C언어로 작성)

 

 

 

i,j = for문 인자

min = 비교 할 변수

temp = 서로 자리를 바꿀때 임시로 저장하는 변수

index = 비교를 다하고 최종적으로 작은수를 입력받는 변수

 

 

 

---

 

 

선택정렬의 시간 복잡도는

 

O(N^2)

 

 

 

 

 

 

 

* 참고 게시글 *

 

시간 복잡도 & 빅오표기법 - 시간복잡도&빅오표기법 공부하러 가자! Click!! Click!!