정렬(sort)

지난 글: [알고리즘] - 알고리즘이란?

 

정수를 순서대로 나열하는 알고리즘 : 정렬(sort)

 

작은 숫자를 찾아 교환하기 : 선택 정렬

알고리즘의 구체적인 예로 정렬(sort, 소트)을 알아보자. 이것은 아무렇게나 나열된 정수를 입력받아서 작은 것부터 차례로 재나열하는 것이다. 정수의 n이 적은 문제만 해결하는 것이라면 간단하겠지만, 알고리즘은 어떤 입력 값에 대해서도 대응할 수 있는 일반적인 방법을 기술해야 한다고 한다. 따라서 정수의 n이 아무리 커지더라고 같은 결과를 내어야 하는 것이다. 가장 먼저 떠오르는 방법은 입력 값 중 가장 작은 숫자를 찾고, 가장 왼쪽에 있는 숫자와 교환하는 것이다. 그러면 가장 왼쪽으로 옮겨진 숫자는 고정돼 이후로 움직이지 않는다. 그럼 다음은 남은 숫자 중 가장 작은 숫자를 찾아 왼쪽에서 두 번째에 있는 숫자와 교환하는 것이다. 이처럼 한 번의 동작이 시작해서 끝날 때까지를 '라운드(round)'라고 책에서는 설명한다. 일반적으로 k라운드에서는 남은 숫자 중에서 가장 작은 숫자를 찾아 왼쪽부터 k번째의 수와 교환한다. k라운드 종료 후, 왼쪽부터 k개만큼 작은 숫자 순으로 나열돼 있을 것이다. 이것을 숫자 개수만큼(n회) 반복하면 모든 숫자가 작은 순부터 나열된다.

 

선택 정렬을 사용하는 경우

만약 위처럼 n개의 정수를 입력받고 작은 숫자 순으로 나열하는 경우 1라운드에서 가장 작은 숫자를 찾기 위해 수열을 왼쪽부터 오른쪽까지 한 번 보므로 n개의 숫자를 확인한다. 다음은 2라운드에서 n - 1개의 수열 중에서 가장 작은 값을 찾으므로 n - 1개의 숫자를 확인한다. 이렇게 n라운드까지 계속하면 전체적으로는 수열을 확인 횟수가 n의 제곱과 같거나 보다 낮다. 이는 완전 탐색 알고리즘과 비교하면 굉장히 빠른 속도를 낼 수 있다.

 

참고서적: