[알고리즘] 06-1. 기본적인 정렬 알고리즘(선택/삽입/버블)

정렬이란? 데이터를 특정한 기준에 따라서 순서대로 나열하는 것

선택 정렬  :  매번 '가장 작은 것을 선택'

배열에서 가장 작은 원소를 찾아 이 원소와 배열의 맨 앞에 있는 A[1]과 자리를 바꾼다. 그러면 방금 맨 앞자리로 옮긴 원소, 즉 가장 작은 원소는 자기 자리를 찾았으므로 이 원소는 정렬이 끝났다고 볼 수 있다. 따라서 이제 이 원소를 제외한 나머지 원소들로 같은 작업을 반복하면 된다.

선택정렬

package sorting;

public class sorting01 {
    public static void main(String args[]){
        int[] array = {7, 5, 9, 0, 3 ,1, 6, 2, 4, 8};

        for(int i=0; i<array.length;i++){
            int min_index = i;
            for(int j=i+1; j<array.length; j++){
                if(array[min_index] > array[j]){
                    min_index = j;
                }
            }
            int temp = array[i];
            array[i] = array[min_index];
            array[min_index] = temp;
        }

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

시간 복잡도 : O(N^2)

N-1만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.

또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다.

∴  N + (N-1) + (N-2) + ... + 2 ≒ (N^2 + N)/2 ≒ O(N^2)

선택 정렬은 데이터의 개수가 늘어날수록 비효율적임

다만, 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요가 있다!

 

 

버블 정렬  :  인접한 원소와 비교 후 교환

버블 정렬도 선택 정렬처럼 제일 작은 원소를 앞자리로 옮기는 작업을 반복하지만 가장 작은 수를 찾은 첫번째 원소와 바꾸는 선택 정렬과 달리 버블 정렬은 첫번째 원소부터 이웃한 수를 비교하면서 하나하나 바꾸어 나감 

 

버블 정렬

시간 복잡도 : O(N^2)

원소를 비교하여 가장 큰 원소를 맨 오른쪽으로 보내는 for에서 last가 n에서 2까지 1씩 감소하므로 총 순환하는 횟수는

∴  (N-1) + (N-2) + ... + 2 + 1 = N(N-1)/2 ≒ O(N^2)

 

 

삽입 정렬  :  특정한 데이터를 적절한 위치에 '삽입'

삽입 정렬은 선택 정렬과 달리 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씬 효율적임

선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다.

 

삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다

정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에 그 위치에 삽입된다는 점이 특징임
(삽입 정렬은 두 번째 데이터부터 시작한다. 왜냐하면 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문)

 

이미 정렬된 A[1...i-1]이 있다고 가정하자. A[i]가 A[i-1]보다 크면 A[i]는 A[1...i-1]에 있는 모든 원소보다 크므로 A[i]는 그냥 제자리에 두면 된다. 그렇지 않으면 A[i-1]부터 시작해서 왼쪽으로 차례로 훑으면서 A[i]가 들어갈 자리를 찾는다. A[i]가 들어가는 자리부터 시작해서 이후의 원소들은 한 칸씩 오른쪽으로 밀려난다.

2번 표 ) 9가 7보다 크면 7 이전의 모든 원소보다 큰 것이므로 그 자리에 삽입해주면 된다.

package sorting;

public class sorting02 {
    public static void main(String args[]){
        int[] array = {7, 5, 9, 0, 3 ,1, 6, 2, 4, 8};

        for(int i=1; i<array.length; i++){
            for(int j=i; j>0; j--){
                if(array[j] < array[j-1]){
                    int temp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = temp;
                }else{
                    break;
                }
            }
        }

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

시간 복잡도 : O(N^2)

실제 수행 시간을 테스트해보면 선택 정렬과 흡사하나,

삽입정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. (최선의 경우 O(N))

∴ 거의 정렬되어 있는 상태로 입력이 주어지는 문제다 ? 아묻따 삽입정렬.