발표 준비 - 선택정렬에 대하여

선택정렬이란? 

입력 배열 전체에서 최소값을 선택하여 배열의 0번 원소와 자리를 바꾸고, 그 다음에는 0번 원소를 제외한 나머지 원소에서 최소값을 선택하여 배열의 1번 원소와 자리를 바꾸는 형식이다. 이처럼 마지막까지 최소값을 비교하여 자리를 바꿔 최종적으로 오름차순 정렬을 마무리하는 것이 선택 정렬의 방식이다.

 

예를 들어, 6칸 짜리 배열이 있다고 치자. 그 배열에는 총 6개의 요소가 들어있다.

요소들은 5, 7, 3, 1, 9, 6 순으로 들어있다.

이 요소들을 선택 정렬을 이용해 정렬해볼 것이다.

 

먼저, 모든 인덱스를 훑으며 최소값을 찾아본다. 3번 인덱스에 들어있는 1이 최소값임을 확인할 수 있다.

그러므로 0번 인덱스에 들어있는 5와 3번 인덱스에 들어있는 1을 서로 자리바꿈한다.

그러면 0번 인덱스에는 1이, 3번 인덱스에는 5가 들어가 정렬 순서는 1, 7, 3, 5, 9, 6 이 된다.

 

이렇게 첫 번째 단계가 끝난 것. 

 

첫 번째 단계가 끝나면 두 번째 정렬 단계를 시작한다.

이때, 이미 0번 인덱스는 가장 작은 최소값을 찾아 정렬하였으므로 정렬된 인덱스인 0번은 제외하고 탐색을 시작한다.

1번 인덱스부터 4번 인덱스까지 최소값을 찾는다. 이 중 최소값은 3. 그러므로 1번 인덱스와 2번 인덱스의 위치를 바꾸면 2번째 정렬 단계가 끝이나고, 배열의 상태는 1, 3, 7, 5, 9, 6이 된다.

 

세 번째 단계부터도 동일하게 정렬된 요소인 1번 인덱스는 빼고 2번 ~5번 인덱스를 탐색하여 최소값을 찾아 위치를 바꾸면 된다.

 

선택 정렬 알고리즘을 코드로 작성하기 위해서 먼저, 한글로 한글코딩을 해보고, 그 뒤에 코드로 작성해보았다.

가장 작은 값을 포함하고 있는 인덱스를 저장할 변수를 선언하고, 이중 for문을 통해 배열을 순회하면서 더 작은 값이 있다면 해당 인덱스를 최소값 인덱스 변수에 대입하는 것이다. 
그리고 임시저장변수를 통해 두 인덱스의 값을 교환해준다. 이때, 교환로직을 사용한다.

 

알고리즘을 책으로는 봤어도, 선택 정렬 그림(개념)만 보고 직접 코드로 작성해보는 것은 처음이라 많이 헷갈렸다. 최소값 변수 선언해서 거기에 저장하고 교환하면 된다는 건 알겠는데 중첩 for문을 사용하려니 순서가 헷갈리고.. 그런식이다. 그리고 시간복잡도 계산하는 방법을 아직 제대로 이해하지 못해서 알고리즘 공부를 처음부터 다시 해야겠다는 생각이 들었다. n^2 등.. 아직 배워야 할 게 너무 많다 나는 알고리즘이 너무 어렵다ㅠㅠ