선택정렬(selection sort) - 선택정렬은 일반적으로 사람이 어떤 것을 크기 순서대로 정렬할 때 사용하는 방법과 유사한 방법입니다.
나열된 것 중에 가장 작은 또는 가장 큰 것을
선택하여 앞 또는 끝으로 보내는 작업을 반복하면
최종적으로 크기 순서대로 정렬이 되는 방식입니다.
다음 영상은 선택정렬에 대한 이해를 도와줍니다.
사람이 정렬을 할 경우 비슷한 과정을 거치지만 일반적인 사람의 경우 직관에 따라 몇몇 숫자의 위치를 정하고 그를 기준으로 수를 정렬하기 때문에 컴퓨터 입장에서 정렬하는 법을 위 영상을 보며 생각해볼 필요가 있습니다.
다음 그림은 선택정렬을 간략화한 그림입니다.
컴퓨터 입장에서 알고리즘이 실행될 때 두 수를 교환하는 과정 전에 더 많은 비교가 있습니다. 위 그림은 직관적으로 알기 쉽게 하기 위해 최종적인 교환 작업만 나타내었습니다.
그럼 컴퓨터 입장에서 선택정렬 알고리즘의 문제해결방법을 단계별로 생각해 보겠습니다.
1.정렬할 배열의 첫 번째 요소를 기준으로 잡고 다음 요소부터 차례대로 크기를 비교한다.
1-1. 비교 도중 기준이 되는 수보다 작은 수가 나타나면 그 수의 위치(첨자를) 임시변수에 기억해두고, 기준이 되는 수를 이 수로 바꾼다.
1-2. 바뀐 기준으로 계속 비교해 나간다.
2. 끝까지 비교가 끝나면 가장 작은 수를 이번 루프에서 비교를 한 수중 제일 첫 번째 요소와 교환을 한다.
3. 1번으로 돌아가서 비교를 하되, 앞선 루프의 비교 시작요소 다음요소부터 위 작업을 반복한다.(앞선 루프에서 0번째 요소부터 시작했으면 다음 루프는 1번째요소부터 비교시작 시작)
말로 설명을 해보니, 코드를 보는 것 보다 더 복잡해 보일거라는 생각이 듭니다. 사실 코드는 매우 간단합니다.(앞선 버블정렬과 매우 유사합니다.)
위에서 설명한 방법은 모든 것을 말해주지만 논리적으로 빈약합니다. 다음과 같은 아이디어를 덧붙이면 좀 더 논리적으로 설명할 수 있게 됩니다. 이 아이디어는 선택정렬 뿐 아니라 버블정렬의 경우에도 해당됩니다.
아이디어 : 주어진 수들은 애초에 정렬되지 않은 수이다.
정렬과정에서 정렬된 수와 정렬되지 않은 수로 나뉠 수 있다.
그럼 위 아이디어를 이용하여 문제해결을 해보겠습니다.
1. 정렬되지 않은 수를 차례대로 비교하면 가장 작은 수를 찾는다.
2. 가장 작은 수와 정렬되지 않은 수 목록 중 가장 첫 번째 수를 교환한다. 교환한 수(가장 작은 수)는 정렬된 수로 간주한다.
3. 정렬되지 않은 목록을 가지고 모든 수가 정렬될 때 까지 위 과정을 반복한다.
사실 위 아이디어가 없이도 위 정렬을 할 수 있고 코드도 짤 수 있습니다. 그러나 위 아이디어를 갖고 문제해결방법에 접근을 한다면 좀더 체계적이고 논리적인 해결이 가능합니다. 개인적으로 이런 작은 아이디어는 명확한 코드를 짜거나 이해하는 데 큰 도움은 준다고 생각되네요.
그럼 선택정렬 알고리즘 코드 예를 보겠습니다.
교환 횟수를 버블정렬과 비교해보면 상황에 따라 다르지만, i루프를 한번에 교환 횟수가 1번을 넘기지 않습니다. 버블정렬은 최악의 경우 비교할 때마다 교환할 수도 있습니다. 그래서 자료의 크기가 큰 경우 버블 정렬보다 선택정렬이 효율적일 수도 있습니다. 그래도 버블정렬과 선택정렬은 간단하면서 느린 정렬에 속합니다.
http://www.sorting-algorithms.com
위 사이트에서 각 정렬간에 상황에 따른 속도를 비교해 보시길 바랍니다.