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

선택 정렬 : 해당 순서에 원소를 넣을 위치를 먼저 정한 후, 어떤 원소를 넣을지 선택하는 알고리즘

예시)  선생님이 학생들을 작은 키부터 큰 키 순서대로 세운다고 가정해보자.  1열로 서있는 학생들 중 가장 작은 학생을 뽑아 맨 앞으로 보내고, 남은 학생들 중 가장 작은 학생을 두번째로 보낸다. 이런 식으로 자리를 먼저 정하고 그 자리에 어떤 원소를 넣을지를 정하는 것이 선택 정렬이다. 

과정

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

 

 

Java Code - 오름차순 기준

void selectionSort(int[] arr) {
    int indexMin, temp;
    
    // 1. 원소를 넣을 위치(index) 선택
    for (int i = 0; i < arr.length-1; i++) {        
        indexMin = i; // 배열의 첫번째 값을 최소값으로 설정
        
        // 2. i+1번째 원소부터 index 의 값과 비교
        for (int j = i + 1; j < arr.length; j++) {  
        	// 3. 현재 선택한 자리에 있는 값보다 순회하고 있는 값이 작다면, index를 갱신
            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));
}

 

gif로 이해하는 선택정렬

 

시간복잡도와 공간복잡도

시간복잡도

데이터의 개수를 n개라고 했을 때, 

• 첫 번째 회전에서의 비교 횟수 :  1~n → n-1회
• 두 번째 회전에서의 비교 횟수 :  2~n → n-2회
• ....
• (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2

이와 같이 비교가 이루어지므로 시간 복잡도는 O(n^2) 이다.

공간 복잡도

선택 정렬은 주어진 배열 안에서 교환을 통해 정렬이 수행되므로 공간 복잡도가 O(n) 이다.

 

🔈 시간복잡도, 공간복잡도가 뭔지 모르겠다면 글 확인하기!

2020/02/11 - [기술면접] - [알고리즘] 계산복잡도 - 시간복잡도, 공간복잡도

[알고리즘] 계산복잡도 - 시간복잡도, 공간복잡도

 

 

장점과 단점

장점

• 거품정렬(Bubble Sort)와 마찬가지로 알고리즘이 단순하다.
• 비교횟수는 많지만 거품정렬에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료 상태에서 비교적 효율적이다.
• 거품정렬과 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식으로, 다른 메모리 공간을 필요로 하지 않는다. 이런 정렬을 제자리 정렬(in-place sorting)이라고 한다.

단점

• 시간 복잡도가 O(n^2) 으로 비효율적이다.
• 불안정 정렬(Unstable sort)이다.

 

자료출처 및 참고 사이트

https://github.com/GimunLee/tech-refrigerator/blob/master/Algorithm/%EC%84%A0%ED%83%9D%20%EC%A0%95%EB%A0%AC%20(Selection%20Sort).md#%EC%84%A0%ED%83%9D-%EC%A0%95%EB%A0%AC-selection-sort

https://jinhyy.tistory.com/9

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.htmlhttps://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC