기초적인 정렬알고리즘(1) - 선택정렬

 우리가 '물건을 구매할때 가격순으로 보는것'이나 '사전에서 찾고자하는 단어를 찾을 때' 의 상황들처럼 수 많은 정보들 중에서 원하는 정보만 뽑아 볼 수 있다.

 이처럼 정보들을 나열하는것을 정렬(sort)이라고 하는데, 다양한 종류의 정렬중 선택정렬에 대해서 알아가보자.

 선택정렬(Selection Sort) - 오름차순 기준

선택정렬은 가장 큰 값을 뒤로보내고, 그다음 두번째 큰값을 뒤로보내는 식으로 쌓여가는 형태로 정렬이되는 것이다. 먼저, 앞에서부터 n(데이터크기)까지 비교를 통해 가장 큰 값(MAX)를 찾은 뒤, 그 큰 원소가 위치하는 자리와 맨 뒷 자리 원소의 자리를 바꾸어주면 된다. 그리고 그 다음부터 1부터 n-1에서 MAX값을 구해서 n-1번째 위치를 교환을 통해서

정렬이 이루어진다.

ex.  3 2 6 3 4 3 1 이 있는경우 가장 큰 원소는 6이다. 6을 맨 뒤 1이 위치한 자리와 바꾸면

3 2 1 3 4 3 6 가 된다. 이게 첫번째 과정이다.  이 과정들을 반복해보면..

3 2 1 3 3 4 6  - 2회 

3 2 1 3 3 4 6  - 3회

3 2 1 3 3 4 6  - 4회

1 2 3 3 3 4 6  - 5회

1 2 3 3 3 4 6  - 6회 

위 과정들을 통해서 정렬이 된다는것을 알 수 있다. 여기서 우리는 수행시간에 대해서 알아보자. 먼저 1부터 6까지 MAX값을 구하는 방법 즉, 비교는 n개의 크기에서 n-1회 그다음 

n-2 이렇게 계속 작아지므로 n-1번의 비교가 필요하다. 이것은 크기에 비례가 된다.

그리고 맨뒤에 보내지는 과정들 맨 끝 n부터 2가 될 때까지 반복한다. 그러므로 수를 비교하는 총 횟수는 (n-1)+(n-2)+... +2+1=n(n-1)/2, 즉Theta(n제곱)의 수행시간이 걸릴것이다.

수행시간에서 수학적으로 접근하기보다는 어느 상황에서의 수행시간에 영향을 미치는지에 대해서 알아두길 바란다. 

여기서는 수를 비교하는 횟수가 전체 시간을 좌우한다.

알고리즘을 살펴보면,

▶실행결과