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

버블 정렬

Idea

첫 번째 값과 두 번째 값을 비교하고, 두 번째 값과 세 번째 값을 비교하며 n-1 번째 값과 n 번째 값을 비교한다. 만약 n-1 값이 n 값 보다 크다면 서로 순서를 바꾼다. 이렇게 한 번 루프를 거치면 가장 큰 값이 오른쪽 끝에 위치하게 된다. 이 루프를 반복하여 정렬을 완료한다.

Code

public class Main {

    public static int n;
    public static int[] arr = new int[100];

    public static void bubbleSort() {
        boolean sorted;

        do {
            sorted = true;
            for(int i = 0; i < n - 1; i++)
                if(arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    sorted = false;
                }
        } while(!sorted);  // true 일 때만 정렬 완료
    }

    public static void main(String[] args) {
        /** 입력 **/
    }
}

sorted 값이 false 이면 아직 정렬이 완료되지 않았다는 의미이고, sorted값이 true로 if문을 지나지 않으면 정렬이 완료됬다는 의미이다.

Time Complexity

교환 여부를 확인하기 위해 전체 값을 한 바뀌 도는데 시간복잡도는 O(N)이 된다. 최악의 경우(역순의 경우)에는 한 번 순회할 때마다 숫자가 하나씩 제자리로 가기 때문에 N-1바퀴 돌게 된다. 따라서 O(N²)의 시간복잡도를 가지게 된다.

---

선택 정렬

Idea

선택 정렬은 주어진 값들 중 최소값을 맨 앞으로 가져와서 정렬하는 방법이다.
첫 번째 루프에서 전체 값들 중 가장 작은 값을 찾아서 해당 값을 맨 첫 번째에 배치한다. 두 번째 루프에서는 첫 번째 값을 제외한 나머지 값들 중 가장 작은 값을 찾아서 두 번째에 배치한다. 해당 과정을 두 번째, 세 번째, ..., n-1 번째 값을 제외하고 가장 작은 값을 정해진 위치에 배치할 때까지 반복한다.

Code

public class Main {

    public static int n;
    public static int[] arr = new int[n];

    public static void selectionSort() {
        for(int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for(int j = i + 1; j < n; j++) {
                if(arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }

            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    public static void main(String[] args) {
        /** 입력 **/
    }
}

Time Complexity

n-1, n-2, ..., 2, 1번의 고정된 횟수의 비교 연산이 필요하므로 n*(n-1)/2의 연산을 하여 O(N²)의 시간복잡도를 가지게 된다.

---

삽입 정렬

Idea

삽입 정렬은 선택한 원소의 앞에 있는 모든 원소가 정렬되어 있다는 가정 하에 현재 원소의 위치를 적절하게 집어넣는 정렬이다.

43kg, 63kg, 58kg, 52kg

위의 예시에서 앞의 두 원소가 정렬 범위에 포함된다고 한다면 이미 정렬이 완료된 상태이다. 여기서 정렬 범위를 1칸 늘려 58kg까지 포함한다면 58kg은 바로 앞의 63kg와 비교하여 더 작으므로 63kg의 앞으로 이동하게 되고 이번에는 43kg과 비교하여 더 크므로 해당 위치에 적절한 위치로 삽입된다.

43kg, 58kg, 63kg, |← 정렬 완료 | 52kg

이번에는 정렬 범위를 한 칸 늘려 52kg까지 포함하겠다. 52kg 앞의 값들은 정렬된 상태인 것을 확인할 수 있다. 52kg도 이전 과정과 동일한 방법으로 앞의 원소와 순서대로 비교하면 적절한 위치에 삽입되며 정렬이 완료된다.

43kg, 52kg, 58kg, 63kg |← 정렬 완료 |

 

Code

public class Main {
    
    public static int n;
    public static int[] arr = new int[100];

    public static void insertionSort() {
        for(int i = 1; i < n; i++) {
            int j = i - 1;
            int key = arr[i];  // 삽입해야 할 원소
            while(j >= 0 && arr[j] > key) {  // 앞에 있는 원소가 더 크면
                arr[j + 1] = arr[j];  // 앞의 원소 값을 한 칸 뒤로 이동
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        /** 입력 **/
    }
}

 

Time Complexity

n개의 원소에 대하여 값의 삽입이 진행된다. 2번째 원소의 경우 최대 1개의 원소를 이동하게 되고, 3번째 원소는 최대 2개의 원소를 이동하게 되며 n번째 원소는 최대 n-1개의 원소가 이동해야되므로 n*(n-1)/2의 연산을 하여 O(N^2)의 시간복잡도를 가지게 된다.