선택 정렬 ( Selection Sort )이란?

안녕하세요~~ 

 

어제는 너무 피곤해서 포스팅을 못하고 일찍 잠이 들었어요..

 

오늘은 어제 충분히 잠을 잤으니 포스팅을 또 이어 가려 합니다.

 

오늘은 선택 정렬에 대해서 포스팅을 할 건데요, 

 

이 선택 정렬은 앞에서 포스팅 했던 버블 정렬이나 삽입 정렬처럼 쉽고 간단한 정렬 알고리즘입니다.

 

우선, 간단하게 선택 정렬 알고리즘의 수행 방법에 대해서 얘기하자면,

 

선택 정렬은 정렬되지 않은 데이터 셋을 처음부터 순차적으로 모든 데이터에 대해서 검사를 하면서 최소 데이터를 찾아냅니다.

 

그리고 그렇게 찾은 데이터와 첫 번째 인덱스에 있는 데이터를 서로 바꿔줍니다.

 

이렇게 함으로써 가장 좌측에는 가장 작은 수가 들어가겠죠.

 

두 번째 이터레이션에서 찾은 (전체 데이터 중에서) 두 번째로 작은 수는 두 번째 인덱스의 데이터와 위치를 바꾸게 됩니다.

 

이런 식으로 총 n - 1 번의 이터레이션을 통해서 모든 데이터를 정렬하게 됩니다.

 

무슨 말인지 이해가 잘 안되실 테니 그림으로 설명을 다시 해볼게요.

 

자, 아래와 같이 정렬되지 않은 데이터 셋이 있다고 가정해볼게요

 

 

 

이 데이터 셋의 모든 데이터에 대해서 루프를 돌면서 가장 작은 수를 찾아냅니다.

 

10이 가장 작은 수라는 것을 찾아내면 첫 번째 인덱스에 있는 숫자와 10의 위치를 바꿔줍니다.

 

이제 두 번째 인덱스의 33과 위치를 바꿀 가장 작은 수를 또 찾아냅니다. 

 

물론 이때는 10은 제외하고 검사를 합니다. 10은 이미 정렬된 수 이니까요.

그랬더니 이번에는 14가 아직 정렬되지 않은 수들 중에서 가장 작은 수이군요.

 

 

33과 14의 위치를 바꿔줍니다.

 

이제 세 번째 인덱스의 숫자인 27과 자리를 바꿀 숫자를 찾아야 겠네요.

 

이런 식으로 모든 숫자에 대해서 정렬을 하게 되는데 이것이 바로 선택 정렬인 것입니다.

 

 

자, 여기서 잘 눈여겨 보시면 좌측에는 항상 정렬된 데이터들이 나열되고, 

 

우측에는 정렬되지 않은 데이터들이 나열되어 있는 것을 알 수 있습니다.

 

즉, 추상적으로 정렬된 데이터 목록과 정렬되지 않은 데이터 목록이 존재하며, 

 

정렬 알고리즘이 시작할 때에는 정렬된 데이터 목록은 비어있는 상태이고, 

 

정렬되지 않은 데이터 목록은 전체 목록과 같다고 생각하시면 됩니다.

 

 

별로 어렵지 않죠?

 

선택 정렬에서의 핵심은 정렬되지 않은 비교 가능한 데이터 목록에서 어떤 기준에 의해서 특정 데이터를 하나 선택하여 순서대로 정렬하는 것입니다.

 

그러면 선택 정렬의 시간복잡도는 어떻게 될까요? 

 

처음에는 n개의 데이터를 모두 훑어봐야하고 그 다음에는 n-1, 또 그 다음에는 n-2개의 데이터를 훑어서 각 이터레이션 별로 가장 작은 수를 찾아내야 하니 O(n²)가 되겠네요.

 

 

이상으로 선택 정렬에 대한 포스팅을 마치도록 할게요.

 

잘못된 부분이 있거나 이해가 안되거나 하신다면 댓글 남겨주세요.

 

바로바로 수정하거나 답글 남겨드릴게요~ ^-^