정렬 알고리즘 - 순서도와 C언어로 알아 본 선택정렬(selection sort)

 
프로그래밍이나 알고리즘을 공부하는 사람들이 가장 먼저 만나게 되는 알고리즘 중에 하나가 바로 정렬 알고리즘 입니다. 그 중에서도 선택정렬은 가장 많이 사용되기도 하고 가장 먼저 배우기도 하는 정렬알고리즘 입니다. 지금부터 가장 간단한 정렬 알고리즘을 알아 보도록 하겠습니다.
우선 예로 3 , 5, 1, 7, 9, 2, 6 이렇게 7개의 숫자를 정렬해 보겠습니다.
아래 그림처럼 a[7]인 배열 함수에 숫자들이 차례대로 들어 있다고 가정합니다.
첫 번째 a[0]은 key 값이 됩니다. 여기서 key라고 정의한 것은 key가 있는 위치에 가장 작은 값을 넣을 것이라는 의미 입니다. a[0]을 a[1]부터 a[6]까지 차례대로 비교하면서 a[0]에 있는 값보다 작은 값을 만나면 둘의 위치를 바꾸어 줍니다. 그래서 아래 그림에서 3보다 작은 1을 만났을 때 1과 3의 위치가 바뀌게 된 것입니다. 이후에는 1보다 작은 수가 없기 때문에 변화가 없습니다.
두 번째 a[1]을 key로 설정하고 a[2]부터 a[6]까지의 값을 비교합니다. a[1]에는 5가 들어 있어서 a[2]에 있는 3이 작기때문에 먼저 5와 3의 위치를 바꾸어 줍니다. 다음에는 key 값이 3이 들어 있기 때문에 3보다 작은 2를 만나기 전에는 변화가 없다가 2를 만난 후 2와 3의 위치를 바꾸어 줍니다. 이런 방법으로 a[5]까지 key를 정하면서 a[6]까지 7개의 순자를 정렬하는 것입니다.

위의 모양을 순서도와 프로그래밍으로 바꾼 것이 아래의 그림입니다.
key라고 써 놓은 for문과 순환문이 배열 a[0]부터 a[5]까지를 차례대로 key값으로 정의 하여 진행하게 되어 있으며 변수 j 값은 key 값인 변수 i 의 뒤에 있는 배열들을 찾아가며 if문으로 비교를 하고 있습니다.
만약 a[i]값 보다 작은 것을 a[j]에서 찾으면 tmp라는 임시 변수를 사용하여 위치를 바꾸고 있는 것을 확인 할 수 있습니다.

이상으로 선택정렬의 기본 구성을 알아 보았습니다. 이 알고리즘에서는 key값을 두고 key 값과 나머지를 모두 비교하면서 찾는 방식을 사용했습니다.
다른 방식으로는 key값은 두고 나머지들만 서로 비교하여 가장 작은 값을 찾은 후 가장 작은 값과 key 값을 비교하여 key보다 작은면 바꾸도록 하는 방법이 있습니다.