기본 정렬 알고리즘 : 선택정렬, 삽입정렬, 버블정렬

정렬

: 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것.

 

단순하지만 비효율적인 방법의 정렬 알고리즘 : 선택정렬, 삽입정렬, 버블정렬

 

 

 

① 선택 정렬

 

▷ 아이디어

: 정렬된 리스트와 정렬 안 된 리스트를 가정함. 정렬 안 된 리스트에서 최소값이나 최대값을 선택해 한쪽으로 몰아넣음.

 

예시: 정렬 안 된 오른쪽(흰) 리스트의 최소값인 3을 선택하여 정렬된 왼쪽(파) 리스트 쪽으로 이동시킴

 

 

▷ 알고리즘 ;  오름차순 정렬 기준

 

1. 오른쪽 리스트에서 최소값의 인덱스 선택

2. 오른쪽 리스트의 첫번째 수의 값과 최소값을 교환

3. 왼쪽 리스트 크기 1 증가, 오른쪽 리스트 크기 1 감소

4. 오른쪽 리스트가 소진될 때까지 1~3 과정 반복

 

 

 

▷ 프로그램

void selection_sort(int list[], int n){
    int least, temp;
    for (int i = 0; i < n-1; i++) {
        least = i;
        for (int j = i+1; j < n; j++) {
            if (list[j] < list[least]) least = j; //최소값 인덱스 선택
            
        temp = list[i]; // 오른쪽 리스트의 첫번째 값과 교환
        list[i] = list[least];
        list[least] = temp;
        }
    }
}

 

 

 

▷ 시간 복잡도

: list[j] < list[least] 의 비교 연산이 이중 for문에 의해서 약 O(n²)의 시간 복잡도를 가지며, 최소값과 첫 번째 값을 교환하는 연산을 한 번 시행할 때마다 3번의 이동 연산이 시행되고 최악의 경우 교환 연산은 n-1번 시행되므로 총 3(n-1)의 이동연산이 시행되어 전체적으로 O(n²)의 시간복잡도 가짐.

 

 

 

 

② 삽입 정렬

 

▷ 아이디어

: 정렬되어 있는 앞부분에 새로운 레코드가 들어갈 올바른 위치를 찾아 삽입.

 

 

 

▷알고리즘

1. 첫 번째 원소의 경우에는 정렬되어 있는 앞 부분의 리스트가 없으므로 두 번째 원소부터 삽입할 원소로 선택.

2. 삽입할 원소의 바로 앞 원소부터 리스트 첫 번째 원소까지 비교 

3-1. 삽입할 원소가 더 작다면 앞에 있던 원소를 뒤로 한칸 이동시킴

3-2. 삽입할 원소가 더 크다면 비교한 원소의 뒤에 삽입

4. 마지막 원소까지 차례대로 삽입할 원소로 선택

 

 

 

▷ 프로그램

void insertion_sort(int list[], int n){
    int i, j, key;
    for(i=1; i<n; i++){
        key = list[i];
        for(j=i-1; j>=0 && list[j] > key; j--) //삽입할 원소가 더 작은 경우
            list[j+1] = list[j]; //비교한 원소를 한 칸 뒤로 이동
        list[j+1] = key; //삽입 연산 시행
    }
}

 

 

 

▷ 시간 복잡도

: 이미 정렬되어 있는 최선의 경우에는 비교연산만 시행되므로 O(n)의 시간 복잡도를 가지며, 역순으로 정렬되어 있는 최악의 경우에는 매 시행마다 이동연산이 뒤따르므로 이중 for문에 따라 비교 연산과 이동 연산 모두 O(n²)의 시간 복잡도를 가져 전체적으로 O(n²)의 시간 복잡도를 가짐.

 

 

 

 

③ (개선된) 버블 정렬

 

▷ 아이디어

: 인접한 2개끼리 비교하여 2개의 원소가 올바른 순서가 되도록 만듦.

 

 

 

▷ 알고리즘

1. 첫 번째 원소부터 마지막 원소까지 차례대로 인접한 1개의 원소와 대소 비교

2. 오른쪽 원소가 더 작다면 교환

3. 1~2의 과정(스캔)을 더 이상 원소 교환이 일어나지 않을 때까지 시행. (개선되기 전의 버블 정렬은 n번의 스캔 시행)

 

 

▷ 프로그램

void bubble_sort(int list[], int n){
    int i,j,temp;
    bool flag = true;
    while(j<n-1 && flag){ // 전 단계에 교환된 게 있으면 시행
        flag = false;
        for(i=n-1; i>j; i--){
            if(list[i] < list[i-1]){ // 오른쪽 값이 더 작다면 교환
                temp = list[i];
                list[i] = list[i-1];
                list[i-1] = temp;
                flag = true; // 교환이 이루어짐을 표시
            }
        j++;
    }
}
            

 

 

 

▷ 시간 복잡도

: 이미 정렬된 최선의 경우에는 첫 번째 반복에서 교환이 이루어지지 않으므로 n번의 비교만 시행되어 O(n)의 시간 복잡도를 가짐. 역순으로 정렬된 최악의 경우에는 이중 for문에 의해 비교 연산만 O(n²)의 시간 복잡도를 가지고, 교환 연산 역시 동일한 시간 복잡도를 가져 전체적으로 O(n²)의 시간 복잡도를 가짐. 개선되지 않은 버블 정렬은 최선, 평균, 최악의 경우 모두 비교 연산이 O(n²)의 시간 복잡도를 가지기 때문에 전체적으로 O(n²)의 시간 복잡도를 가짐.