[알고리즘] 선택 정렬(selection sort) 쉽게 이해하기!

선택 정렬이란 ?

 

원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.

 

나는 이게 인간의 사고와 가장 유사한 알고리즘이라는 생각이 든다.

 

 

주어진 숫자 다섯가지를 오름차순으로 정렬해야 한다고 치자.

12, 21, 41, 5, 23  

숫자가 이렇게 주어져 있을 때 여러분들은 어떻게 정렬할 것인가?

 

아마 가장 작은 숫자를 찾고 있을 것이다.

 

가장 작은 숫자인 5를 찾아낸다면 그 다음은?

 

그 다음으로 작은 숫자인 12를 찾아낸다. 

 

위 과정을 반복하면 결국  5, 12, 21, 23, 41 임을 알아낼 수 있다. 

 

그리고 이 과정이 선택 정렬이다. 

 

 

컴퓨터와 한 가지 다른 것은, 우리는 새로운 공간(종이같은 곳)에

 

가장 작은 수부터 써내려갈 수 있지만

 

컴퓨터는 주어진 공간에서만 이를 처리해야하기 때문에 가장 작은 수를 찾은 뒤,

 

그 수를 맨 왼쪽에 있는 숫자와 바꾸어 정렬한다. (숫자를 선택한 뒤 정렬)

 

 

 

주황색 부분은 인간과 컴퓨터가 공통으로 거치는 사고라고 생각하면 되고,

양 옆의 기록 방식만 조금 다른 것이라 이해해도 된다. 

 

 

 

 

컴퓨터가 거쳐가는 과정을 먼저 생각해보면 아래와 같다.

step 1,2 -> step 1,2 -> step 1,2 -> step 1,2

 

먼저, arr[0]을 arr[1~4] 와 각각 비교한다.  (총 비교 횟수 : 4번) 

1,2 에선 여전히 12가 가장 작기 때문에 자리가 바뀌지 않고,

3에선 5가 12보다 더 작기 때문에 자리가 바뀔 것이다.

4에선 12와 23이 아닌, 5와 23을 비교한다. 5가 더 작으므로 자리는 바뀌지 않는다.

step3,4 -> step 3,4 ->step 3,4

 

step 3,4에서도 마찬가지로, arr[1]을 뒤의 arr[2,4]와 각각 비교해준다. (총 비교 횟수 : 3번) 

step 5,6 -> step 5,6

step 7,8

 

arr[2] 와 arr[3]도 같은 방식으로 비교를 해주고 숫자를 바꾸어준다면, 배열이 끝날 것이다. 

(☆arr[3]까지 마치면 arr [4] 에는 자동으로 가장 큰 수가 올 것이므로 arr[4]는 따로 비교하지 않아도 된다.

 ==이건 이해가 안 돼도 상관없다. "그럼 arr[4]를 뭐랑 비교할 건데?" 라는 질문 하나면 설명은 끝나니까.. )

 

그렇다면 우리는 step 1,2 는 4번, step 3,4는 3번, step 5,6은 2번 step 7,8은 1번 거친다는 걸 알 수 있다.

 

 

 

C언어로 선택 정렬을 구현할 때, 필요한 구문은 이중 for문이다. 구조가 아예 똑같다.

 

다음엔 선택 정렬을 C언어로 직접 구현하는 과정에 대해 설명할 것이다 :)

 

https://studywithsheep.tistory.com/30

[알고리즘] 선택 정렬 C언어 구현하기!