[ C언어 ] [제자리 정렬] 선택 정렬 (Selection Sort)에 대해 알아보기 -1

[C언어] 선택 정렬 (Selection Sort)에 대해서 -1

 

 

 

 

선택 정렬 (Selection Sort) 란?

 

 

 

선택 정렬은 제자리 정렬 알고리즘의 하나입니다.

나열된 것 중에 가장 작은 또는 가장 큰 것을 선택하여 앞 또는 끝으로 보내는 작업을 반복하여

최종적으로 크기 순서대로 정렬이 되는 방식입니다.(오름차순 , 내림차순)

 

 

 [무작위 배열의 수(데이터)가 선택 정렬되는 예시]

*알고리즘 순서*

1. 주어진 리스트 중에 최소 값을 찾는다.

2. 그 값을 맨 앞에 위치한 값과 교체한다.

3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

 

 

 

버블 정렬 (Bubble sort ) 실행 과정 살펴보기

 

 

* 7개의 로또 번호가 추첨 되었습니다*

버블 정렬을 이용해 작은수를 앞으로 큰수를 뒤로 보내는 과정을 설명합니다.

 

10

45

25

5

6

35

1

 

최소 혹은 최대 값을 찾아 정렬하는 방식이기 때문에,

최초 최소(혹은 최대)의 값을 가지는 위치(index)를 0번째 라고 정하고 시작합니다.

 

최소값을 기준으로 설명 하겠습니다.

그래서 indexMin이라는 배열의 위치 값을 담을 변수가 있다고 생각합니다.

 

indexMin = 0;

 

 

[1번째 반복 - 첫번째 비교]

현재 최소 값의 위치 indexMin = 0;

10

45

25

5

6

35

1

 

- 첫번째로  indexMin의 값10을 그 다음 수인 45와 비교합니다. ( 10 < 45 )

- 따라서 indexMin은 그대로 0 입니다. 10이 45보다 작기 때문

 

 

 

 

[1번째 반복 - 두번째 비교]

현재 최소 값의 위치 indexMin = 0;

10

45

25

5

6

35

1

 

- 두번째로 indexMin의 값인 10과 45의 다음 수인 25를 비교합니다. ( 10 < 25)

- 마찬가지로 indexMin은 그대로 0 입니다. 10이 25보다 작기 때문입니다.

 

 

 

[1번째 반복 - 세번째 비교]

현재 최소 값의 위치 indexMin = 3;

10

45

25

5

6

35

1

 

- 세번째로 indexMin의 값인 10과 25의 다음 수인 5를 비교합니다. ( 10 < 5 ) 거짓!

- 드디어 10보다 작은 수를 찾았습니다. 그럼 indexMin의 값이 바뀝니다 . indexMin = 3

- 배열의 위치 값(index)는 항상 0부터 시작하시는거 아시죠!?. 그렇기 때문에 5의 값을 가지는 배열의 index 값은 3입니다.

 

 

 

[1번째 반복 - 네번째 비교]

현재 최소 값의 위치 indexMin = 3; (값은 5)

10

45

25

5

6

35

1

 

- 네번째로 indexMin의 값인 5와 5의 다음 수인 6을 비교합니다. ( 5 < 6 )

- indexMin의 값은 그대로 3입니다....

 

 

[1번째 반복 - 다섯번째 비교]

현재 최소 값의 위치 indexMin = 3; (값은 5)

10

45

25

5

6

35

1

 

- 냉무

 

 

[1번째 반복 - 여섯번째 비교]

현재 최소 값의 위치 indexMin = 6; (값은 1)

10

45

25

5

6

35

1

 

- 여섯번째로 indexMin의 값 5와 35다음 수인 1을 비교합니다. ( 5 < 1 ) 거짓 !!

- 또 다시! 5보다 작은 수를 찾았습니다.

- 따라서, indexMin = 6으로 바뀌게 됩니다.

 

 

 

 

1번째 반복이 끝나면서 가장 작은 값은 1이고 , indexMin = 6 이라는 것을 알아냈습니다.

선택 정렬에서는 이 값을 맨 앞의 값과 교체합니다.

 

 

[ 초기 상태 ]

10

45

25

5

6

35

1

 

[ 1번째 반복의 결과 ]

1

45

25

5

6

35

10

 

 

 

 

값의 교체가 이루어진 후 다시 반복 잡업에 들어갑니다.

이번엔 두번째 반복을 실행하며, indexMin의 값은 1부터 시작합니다.

이유는 첫번째 위치에는 최소 값을 넣어 놨으니...

건들면 손해겠죠??

 

 

 

 

[2번째 반복 - 첫번째 비교]

현재 최소 값의 위치 indexMin = 1; (값은 45)

1

45

25

5

6

35

1

.

.

.

.

.

. 

 

이런식으로 반복을 쭈우우욱 하면

이처럼 최소값을 기준으로 정렬된 데이터를 볼 수 있습니다. ㅎㅎ

 

총 6번의 반복

반복 마다 실행되는 비교 반복...

2중 for문 입니다.!! 소스는 다음 포스트에서 작성하겠습니다.

 

[결과]

1

5

6

10

25

35

45

 

 

 

감사합니다. 공감 한번 부탁드립니다.

[ 다음 장 ]

[ C언어 ] 선택 정렬(Selection Sort) 오름차순 정렬 소스코드 배워보기 : http://popbox.tistory.com/9

[ C언어 ] 선택 정렬(Selection Sort) 내림차순 정렬 소스코드 배워보기 : http://popbox.tistory.com/10