무민이의 반반무많이

Selection Sort(선택 정렬) 본문

Algorithm/Theory

Selection Sort(선택 정렬)

M00min 2016.08.16 23:36

(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)


Selection Sort(선택 정렬)는 기준 하나를 선택해서, 그 값과 나머지 값 전부를 비교하여 올바른 순서로 되어있지 않으면, 두 값을 서로 교환하는 정렬 방식을 말한다. 아래 예제를 통해 자세히 알아보자.


1. 먼저 배열에 아래와 같이 5개의 값이 있다고 하자. 우리는 이 값을 오름차순으로 정렬하고자 한다.


2. 먼저 첫 번째 값을 기준으로 잡고, 나머지 값과 비교를 하여, 기준 값이 더 큰 경우 서로 값을 바꾸도록 하자. 배열의 첫 번째 값과 두 번째 값을 비교하여, 첫 번째 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 5가 4보다 크므로 자리가 바뀐다.


3. 배열의 첫 번째 값과 세 번째 값을 비교하여, 첫 번째 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 4가 1보다 크므로 자리가 바뀐다.


4. 배열의 첫 번째 값과 네 번째 값을 비교하여, 첫 번째 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 1이 3보다 작으므로 자리가 바뀌지 않는다.


5. 배열의 첫 번째 값과 다섯 번째 값을 비교하여, 첫 번째 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 1이 2보다 작으므로 자리가 바뀌지 않는다.


6. 배열의 첫 번째 값의 정렬이 완료되었다. 정렬 결과 가장 작은 값이 첫 번째 위치에 왔다.


7. 이번에는 배열의 두 번째 값을 기준으로 잡고, 나머지 값과 비교를 하여, 기준 값이 더 큰 경우 서로 값을 바꾸도록 하자. 배열의 두 번째 값과 세 번째 값을 비교하여, 두 번째 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 5가 4보다 크므로 자리가 바뀐다.


8. 배열의 두 번째 값과 네 번째 값을 비교하여, 두 번째 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 4가 3보다 크므로 자리가 바뀐다.


9. 배열의 두 번째 값과 다섯 번째 값을 비교하여, 두 번째 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 3이 2보다 크므로 자리가 바뀐다.


10. 배열의 두 번째 값의 정렬이 완료되었다. 정렬 결과 두 번째로 작은 값이 두 번째 위치에 왔다.


11. 이번에는 배열의 세 번째 값을 기준으로 잡고, 나머지 값과 비교를 하여, 기준 값이 더 큰 경우 서로 값을 바꾸도록 하자. 배열의 세 번째 값과 네 번째 값을 비교하여, 세 번째 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 5가 4보다 크므로 자리가 바뀐다.


12. 배열의 세 번째 값과 다섯 번째 값을 비교하여, 세 번째 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 4가 3보다 크므로 자리가 바뀐다.


13. 배열의 세 번째 값의 정렬이 완료되었다. 정렬 결과 세 번째로 작은 값이 세 번째 위치에 왔다.


14. 이번에는 배열의 네 번째 값을 기준으로 잡고, 나머지 값과 비교를 하여, 기준 값이 더 큰 경우 서로 값을 바꾸도록 하자. 배열의 네 번째 값과 다섯 번째 값을 비교하여, 네 번째 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 5가 4보다 크므로 자리가 바뀐다.


15. 배열의 네 번째 값의 정렬이 완료되었다. 정렬 결과 네 번째로 작은 값이 네 번째 위치에 왔다.


16. 배열의 다섯 번째 값의 정렬이 완료되었다. 정렬 결과 다섯 번째로 작은 값이 다섯 번째 위치에 왔다.


지금까지 Selection Sort(선택 정렬)의 오름차순 정렬에 대해 알아보았다. 하나의 기준을 선택하여 기준 값과 나머지 값을 비교한다고 하여 Selection Sort(선택 정렬)라고 불린다. 내림차순 정렬시에는 기준 값과 나머지 값을 비교하여, 기준 값이 더 작은 경우 자리를 바꿔서 큰 수가 앞에 위치하도록 정렬을 해나가면 된다.


<오름차순 정렬>


<내림차순 정렬>

'Algorithm > Theory' 카테고리의 다른 글

Insertion Sort(삽입 정렬)  (0) 2016.08.16
Selection Sort(선택 정렬)  (0) 2016.08.16
Bubble Sort (버블 정렬)  (0) 2016.08.16
0 Comments
댓글쓰기 폼