[알고리즘] 정렬 - 선택정렬

1. 개념

배열의 원소를 순서대로 살피면서, 살피는 원소 아래에 있는 모든 원소를 확인해서 만약 더 작은 것이 있다면 현재 살피는 원소와 해당 원소를 바꾼다. 

2. 특징

• 제자리 정렬 알고리즘의 하나(입력 배열 이외에 추가 메모리를 요구하지 않음)

1) 장점

• 구현이 쉽다
• 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.

2) 단점

• 안정 정렬이 아니다(값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.)
• 정렬 규칙이 다수이거나 특정 순서를 유지해야 할 때 문제가 될 수 있다.
• 시간복잡도 상 효율이 좋지 않음

3) 단점 보완 방법

• 이중 선택 정렬
  • 한 번의 탐색에서 최솟값과 최댓값을 같이 찾는 방법이다. 탐색 횟수가 절반으로 줄어들게 된다.
• 탐색을 응용하여 개선
  • 한 번의 탐색 때 동일한 값이 있다면 함께 정렬하는 방법이다. 즉, 만약 최솟값을 찾았는데 그 값과 같은 값이 있다면 다음 번 탐색 때 최솟값으로 탐색될 것이기에 이 값도 탐색된 것으로 보고 미리 정렬한다. 같은 값이 많을수록 유용

3. 시간복잡도

1) 비교횟수

첫 번째 인덱스 원소를 선택했을 때 해당 원소와 비교하는 횟수 = n-1

두 번째 인덱스 원소 선택했을 때 해당 원소와 비교하는 횟수 = n-2

....

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

이 작업이 배열이 어떻게 정렬되어 왔던지 무조건 실행되어야 한다. O(n2)

 

2) 교환횟수

내부 for문에서 최대 n-1번의 교환 발생 가능

근데 temp에 하나 넣고, i에 하나 넣고, j에 하나 넣어서 총 3(n-1)이라고 할 수 있다. O(n)

 

따라서 총 시간복잡도는 O(n2) (최선, 최악, 평균 모두)

4. 코드

// 선택정렬 오름차순
public class HelloWorld{

     public static void main(String []args){
        int[] numbers = {3,4,2,6,1};
        
        for(int i = 0; i<numbers.length; i++){
            for(int j = i+1; j<numbers.length; j++){
                if(numbers[i] > numbers[j]){
                    int temp = numbers[i];
                    numbers[i] = numbers[j];
                    numbers[j] = temp;
                }
            }
        }
        
        for(int num : numbers){
            System.out.println(num);
        }
     }
}

// 선택정렬 내림차순

public class HelloWorld{

     public static void main(String []args){
        int[] numbers = {3,4,2,6,1};
        
        for(int i = 0; i<numbers.length; i++){
            for(int j = i+1; j<numbers.length; j++){
                if(numbers[i] < numbers[j]){
                    int temp = numbers[i];
                    numbers[i] = numbers[j];
                    numbers[j] = temp;
                }
            }
        }
        
        for(int num : numbers){
            System.out.println(num);
        }
     }
}

// 선택정렬 내림차순, 매번 교환하지 않고 최댓값 인덱스 구한 후 마지막에 교환하도록
for(int i = 0; i<nums.length; i++){
    int maxIndex = i;
    for(int j = i+1; j<nums.length; j++){
        if(nums[maxIndex] < nums[j]){
            maxIndex = j;
        }
    }
    if(nums[i] < nums[maxIndex]){
        int temp = nums[i];
        nums[i] = nums[maxIndex];
        nums[maxIndex] = temp;
    }
}

5. 언제 적합

교환이 많이 이루어지는 역순 정렬이 필요할 때

 

6. 관련 문제

백준 1427

GitHub - Lee-Min-Jung/coding_test_practice