선택 정렬

이번 글은 선택 정렬에 대해서 정리해보려고 한다.

선택 정렬이란?

• 선택 정렬은 정해진 순서에 들어갈 원소를 찾는 정렬이다.
• 첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 찾아서 교환한다.
• 두 번째 순서에는 두 번째 최솟값을 찾아서 교환한다.
• 이를 계속 반복해서 정렬을 진행하게 된다.
• 예를 들어 설명해보겠다. ( 9 6 7 3 5 )
  • 1회전
    • 9 6 7 3 5 → 3 6 7 9 5
  • 2회전
    • 3 6 7 9 5 → 3 5 7 9 6
  • 3회전
    • 3 5 7 9 6 → 3 5 6 9 7
  • 4회전
    • 3 5 6 9 7 → 3 5 6 7 9
• 위처럼 숫자 배열 안에서 가장 작은 숫자를 찾아서 현재 인덱스에 들어갈 숫자를 찾아서 교환하는 방식으로 이루어진다.
• 각 회전에 대한 설명은 다음과 같다.
  • 1회전에서는 첫 번째 자리에 가장 작은 숫자인 3을 찾아서 교환하게 된다.
  • 2회전에서는 두 번째 자리에 가장 작은 숫자인 5을 찾아서 교환하게 된다.
  • 3회전에서는 두 번째 자리에 가장 작은 숫자인 6을 찾아서 교환하게 된다.
  • 4회전에서는 두 번째 자리에 가장 작은 숫자인 7을 찾아서 교환하게 된다.
• 4회전 이후에 마무리하게 된다.

코드(Java)

for(int i = 0; i < number-1; i ++){
    int idx = i;
    for(int j = i; j < number; j ++){
        if(numArr[j] < numArr[idx]){
            idx = j;
        }
    }
    int tmp = numArr[i];
    numArr[i] = numArr[idx];
    numArr[idx] = tmp;
}

• 코드에서는 가장 작은 숫자의 인덱스를 기록하여 교환하는 방식으로 이루어진다.

시간복잡도

• 선택정렬의 시간복잡도는 for문을 통해 전체를 탐색하면서, 2중 for문을 통해 최솟값을 찾기 때문에 O(N^2)의 시간 복잡도를 가지고 있다.

참고 -

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html