[Java]선택정렬(Selection Sort)

Selection Sort [선택 정렬]

선택 정렬은 제자리 정렬 알고리즘의 하나로 입력 배열외의 다른 추가 메모리를 요구하지 않는 정렬방법이며 선택정렬은불안정 정렬이다. 배열에 앞에서부터 최솟값 또는 최댓값을 찾아 교환하는 방식의 알고리즘으로 선택 정렬의 과정은 이렇다.

1. 주어진 리스트 중에 최솟값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

public class 선택정렬 {
    public static void main(String[] args) {
        int[] arr = {7, 5, 2, 4, 3, 1, 9, 6, 0, 8};
        selectionSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    // 선택정렬 알고리즘
    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i+1; j < arr.length; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            int temp=arr[i];
            arr[i]=arr[min];
            arr[min]=temp;
        }
    }
}

- 장점

• 추가적인 메모리 소비가 거의 없다.

- 단점

• 시간 복잡도가 O(n^2)이다.
• 같은 값이 있는 경우에 위치가 변경될 수 있다.

- 시간복잡도

(n-1) + (n-2) + … + 2 + 1의 시간 복잡도를 갖지만 N^2의 이하로 나오므로 최악의 시간 복잡도는 O(n2)이다.

Bubble Sort와 같은 시간 복잡도를 갖지만 상태적으로 적기 때문에 조금 더 빠르긴 하나 좋은 정렬 알고리즘으로는 보기 힘들다.

 

- 불안정 정렬이란

{3,3,1,4}의 값이 있다고 하면 선택 정렬 시에 첫 반복에 {1,3,3,4}이 될 것이다. 이렇게 되면 처음 두 개의 3의 위치가 바뀌는데 이 이유 때문에 불안정한 정렬이라고 한다.

 

- 선택 정렬은 정렬 중에 기본이 되는 정렬방법이지만 성능상 좋지는 못하더라도 알아둬야 할 정렬방법이다.

예제로 풀어보면 될 문제이다.

https://www.acmicpc.net/problem/2752

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

참조

- https://st-lab.tistory.com/168