[정렬] 버블 정렬과 삽입 정렬

버블 정렬

• 정의 : 버블 정렬은 말 그대로 거품 정렬이다. 리스트 안의 원소들이 점점 뒤로 밀려들어가기 때문에 이 모습이 마치 거품이 수면위로 올라오는 듯한 모습처럼 보여 지어진 이름이다.
• 방법 : 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해 가면서, 큰 수가(내림차순인 경우 작은 수가) 오른쪽으로 가도록 교환한다. 이 때 맨 끝과 그 앞의 원소까지 비교하면, 가장 큰 원소(또는 가장 작은 원소)를 찾은 것이므로, 다시 나머지 n-1개 수에 대하여 다시 반복한다.
• 예시 

9 5 2 4 1 라는 배열이 있다고 가정하자. 오름차순을 만드는 버블 정렬을 순차적으로 표현하면

9 5 2 4 1 -> 5 9 2 4 1 -> 5 2 9 4 1 -> 5 2 4 9 1 -> 5 2 4 1 9

5 2 4 1 9 -> 2 5 4 1 9 -> 2 4 5 1 9 -> 2 4 1 5 9

2 4 1 5 9 -> 2 4 1 5 9 -> 2 1 4 5 9   

2 1 4 5 9 -> 1 2 4 5 9

 

이렇게 주어진 배열을 오름차순으로 정렬할 수 있다.

 

• C++ 코드

#include <stdio.h>
 
int main() {
    int mat[5] = {9,5,2,4,1};
    
    //bubble sort
    for (int i = 0; i < 5; i++) {
        for (int j = i; j < 5; j++) {
            if (mat[i] > mat[j]) { //두 수 swap
                int temp = mat[i];
                mat[i] = mat[j];
                mat[j] = temp;
            }
        }
    }
    for (int i = 0; i < 5; i++) {
        printf("%d ", mat[i]);
    }
 
    return 0;
}

이런 식으로 for 문을 두 번 돌면서 두 수를 계속 비교해 왼쪽에 있는 수가 더 크면 오른쪽 수와 교환한다.

 

• 시간 복잡도

  처음 가장 큰 원소를 구할 때 n-1 비교, 두번째 큰 원소를 구할 때 n-2번 비교 , ...

  (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n^2) 

  이처럼 입력과 무관하게, n개의 값을 정렬할 때 항상 똑같은 횟수의 비교를 수행한다 (그 전에 정렬이 완료되었어도 컴퓨터가 알아서 멈추지 않고 계속 비교한다!)

,

삽입 정렬

• 정의 : 정렬 대상이 될 원소들을 두 부분으로 나눈 후 순차적으로 오른쪽 원소들을 왼쪽으로 삽입시켜 정렬한다.
• 방법 : 원소들을 담고 있는 배열을 "아직 정렬되지 않은 부분", "정렬된 부분"으로 각각 나눈 후, 정렬되지 않은 부분에서 원소들을 하나 씩 꺼내 정렬된 부분에 삽입한다. 이 때 삽입은 "정렬된 부분" 의 가장 큰 원소(오른쪽)부터 왼쪽으로 비교해나가면서 진행한다.
• 예시 : {5,3,1,4,2} 배열이 있다고 가정하자.  배열의 가장 왼쪽 부분 즉 {5} 왼쪽부분({})을 "정렬된 부분"이라하고(아직 아무것도 안들어있다), 오른쪽 부분({5,3,1,4,2})을 "정렬되지 않은 부분"이라고 두자. 이후 정렬되지 않은 부분의 첫번째 원소부터 오른쪽으로 집어넣어보자

순서	정렬된부분(왼쪽)	정렬되지 않은부분(오른쪽)
1	비어있음	5 3 1 4 2
2	5	3 1 4 2
3	5 3 -> 3 5	1 4 2
4	3 5 1 -> 3 1 5 -> 1 3 5	4 2
5	1 3 5 4 -> 1 3 4 5	2
6	1 3 4 5 2 ->> 1 2 3 4 5	비어있음

위 표의 밑줄은 이 부분에서 비교를 진행한다는 의미이다.

이런식으로 하나의 배열 안에서 정렬을 할 수 있고, 위의 버블 정렬과 다르게 적절한 위치를 찾으면 거기서 멈출 수 있다.

• C++ 코드

 

#include <iostream>
using namespace std;
 
//삽입 정렬
void insertionSort(int arr[], int n) {  //배열과 배열 원소의 개수를 받는다
    int temp = 0; //비교할 값을 저장할 변수
    for (int i = 1; i < n; i++) {    //가장 왼쪽 값은 옮겨둔것으로 설정한 후 나머지 n-1개의 원소만 옮김
        temp = arr[i];
        int sort_cnt = i - 1; //저장 공간 변수 index
        while (sort_cnt >= 0 && arr[sort_cnt] > temp) {  //배열범위 0 이상 and 정렬된 부분의 원소가 꺼낸 값보다 클 때
            arr[sort_cnt + 1] = arr[sort_cnt];
            sort_cnt--;
        }
        arr[sort_cnt + 1] = temp;
    }
}
int main()
{
    int arr[5] = { 5,3,1,4,2 };  // 주어진 배열
    int n = 5; // 원소의 개수     
    insertionSort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ",arr[i]);
    }
    return 0;
}
 

 

 

• 시간복잡도 : 삽입정렬은 위에서도 말했듯이 숫자 입장에서 자기가 적절한 위치에 왔다~ 싶으면 멈춘다(왼쪽값보다 자기가 크면 반복을 멈추고 다음 수로 넘어간다) 
• 최적 : 이미 배열이 정렬된 경우 숫자를 그냥 옮기고 딱 한번만 비교하면 더이상 비교를 하지 않아서 시간복잡도는 O(n)이 된다. 
• 최악 : 배열이 내림차순으로 정렬된 경우 최적의 경우 + 값을 옮길때마다 왼쪽에있는 정렬된값들을 전부다 비교해야하므로 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n^2) 번 비교한다.

위에서 살펴본 두 정렬은 모두 시간복잡도가 O(n^2)이다.

그렇다면 정렬은 O(n^2)이 최적일까?? 당연히 아니다

하지만, 인접한 두 원소를 교환하는 방식으로는 O(n^2)가 최적이다.

왜냐하면 n개의 원소들 중 둘을 뽑는 방법은 (n,2)가지가 있는데, 최악으로 정렬된 경우 이 방법 전부다 사용하여야하기때문에 (n,2) = O(n^2) 번 교환이 필요하다.

그렇다면 인접한 두 원소를 비교하여 정렬하는 방법 말고 다른 방법이 있을까?? 그렇다!

간단히 생각해보자면 크게 크게 정렬을 하면서 나누면 된다. 이를 분할 정복 기법이라고 하는데

다음 장에서 살펴보겠다.