C언어 SelectionSort에 대해 알아보자

Selection Sort란 한국어로 선택정렬이라고도 합니다.

처음에 가지고 있는 키와 남아있는 키를 비교해서 가장 작은 값을 첫번째에 놓고

바뀐 값은 가장 작은 값이 있던 위치로 보내버리는 정렬 방법입니다.

이렇게 정렬을 하게 될 경우, 빅오 표기법으로 효율을 나타내면 O(n^2)이 됩니다.

이는 지수함수 형태로 나타나기 때문에 그리 좋은 정렬 방법은 아니라고 볼 수 있는데요.

데이터의 양이 많지 않을 때에는 문제가 되지 않지만 양이 많아졌을 경우

급격하게 효율이 떨어지는 양상을 보이게 됩니다.

우선 코드를 보겠습니다.

처음에 최대 크기 100개의 array를 선언합니다. 

이후 사용자가 순차적으로 데이터를 원하는 개수만큼 집어넣습니다.

15번째 줄부터 정렬 알고리즘이 시작되는데요.

position은 현재 위치를 나타냅니다.

현재 위치를 잠시 저장해두고 남아있는 값들 중에서

position에 있는 값보다 작은 것이 있는지 탐색합니다.

탐색 결과 작은 값이 있다면 position은 그 값의 인덱스를 가리키고 있을 것입니다.

이후 22번째 줄에서 position의 값의 원래 i값하고 달라졌다면,

남아있는 값들 중에 현재 위치의 값보다 더 작은 값이 존재한다는 것을 의미하므로

둘의 값을 서로 바꿔줍니다.

이렇게 하번 한번의 루틴이 끝나게 되고

현재위치를 1 증가시켜서 같은 작업을 반복하게 됩니다.

이러한 과정을 배열의 끝까지 반복하게 되면

오름차순으로 정렬이 됩니다.

코드 설명에서 보셔서 아시겠지만 결국 처음부터 끝까지 

모두 탐색하고 swap하게 됩니다. 그렇기 때문에 효율이 O(n^2)이 나온다고 할 수 있는 것이죠.

이것은 제가 임의로 코드를 실행시켜 본 결과입니다.

간단하게 데이터를 5개만 넣어봤는데, 잘 작동이 되고 있는 것으로 보이네요.

효율성은 좋지 않지만 연습용으로 한번쯤 해보시면 좋을 것 같습니다