선택정렬 (selection sort)

가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘

선택정렬은 다음과 같은 순서로 이루어진다.

1. 주어진 리스트에서 최솟값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 정렬된 요소를 제외한 나머지 리스트를 같은 방법으로 교체한다.(반복)

선택정렬 - 예시

• 정렬되지 않은 위의 항목들을 이용하여 선택정렬을 한다.
  

• 최솟값인 1을 찾고, 첫 번째 위치한 인덱스의 값과 교환한다.
• 1 -> 3의 위치로, 3 -> 1의 위치로 이동
  

• 첫 번째 인덱스에 최솟값이 정해졌다. (정렬마침)
  

• 두 번째 위치 ~ 마지막 위치의 최솟값을 찾는다.
• 최솟값 2를 찾았다. 2는 두 번째 인덱스인 값과 교환한다.
• 2 -> 3의 위치로, 3 -> 2의 위치로 이동
  

• 두 번째 인덱스에 최솟값이 정해졌다. (정렬마침)
  

• 세 번째 위치 ~ 마지막 위치의 최솟값을 찾는다.
• 최솟값 3을 찾았다. 현재 정렬 위치와 최솟값 3의 위치가 동일하므로 그대로 정렬을 마친다.
  

• 세 번째 인덱스에 최솟값이 정해졌다. (정렬마침)
• 마지막 인덱스 정렬이 완료 될 때 까지 앞의 작업들을 계속 반복한다.
  

애니메이션

선택정렬 전체 과정 애니메이션이다.

선택정렬 - Java 코드

public class SelectionSortTest {

    // 자리이동
    static void swap(int[] arr, int idx1, int idx2) {
        int tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }

    // 선택정렬
    static void selectionSort(int[] arr) {

        // 마지막 자리는 자동 정렬 되므로 arr.length - 1
        for (int i = 0; i < arr.length - 1; i++) {

            // 현재 정렬할 인덱스를 최솟값으로 잡고 시작
            int min = i;

            // 정렬 대상 인덱스 다음 순서부터 배열 끝까지 비교하며 최솟값을 찾는다.
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }

            // 정렬 대상 인덱스 자리에 이미 최솟값이 있다면 넘어간다.
            if (i != min) {
                swap(arr, i, min);
            }

        }

    }

    public static void main(String[] args) {

        int[] arr = {3, 1, 2, 6, 7 , 5, 4};

        // 선택정렬
        selectionSort(arr);

        // 결과 출력
        System.out.println(Arrays.toString(arr));

    }
}

선택정렬 특징

• 장점
  • 구현이 쉽다.
  • 내림차순으로 정렬되어있는 요소를 오름차순으로 재정렬할 때 효율이 좋다.
  • 비교 횟수는 많지만, 실제로 교환하는 횟수는 적다. 교환이 많이 일어나는 자료상태라면 효율적이다.
    • 버블정렬과 비교했을 때, 똑같은 O(n2) 의 시간복잡도를 갖지만,
      시간을 측정해보면 버블정렬보다 시간이 짧게 소요됨.
• 단점
  • 서로 떨어져 있는 요소를 교환하기 때문에 안정적이지 않다.
    • 중복된 값이 2개 있을 때 요소의 순서가 바뀔 수 있음.
  • 이미 정렬된 상태에서 소수의 자료가 추가된 후 재정렬 하면 비효율적이다.
  • 시간복잡도 O(n2) 로 인하여 정렬 시간이 오래 걸림.

References

• 선택정렬-위키백과
• https://gmlwjd9405.github.io/2017/10/01/basic-concepts-of-development-algorithm.html
• https://yabmoons.tistory.com/250
• 보요 시바타, 『자료구조와 함께 배우는 알고리즘 입문』, 이지스퍼블리싱(2018)
• 모든 이미지는 직접 그림