4. 정렬 (1) - 선택, 버블, 삽입 정렬

1. 선택 정렬

- 배열 A[0, ..., n]에서 가장 큰 원소를 찾아 배열의 맨 끝 원소 A[n-1]과 자리를 바꾼다

- 방금 맨 뒷자리로 옮긴 원소, 가장 큰 원소를 자기 자리를 찾았기 때문에 정렬이 끝날 때까지 자리를 지키면 된다

- 원소 A[n-1]을 관심 대상에서 제외하고 나머지 원소들 A[0, ..., n-2]를 대상으로 같은 작업을 반복하면 된다

-만약 위의 알고리즘에서 n=1이라면, 하나의 원소 A[0]이 입력이 되고, 이 하나의 요소로 정렬을 요구하면 아무 일도 하지 않고 그냥 끝난다.

 

-수행시간을 좌우하는 작업은 두 수를 비교하는 작업이다

-두 수를 비교하는 작업을 몇 번 하느냐가 선택 정렬의 점근적 수행 시간 척도가 된다.

 

-선택 정렬의 수행 시간은 모든 경우에 O(n^2) 이다.

(1) 모든 원소를 정렬하기 위해 돌리는 for 루프의 경우 n-1번 배열을 순환한다.

(2) 각 부분 배열에서 가장 큰 수를 찾는 작업의 시간은 부분배열의 크기와 비례한다

(3) 마지막에 두 수의 위치를 교환하는 작업은 단순히 두 수를 교환하는 것이기 때문에 상수 시간이 들게 된다

-따라서 수를 비교하는 총 횟수는 (n-1) + (n-2) + ... + 1 = n(n-1)/2

-즉 최고차항의 차수를 가지고 온 O(n^2)이 위 알고리즘의 시간 복잡도가 된다.

 

-선택 정렬 구현 코드

//Selection Sort 
#include<iostream>
using namespace std; 

//swap 함수
void Swap(int &a, int &b){    
	int tmp;    
    tmp = a;    
    a = b;    
    b = tmp;
}  //selection sort.

//오름차순으로 구현하겠습니다.
void SelectionSort(int *arr, int len){     
	int min_idx;    
    for(int i=0; i<len-1; i++){        
    	min_idx = i;         
        for(int j=i+1; j<len; j++){            
        	if(arr[min_idx] > arr[j]){                
            	min_idx = j;            
            }        
        }        
        
    Swap(arr[min_idx], arr[i]);    
    } 
}

int main(void){     
	int arr[5] = {3, 5, 1, 2, 4};    
    int len = 5;     
    for(int i=0; i<len; i++){        
    	cout << arr[i] << " ";    
    }    
    cout << endl;      
    SelectionSort(arr, len); //선택정렬 호출     
    for(int i=0; i<len; i++){        
    	cout << arr[i] << " ";    
    }     
    return 0;
}

 

 

 

2. 버블 정렬

- 버블정렬도 선택정렬처럼 제일 큰 원소를 끝으로 옮기기를 반복하나, 제일 큰 원소를 오른 쪽으로 옮기는 방식이 다르다

- 이웃하는 숫자를 비교하여 큰 수를 뒤로 이동시키는 과정을 반복하는 정렬 기법이다.

- 선택 정렬이 가장 큰 수를 찾은 다음 맨 오른쪽 수와 바꾸는 반면, 버블 정렬은 왼쪽부터 한 칸씩 이동하면서 이웃한 두 수를 비교하여 순서가 제대로 되어있지 않으면 바꾼다.

-위 부분 때문에 버블 정렬이 선택 정렬보다 느리다

- 버블 정렬도 선택 정렬처럼 두 수를 비교하는 작업이 시간을 좌우한다

 

 

3. 삽입 정렬

-삽입 정렬은 선택 정렬 / 버블 정렬과 정반대로 착상한 정렬이다.

-선택 정렬과 버블 정렬은 '정렬되지 않은' 배열의 크기를 n부터 시작하여 하나씩 줄이는데, 삽입 정렬은 '이미 정렬된 배열'의 크기를 1에서 시작하여 하나씩 늘린다

- 삽입 정렬의 핵심 작업은 이미 정렬되어있는 i개짜리 배열에 하나의 원소를 더하여 정렬된 i+1개짜리 배열을 만드는 과정이다

- 이미 정리가 되어있는 배열에 삽입하려는 원소는 삽입될 때 제 자리를 찾아 들어가게 된다

 

-앞에서부터 k개의 원소로 이루어진 부분 배열이 정렬된 상태고, 여기에 k+1번째 원소를 포함하여 정렬된 상태가 되도록 k+1번째 원소를 알맞은 위치에 삽입한다.

-원소가 삽입될 때 해당 원소보다 큰 원소들은 한 칸씩 오른쪽으로 시프트

 

-삽입 정렬의 수행 시간은, 새로운 원소를 변수에 차례대로 넣는 for loop, 그리고 제자리를 찾아 삽입되는 for loop을 제외하면 모두 상수 시간 작업들이기 때문에 이 두 루프와 관련한 순환 횟수가 시간을 좌우한다

-최악의 경우 수행 시간은 1+2+....+(n-1)이므로 즉, O(n^2)이다.

-보통의 경우 대략 A[0, ..., i-1}에서 평균적으로 절반 정도를 훑고 끝낼 것이기 때문에, 그러므로 전체 비교 횟수는 최악의 경우에 비해 절반 정도 될 것이나, 이 경우에도 상수배밖에 차이가 나지 않기 때문에 수행 시간은 여전히 O(n^2)이다.

 

-따라서 삽입 정렬은 시간 복잡도 O(n^2)에 해당하는 비효율적인 정렬 알고리즘 군에 속하지만 배열이 거의 정렬이 되어있는 상태로 입력되는 경우 가장 매력적인 알고리즘이 된다

-배열이 완전히 정렬이 된 채로 입력된다면 제자리를 찾아 삽입되는 for loop은 한 번도 수행되지 않기 때문에 이 for loop를 한 번 수행할 때마다 상수 시간이 들어 이 때의 시간 복잡도는 O(n)에 가깝다

-이러한 매력 덕분에 많은 지능적인 프로그래머들이 다른 정렬을 사용하는 경우에도 상황에 따라 가끔 삽입 정렬을 섞어서 쓴다.

-삽입 정렬이 거의 정렬되어 있을 때 빠른 특성을 이용하여, 사전 작업으로 거의 정렬된 형태에 가깝게 만든 다음 삽입 정렬을 수행하면 굉장히 빨라진다. -> 셸 정렬이 이러한 특성을 이용

 

-정리하면, 삽입 정렬은 최악의 경우와 평균적인 경우 O(n^2)의 시간복잡도를 가지고, 최선의 경우에는 O(n)의 시간복잡도를 가진다.

-삽입 정렬은 선택 정렬이나 버블 정렬보다는 빠르다. 

-이는 삽입 정렬이 재귀적 성격을 포함하고 있기 때문이다. 즉, 삽입 정렬은 재귀 알고리즘을 바탕으로 제작

-재귀 알고리즘의 귀납법 증명 ****** 얘 세연이랑 다시 검토

 

 

 

**쉽게 배우는 알고리즘 3판 (문병로) 책 참고