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

출처 : https://s-satsangi.medium.com/insertion-sort-selection-sort-and-bubble-sort-5eb16d55a4de

선택 정렬이란?

선택 정렬은 정렬되지 않은 데이터들에 대해 `가장 작은 데이터를 찾아` 가장 앞의 데이터와 교환해나가는 방식이다. 최솟값의 자리를 변수에 저장해놓고 그 자리의 값과 나머지 값들을 비교하며 최종 최솟값을 찾는 반복문이 끝나면 그때 스왑해준다.
 

선택 정렬 장점과 단점

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

 

시간 복잡도

알고리즘	Best	Avg	Worst	Run-time(정수 60,000개) 단위: sec
삽입정렬	O(n)	O(n²)	O(n²)	7.438
선택정렬	O(n²)	O(n²)	O(n²)	10.842
버블정렬	O(n²)	O(n²)	O(n²)	22.894
셸 정렬	O(n)	O(n¹·⁵)	O(n²)	0.056
퀵 정렬	O(nlogn)	O(nlogn)	O(n²)	0.014
힙 정렬	O(nlogn)	O(nlogn)	O(nlogn)	0.034
병합 정렬	O(nlogn)	O(nlogn)	O(nlogn)	0.026

 

선택 정렬 알고리즘 구현

void selectionSort(int[] arr) {
    int indexMin, temp;

    for (int i = 0; i < arr.length - 1; i++) {
        indexMin = i; // 다음 자리로
        for (int j = i + 1; j < arr.length; j++) { // 정렬된 부분 제외하고 탐색
            if (arr[j] < arr[indexMin]) {
                indexMin = j; // 가장 작은 값의 인덱스 갱신
            }
        }
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
    }

    System.out.println(Arrays.toString(arr));
}

1. 주어진 배열 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

 

참고자료

[1] 위키백과 - 선택정렬
[2] ShootForTheMoon - [기술면접] 알고리즘 - 1/2 (6개 정렬 알고리즘)