흔히 쓰는 O(n²) 정렬 (삽입,선택,버블) 요약

일반적으로 쓰는 정렬 알고리즘도 참 많은게 있다.

 

그중, 흔히 말하는 시간 복잡도 O(n²) 정렬들은 구현도 간단하여 자주 사용하는 편인데, 정작 각 정렬에 대한 차이를 명확하게 답변하지 못할때가 종종 있어서 복습 겸 정리를 좀 할까 싶다.

 

 

 

1. 해당 문서의 예시 코드는 C/C++ 기반으로 작성되었습니다.

2. 모든 설명은 오름차순을 기준으로 합니다.

---

삽입 정렬

---

삽입정렬은 "맨 처음부터 진행하면서 내 위치일 것 같은곳으로 삽입" 하는 정렬이다.

예를들어, [5 3 2 1 4] 의 순서로 자료가 있다고 하면

 

시작 - [5 3 2 1 4]

1회차 - [5 3 2 1 4] --> [3 5 2 1 4]

2회차 - [3 5 2 1 4] --> [2 3 5 1 4]

3회차 - [2 3 5 1 4] --> [1 2 3 5 4]

4회차 - [1 2 3 5 4] --> [1 2 3 4 5]

종료 - [1 2 3 4 5]

 

의 방식으로 정렬이 이루어진다.

 

삽입 정렬의 특징이자 문제점이, "삽입" 방식으로 이루어지다보니 중간에 데이터를 삽입하면 뒤로 밀어버려야 한다는 특징이 있는데..

 

코드를 보면서 설명하도록 하겠다.

 

void Insertion_Sort(int *data, int n)	//data = int 동적배열, n = 배열 길이
{
	int i, j;
    int temp;		//임시 기억용 변수
    
    for (i = 1 ; i < n ; i++)  //2번째 원소부터 검사하므로 index가 1부터 시작함.
    {
    	j = i;
    	temp = data[i];
        
        while (--j >= 0 && data[j] > temp)	//검사중인 원소부터
        {					//0번 인덱스 원소까지
        	data[j+1] = data[j];		//한칸씩 뒤로 당김
        }					//* while문 최초 실행때 [j+1] 원소는 temp에 들어간 원소와 같다.
        data[j+1] = temp;			// j = i = 1일때, j + 1은 0이 될 수 있다.
    }
}

 

흐름은 다음과 같다.

 

시작을 i 번 원소부터 했을때 

1. [i - 1] 원소가 [i] 보다 클때 = i 원소의 값을 [i - 1]로 바꾼다. 

2. [i - 1] 원소가 [i] 보다 작을때 = 값을 바꾸지 않고 종료한다.

3. while 루프 종료시 = 최종 위치에 임시값을 삽입한다. (1, 2번을 수행하면서 생긴 "중복 값" (=빈 자리) 에 삽입)

 

 

여기 나오는 모든 정렬들이 그렇겠지만, 삽입정렬도 N번째 값 정렬 시 N-1만큼의 순회를 돌아야 하므로,
시간 복잡도는 O (N(N-1)) = O(n² - n) = O(n²) 로 수렴한다.

 

구현이 간단하고, 나름 빠른 편 (선택 정렬과 버블정렬은 순수하게 O(n²) 의 시간 복잡도를 가진다) 이나, 배열이 길어질수록 효율이 떨어진다는 단점이 존재한다.

 

이미 정렬이 되어있는 경우에는 비교를 제외한 추가적인 연산이 필요 없으므로 최선의 케이스가 나오며, 이때 시간 복잡도는 O(n) 이 나온다.

 

 

 

 

 

 

선택 정렬

---

선택 정렬은 "리스트의 최소값부터 정렬하는" 알고리즘이다.

 

삽입정렬과 헷깔릴 수 있는데, 선택정렬은 N번째 자료를 정렬시에 N-1번까지는 이미 정렬이 완전히 끝난 상태라는것이 가장 큰 차이. (위에도 언급했지만 삽입정렬은 N번째 자료 정렬시 정렬이 끝난다는 보장을 할 수 없다.)

 

선택 정렬은 다음과 같이 작동한다.

 

시작 - [5 3 2 1 4]

1회차 - [5 3 2 1 4] --> [1 3 2 5 4]

2회차 - [1 3 2 5 4] --> [1 2 3 5 4]

3회차 - [1 2 3 5 4] --> [1 2 3 5 4]  // 이미 순서가 맞으므로 추가 정렬 X

4회차 - [1 2 3 5 4] --> [1 2 3 4 5]

종료 - [1 2 3 4 5]

 

 

선택 정렬은 N번째 자료 정렬시 그 앞까지 (N-1까지)는 정렬이 완료되었다는 보장을 할 수 있는데, 현재 값이 "어느 위치인지" 알기 위해서 결국 모든 자료를 검사해야한다는 불상사가 발생한다.

 

