선택 정렬(Selection Sort)

 

개념

선택 정렬은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다.

 

과정

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

 

예시

 

 

구현(Java)

void selectionSort(int[] arr) {
    int indexMin, temp;
    for (int i = 0; i < arr.length-1; i++) {        // 1. 위치 선택
        indexMin = i;
        for (int j = i + 1; j < arr.length; j++) {  // 2. i+1번째 값부터 선택한 위치(index)의 값과 비교
            if (arr[j] < arr[indexMin]) {           // 3. 비교값이 작다면
                indexMin = j;           	    // 해당 위치를 기억
            }
        }
        // 4. 현재인덱스 값을 최소값과 교체
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
  }
  System.out.println(Arrays.toString(arr));
}

 

시간복잡도

데이터의 개수가 n개일 때,

첫 회전에서의 비교횟수 : 1 ~ n-1 => n-1

두번째 회전에서의 비교횟수 : 2 ~ n-1 => n-2

.

.

.

(n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

 

즉, n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸린다.

 

비교

같은 시간 복잡도 O(n^2)를 가진 삽입 정렬(Insertion Sort), 버블 정렬(Bubble Sort)과 비교해보면

• 버블 정렬보다 교환 횟수가 적기에 항상 선택 정렬이 우수하다.
• 선택 정렬은 k번째 반복 후, k+1번째 요소를 찾기 위해 나머지 요소를 탐색하지만, 삽입 정렬은 필요한 만큼만 탐색하기에 삽입 정렬이 더 효율적으로 실행된다.

 

 

 

 

 

 

 

 

---

 

참고 

https://gyoogle.dev/blog/algorithm/Selection%20Sort.html

https://ssdragon.tistory.com/110