알고리즘 - 2

일반적으로 알고리즘을 공부할 때 가장 먼저 풀어보는 문제는 ‘정렬(Sort)’문제이다. 왜냐하면 정렬만큼 알고리즘의 효율성 차이를 극명하게 보여주는 것이 없기 때문이다. 그래서 정렬 알고리즘을 통해 시간 복잡도의 개념을 알아가보자!

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성해보자

1 10 5 8 7 6 4 3 2 9

---

위와 같은 문제를 만났을 때 가장 직관적으로 푸는 방법은 선택 정렬이다. 사람은 대략적으로 전체 배열을 확인한 뒤에 1부터 10까지의 숫자를 써내려가겠지만, 컴퓨터에게는 그 과정을 구체적으로 명시해주지 않으면 제대로 동작하지 않는다. 따라서 알고리즘을 정의해주어야 한다.

가장 작은 것을 선택해서 제일 앞으로 보내면 어떨까?

문제의 숫자들을 정렬하기 위해서 가장 작은 것을 선택해서 제일 앞으로 보내는 방법을 생각해보았는데, 이러한 방법을 ‘선택 정렬’ 알고리즘이라고 한다. 효율적이진 않지만 가장 원시적이고 기초적인 방법 중 하나이다.

public class MainClass{
    public static void main(String args[]){

        int[] array = {3, 10, 5, 8, 7, 6, 4, 1, 2, 9};
        
        // 배열 안에 들어가는 수는 1 <= x <= 100
        for(int i = 0; i < array.length; i++){
            int min = 101;
            int temp = 0;
            int index = 0;
            for(int j = i; j < array.length; j++){
                if(min > array[j]){
                    min = array[j];
                    index = j;
                }
            }
            temp = array[i];
            array[i] = array[index];
            array[index] = temp;
        }

        for(int i = 0; i < array.length; i++){
            System.out.println(array[i]);
        }
    }
}

위와 같이 선택 정렬에 대해 소스 코드를 작성해보았는데, 여기에서 가장 중요한 것은 데이터의 갯수가 n개일 때 총 몇 번의 비교 연산을 해야 되는지이다.

1부터 n까지의 자연수의 합을 구하는 공식은 (n + 1) x n / 2 으로 표현할 수 있는데, 이를 쉽게 표기하기 위해 빅오표기법을 사용하면 상수항과 영향력 없는 항을 무시하기 때문에 O(N * N)으로 표현할 수 있다.

결과적으로 선택 정렬의 시간 복잡도는 O(N^2)이다.