정렬

※ 모든 정렬은 오름차순, 횟수와 복잡도는 최악의 경우로만 표현

선택 정렬

길이가 n 인 배열 a 가 있을 때, i 번째 원소를 i ~ n 번째 값들 중 최소값과 바꾸어 나가는 작업을 1 부터 n-1 번째 원소까지 차례대로 반복한다.

C++

void swap(int& x, int& y){
    int tmp;
    tmp = x;
    x = y;
    y = tmp;
}

void selectionSort(vector<int>& a, int n){
    int least;
    for(int i = 0; i < n-1; i++){
        least = i;
        for(int j = i+1; j < n; j++){
            if(a[j] < a[least]) least = j;
        }
        swap(a[i], a[least]);
    }
}

외부 루프는 [0, n-1) n-1 번, 내부 루프는 [i+1, n) n-(i+1) 번으로 i 값이 0 부터 n-2 까지 증가됨에 따라 (n-1) + (n-2) + ... + 1 = n(n-1)/2 번 비교 연산이 진행된다.

• 비교 횟수 : n(n-1)/2
• 교환 횟수 : n-1
• 복잡도 : O(n²)

삽입 정렬

길이가 n 인 배열 a 가 있을 때, i 번째 원소를 1 ~ i-1 범위 내에서 올바른 위치를 찾아 삽입하는 작업을 2 부터 n 번째 원소까지 차례대로 반복한다.

C++

void insertionSort(vector<int>& a, int n){
    int key;
    for(int i = 1; i < n; i++){
        key = a[i];
        int j = i-1;
        while(j >= 0){
            if(a[j] < key) break;
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = key;
    }
}

자료가 정렬되어 있을 경우 각 단계별로 1번의 비교 연산만 이루어지지만, 자료가 역순으로 정렬되어 있을 경우 [1, n) 1 부터 n-1 까지 i 번씩 자리를 옮겨야 하므로 최대 1 + 2 + ... + (n-1) = n(n-1)/2 번 비교 연산이 진행된다.

• 비교 횟수 : n(n-1)/2
• 이동 횟수 : n(n-1)/2 + 2(n-1)
• 복잡도 : O(n²)

버블 정렬

인접한 두개의 원소를 비교하여 크기가 순서대로 되어있지 않으면 교환, 순서대로라면 교환하지 않는 작업을 맨 왼쪽 끝에서 오른쪽 끝 까지 진행한다. 이 과정을 n-1 번 반복하여 적용하면 정렬이 완료된다.

C++

void swap(int& x, int& y){
    int tmp;
    tmp = x;
    x = y;
    y = tmp;
}

void bubbleSort(vector<int>& a, int n){
    for(int i = n-1; i > 0; i--)
        for(int j = 0; j < i; j++)
            if(a[j] > a[j+1])
                swap(a[j], a[j+1]);
}

버블 정렬의 비교 횟수는 어떠한 경우에도 1 + 2 + ... + (n-1) = n(n-1)/2 번으로 일정하고, 이동 횟수는 자료가 역순으로 정렬되어 있을 때가 최악으로 모든 비교 과정에서 자료가 교환된다.

• 비교 횟수 : n(n-1)/2
• 이동 횟수 : n(n-1)/2
• 복잡도 : O(n²)