[정렬] 버블 정렬, 선택 정렬, 삽입 정렬

버블 정렬

버블 정렬은 이웃한 항끼리 비교하는 연산을 "될 때까지" 반복하여 숫자 배열을 정렬하는 알고리즘이다.

 

예시

int[] arr = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1};
boolean isSorted;
do {
    isSorted = true;
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i + 1] < arr[i]) {
            int temp = arr[i + 1];
            arr[i + 1] = arr[i];
            arr[i] = temp;
            isSorted = false;
        }
    }
} while (!isSorted);

위 알고리즘은 위처럼 최악의 경우 O(N^2)의 시간복잡도를 보이므로, 구현은 쉬우나 성능이 좋지 못한 알고리즘이다.

 

위 알고리즘을 조금이나마 개선하면 다음과 같다.

int[] arr = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1};
for (int i = 0; i < arr.length - 1; i++) {
    for (int j = 0; j < arr.length - i; j++) {
        if (arr[i] > arr[i + 1]) {
            int temp = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = temp;
        }
    }
}

위와 같은 방식으로 하면 무한루프를 사용할 필요도 없고, isSorted라는 boolean 변수를 관리할 필요도 없다.

 

이를 보면 시간복잡도 계산이 더욱 쉽게 보인다. 최악의 경우 n개의 숫자를 n-1,n-2,n-3,...,1번씩 더 훑어야 하므로 시간복잡도가 O(N^2)로 되는 것이다.

 

선택 정렬

선택 정렬은 정렬된 인덱스까지를 기준으로 그 뒤를 한번씩 훑으면서 최소값을 찾아 정렬된 숫자 배열 바로 뒤에 삽입해주는 것을 반복하여 정렬하는 알고리즘이다.

 

예시

int[] arr = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1};
for (int i = 0; i < arr.length; i++) {
    int minVal = Integer.MAX_VALUE;
    int minIdx = 0;
    for (int j = i; j < arr.length; j++) {
        if (minVal > arr[j]) {
            minVal = arr[j];
            minIdx = j;
        }
    }
    arr[minIdx] = arr[i];
    arr[i] = minVal;
}

 

위 정렬도 보이는 바와 같이 시간복잡도가 O(N^2)로, 성능이 좋은 정렬 알고리즘은 아닌 것을 알 수 있다.

 

삽입 정렬

삽입 정렬은 패턴 자체는 선택 정렬과 유사하다. 앞에서부터 인덱스를 순회하면서 기준 인덱스 앞의 수를 정렬해가며, 기준 인덱스의 숫자가 앞의 배열 사이의 적절한 위치에 들어가게끔 삽입을 반복하는 알고리즘이다. 코드로 보면 이해가 쉽다.

 

예시

int[] arr = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1};
for (int i = 1; i < arr.length; i++) {
    int key = arr[i];
    int j = i-1;

    while (j >= 0 && arr[j] > key) {
        arr[j+1] = arr[j];
        j--;
    }
    arr[j+1] = key;
}

 정렬을 하고자 하는 숫자를 key로 저장해 둔 뒤에, 기준 인덱스 앞의 숫자들은 이미 정렬이 완료되었다 가정하므로 이를 순회하면서 key보다 큰지를 검사한다. 만약 큰 경우에는 한칸씩 뒤로 밀고, 작거나 같은 경우에는 그 숫자의 뒤가 key의 자리이므로 그 곳에 삽입하여 정렬을 마친다. 이 과정을 배열의 끝까지 반복하는 로직이다.

 

이는 n개의 원소에 대하여 정렬을 수행할 때, k번째 원소를 정렬하기 위해 최악의 경우 k-1개의 원소가 위치를 변경하는 로직을 수행해야 한다. 이 과정을 n번 해야 한다고 한다면 우리는 시그마 k(1 <= k <= n) 합공식에 의해 연산 횟수가 (n)(n-1)/2임을 알고 있다. 따라서 시간복잡도는 O(N^2)가 된다.