선택 정렬 - Selection Sort

개념

---

선택 정렬은 버블 정렬과 유사한 알고리즘으로 해당 순서에 원소를 넣을 위치는

이미 정해져있고 어떤 원소를 넣을지 선택하는 알고리즘이다.

 

동작 과정

---

1. 주어진 배열 중에 최소값을 찾는다.

2. 찾은 최소 값을 맨 앞에 위치한 값과 교체한다.

3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

 

Code

---

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;
            }
        }
        // 4. swap(arr[indexMin], arr[i])
        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

...

마지막에서 두번째 회전 비교 횟수 : 2

마지막 회전 비교 횟수 : 1

따라서  (n-1) + (n-2) + ... + 2 + 1 -> n(n-1)/2

O(n^2) 의 시간 복잡도를 갖는다.

 

최선, 최악, 평균의 경우 모두 주어진 배열에서 최소 값을 찾기 위해 

전체 배열을 탐색 해야 하므로 O(n^2) 의 시간 복잡도를 갖는다.

 

장점

---

•  버블 정렬과 마찬가지로 알고리즘이 단순하다.
• 정렬을 위한 비교 횟수는 많지만 버블 정렬에 비해 실제 교환하는 횟수는 적기 때문에 많은 교환이 일어나는 자료 상태에서 비교적 효율적인 알고리즘이다.
  • 버블 정렬은 정렬 된 수를 제외한 모든 수에 대해 교환 연산이 발생해야 하지만 선택 정렬은 최솟값과 정렬 위치에 있는 수만 정렬 하면 되기 때문이다.
• 버블 정렬과 마찬가지로 제자리 정렬 알고리즘이기 때문에 다른 메모리 공간이 필요하지 않다.

 

단점

---

 시간의 복잡도가 O(n^2) 으로 비효율적이다.