[알고리즘 | 정렬] 선택 정렬 (Selection Sort) 정리

선택 정렬이란?

선택 정렬이란 정렬 알고리즘 중 하나로, 배열을 정렬하는 간단한 알고리즘이다.

선택 정렬 알고리즘은 가장 작은 원소를 찾아서 배열의 맨 앞에 놓고, 다음으로 작은 원소를 찾아서 두 번째 위치에 놓는 방식으로 정렬을 진행하며 이 과정을 배열 끝까지 반복하여 정렬된 배열을 생성한다.

선택 정렬의 동작 방식

https://www.lavivienpost.net/selection-sort-gif/

동작 과정 : 

1. 기준 원소 선택: 현재 위치의 원소를 기준으로 삼는다.
2. 가장 작은 원소 찾기: 기준 원소 이후의 배열에서 가장 작은 원소를 찾는다.
3. 교환: 찾은 가장 작은 원소를 현재 위치에 배치합니다.
4. 반복: 배열의 모든 위치에 대해 위 과정을 반복합니다.

 

동작 과정 설명: 

1. 현재 위치의 원소를 기준으로 삼는다.

 

2. 기준 원소 이후의 배열에서 가장 작은 원소를 찾는다.

 

3. 찾은 가장 작은 원소를 현재 위치에 배치한다.

 

4. 배열의 모든 위치에 대해 위 과정을 반복한다.

선택 정렬 구현

public static void selectSort(int[] arr) {
    // 배열의 모든 원소를 기준으로 삼아 반복
    for (int i = 0; i < arr.length; i++) {
        int index = i; // 현재 위치를 기준으로 삼음

        // 현재 위치 이후의 원소들 중에서 가장 작은 원소를 찾음
        for (int j = i + 1; j < arr.length; j++) {
            // 더 작은 원소를 발견하면 인덱스를 업데이트
            if (arr[index] > arr[j]) {
                index = j;
            }
        }

        // 현재 위치의 원소와 가장 작은 원소를 교환
        int temp = arr[i];
        arr[i] = arr[index];
        arr[index] = temp;
    }
    // 정렬된 배열 출력
    System.out.println(Arrays.toString(arr));
}

시간 복잡도 분석

• 외부 루프: 배열의 모든 원소를 순회하며 현재 위치를 기준으로 삼는다.
  • 이 루프는 배열의 크기 $n$ 만큼 반복된다.
  • 즉 $O(n)$의 시간 복잡도를 갖는다.
• 내부 루프: 현재 위치 이후의 원소를 순회하면서 가장 작은 원소를 찾는다.
  
  • $n = 5$ 일 때 :
    • 1회차 : $5 - 0 - 1 = 4$ 4번 반복한다.  
    • 2회차 : $5 - 1 - 1 = 3$ 3번 반복한다.
    • 3회차 : $5 - 2 - 1 = 2$ 2번 반복한다.
    • 4회차 : $5 - 3 - 1 = 1$ 1번 반복한다.
    • 5회차 : $5 - 4 - 1 = 0$ 탈출.

위의 반복횟수를 살펴보면 등차수열의 합 만큼 반복하게 된다는것을 알 수 있다. 때문에  $\frac{n*(n-1)}{2}$ 으로 표현할 수 있으며 빅오 표기법으로 $O(n^2)$로 표현할 수 있다. 선택 정렬은 최선, 평균, 최악의 경우 모두 같은 시간 복잡도를 가지며, 항상$O(n^2)$ 이다. 이는 선택 정렬이 비교 기반의 정렬 알고리즘이기 때문이다.

선택 정렬의 장단점

장점

1. 간단한 구현:
   • 선택 정렬은 구현이 간단하고 직관적이다.
2. 정렬 성질:
   • 안정 정렬은 아니지만, 비교 기반 정렬 알고리즘 중에서는 간단한 개념을 가지고 있다.

단점

1. 비효율적:
   • 선택 정렬의 시간 복잡도는 $O(n^2)$이다. 데이터가 많을 경우 비효율적이다.
2. 비교 횟수 많음:
   • 모든 원소를 비교하여 가장 작은 원소를 찾기 때문에 비교 횟수가 많아진다.
3. 불안정성:
   • 선택 정렬은 안정 정렬이 아니어서, 같은 값의 원소가 원래 순서를 유지하지 않을 수 있다.

결론

선택 정렬은 간단하고 이해하기 쉬운 정렬 알고리즘으로, 작은 데이터셋에서는 유용하게 사용할 수 있다. 그러나 데이터의 크기가 커질수록 비효율적이기 때문에 다른 정렬 알고리즘과 비교하여 선택할 필요가 있을거 같다.