[Algorithm] 여러 가지 정렬1 - 간단하지만 느린 정렬들

배열을 정렬(오름차순)할 수 있는 여러 가지 방법에 대해서 알아보자.

 

1. Selection Sort

• 주어진 배열에서 가장 작은 데이터를 선택하여 앞으로 보내는 정렬
• 첫 번째 과정에서 가장 작은 데이터를 찾아 배열의 첫 번째 자리에 넣고, 두 번째 과정에서 그 다음 작은 데이터를 찾아 두 번째 자리에 넣고, ... n-1자리까지 반복한다.
• n개의 데이터에서 가장 작은 데이터를 찾고, n-1개의 데이터에서 가장 작은 데이터를 찾고, 그 다음은 n-2개, n-3개, ... 이렇게 이어지기 때문에 O(N^2)의 시간복잡도를 가진다.

public void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length - 1; j++) {
            if (arr[i] > arr[i]) {
                swap(arr[i], arr[j]);
            }
        }
    }
}

 

2. Bubble Sort

• 주어진 배열에서 서로 인접한 두 데이터의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하여 정렬
• 정렬 과정에서 데이터의 이동이 거품이 수면으로 올라오는 듯한 모습을 보여 Bubble Sort라는 이름이 붙여졌다고 한다.

public void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 1; j < arr.length - 1; j++) {
            if (arr[j - 1] > arr[j]) {
                swap(arr[j - 1], arr[j]);
            }
        }
    }
}

 

3. Insertion Sort

• 주어진 배열에서 현재 비교를 하고자 하는 데이터를 그 이전 데이터와 비교하여 자리를 교환하는 정렬
• 한마디로 해당 데이터가 위치할 곳을 찾고, 해당 위치에 데이터를 삽입하는 것이다.
• 위의 두 정렬과는 다르게, 최선의 경우 O(N)의 시간복잡도를 가질 수 있다. (하지만 보통 O(N^2)에 가깝다..)
  • 배열이 대부분 정렬이 되어있는 경우 삽입해야 할 횟수가 많지 않기 때문이다.

public void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int target = arr[i];
        int j = i - 1;
        while(j>=0 && target < arr[j]) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = target;
    }
}