[Algorithm] 선택정렬(Selection Sort)

선택정렬이란?

정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환함으로써 정렬하는 정렬 방법이다. 

 

선택 정렬의 과정

 

와 같은 원리로 오름차순 정렬이 된다.

1. 현재의 인덱스를 minIndex에 넣어준다.

2. 그 뒤의 인덱스에서 for문을 돌려 만약에 다른 인덱스의 값이 더 작다면 바꿔준다. 이렇게 마지막까지 돌면 minIndex의 인덱스 값은 가장 작은 값을 가진 인덱스일 것이다. 

마지막 인덱스는 이미 그 앞의 인덱스를 통해 교체가 되어 가장 큰 수일 것이므로 for문은 n-1번까지만 돌면 된다. 

 

구현 코드

import java.util.Scanner;

public class Main {
    private int[] solution(int n, int[] list) {
        for(int i = 0; i < n-1; i++) {
            int minIndex = i;
            for(int j = i+1; j < n; j++) {
                if(list[j] < list[minIndex])    minIndex = j;
            }
            if(minIndex != i) {
                int tmp = list[i];
                list[i] = list[minIndex];
                list[minIndex] = tmp;
            }
        }

        return list;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Main T = new Main();
        int n = scanner.nextInt();
        int[] list = new int[n];
        for(int i = 0; i < n; i++)  list[i] = scanner.nextInt();
        for(int i : T.solution(n, list))    System.out.print(i + " ");
    }
}

 

시간 복잡도

첫 번째 회전에서의 비교 횟수: 1 ~ (n - 1) = n-1

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

...

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

-> O(n^2)

References

https://ssdragon.tistory.com/110

선택정렬(Selection Sort)이란?