이게 무슨소리냐면... 시간 복잡도가 어떤 상황에서든 O(n²) 라는 것이다.

삽입 정렬이나 버블정렬의 경우에는, 비교하는 대상과 본인이 정렬이 되어있다면 추가적인 연산을 하지 않는데 선택정렬은 그런거 모르겠고 이미 끝난 정렬도 함수 안에서 정렬을 수행한다는 뜻이다.

 

선택정렬은 "다음 최소값"이 어떤 값인지 알아야 하는 문제가 있어, 삽입정렬이나 버블정렬보다는 로직이 조금 복잡한 편이다.

 

void SelectionSort(int *data, int n)
{
	int i, j, indexMin, temp;		//최소값 인덱스와 임시값 변수 2종이 추가로 필요함.
    
    for (i = 0 ; i < n-1 ; i++)
    {
    	indexMin = i;
        
        for (j = i+1 ; j < n ; j++)
        {
        	//해당 for문은 정렬되지 않은 구역에서 "최소값"을 찾는 로직이다.
            
        	if (data[j] < data[indexMin])
            {
            	indexMin = j;				
            }
        }
        temp = data[indexMin];	//찾아낸 최소값을 temp에 저장.
        data [indexMin] = data[i];	//위치 교환
        data[i] = temp;	//temp값을 위치에 저장
    }    
}

 

 

흐름은 다음과 같다.

 

시작을 i 번 원소부터 했을때 

1. i번 부터 N번까지 데이터 중 최소값을 찾는다.

2. 최소값이 발견되면 해당 값의 인덱스를 기록한다.

3. 최소값을 임시 변수에 저장한다.

4. i번 값과 최소값이 위치한 인덱스의 값을 교체한다.

5. i번 값에 임시 변수에 저장된 값을 집어넣는다.

 

해당 과정은 값이 이미 정렬이 되어있던, 아니던 상관없이 작동한다. 그러니까 시간 복잡도가 그모양이지

 

 

 

버블 정렬

---

참 자주 얘기하게 되는 정렬 중 하나인 버블 정렬이다.

 

버블 정렬도 길게 설명하면 어지러운 얘기가 많지만, 요약하면 단 한가지로 요약 가능하다.

 

N번째와 N+1번째가 정렬되어 있지 않으면 교체, 정렬 되어있으면 넘어간다.

 

이 문장이 바로 버블 정렬의 본질이라고도 볼 수 있겠다..

 

 

버블 정렬은 다음과 같이 작동한다.

 

시작 - [5 3 2 1 4]

1회차 - [5 3 2 1 4] -> [3 5 2 1 4] -> [3 2 5 1 4] -> [3 2 1 5 4] -> [3 2 1 4 5]

2회차 - [3 2 1 4 5] -> [2 3 1 4 5] -> [2 1 3 4 5] -> [2 1 3 4 5] // 3이 4보다 작으므로 종료

3회차 - [2 1 3 4 5] -> [1 2 3 4 5] -> [1 2 3 4 5] // 2가 3보다 작으므로 종료

종료 - [1 2 3 4 5]

 

void BubbleSort (int *data, int n)
{
	int i, j, temp;
    for (i = 0 ; i < n-1 ; i++)
    {
    	for (j = 0 ; j < n-1-i ; j++)		//이미 정렬된 후위 i번은 확인 할 필요 없음.
        {
        	if (data[j+1] < data[j])
            {
            	temp = data[j+1];
                data[j+1] = data[j];
                data[j] = temp;
            }        
        }    
    }
}

 

흐름은 다음과 같다.

 

시작을 i 번 원소부터 했을때 

1. i번 원소와 i+1원소를 비교한다.

2. i번 원소가 i+1 보다 크면 둘을 교환한다.

3. i번 윈소가 i+1 보다 작거나 같으면 교환하지 않는다.

4. 1~3을 n번 반복한다.

 

 

 

 

 

 

요약

---

 

	삽입 정렬	선택 정렬	버블 정렬
최악의 경우	O(n²) 비교 및 교환	O(n²) 비교, O(n) 교환	O(n²) 비교, O(n²) 교환
최선의 경우 (순정렬인 경우)	O(n) 비교, O(1) 교환 (미실시)	O(n²) 비교, O(n) 교환	O(n) 비교, O(1) 교환 (미실시)
평균인 경우	O(n²) 비교 및 교환	O(n²) 비교, O(n) 교환	O(n²) 비교, O(n²) 교환

 

 

 

 

자주 쓰이지만, 그렇다고 설명하려고 하면 종종 헷깔리는 O(n²) 3종류에 대해 간단히 비교해보았다.