[c++] 알고리즘 개념공부 :: 정렬 (선택 정렬, 버블 정렬, 삽입 정렬)

선택 정렬

개념

 max, min 정렬이라고도 불린다. 처음부터 끝 원소까지 훑으면서 최소나 최대를 찾아서 리스트의 처음이나 끝에 넣고 해당 원소를 제외한 다른 원소에 대해 다시 정렬을 시행하는 방법이다.

 

무작위로 정렬된 데이터의 처음부터 끝까지 탐색한 후, 가장 큰 수를 리스트의 마지막 요소와 교환한다.

 

 

그 후 마지막 원소를 제외한 채로 처음부터 끝까지 데이터를 탐색한 후, 가장 큰 수를 리스트의 마지막 요소와 교환한다.

 

 

구현

의사 코드는 다음과 같다.

(min 정렬)
for i=0 to n:
    a[i]부터 a[n-1]까지 차례로 비교하여 최소값이 있는 a[j]를 찾는다.
a[i]와 a[j]를 바꾼다.

(max 정렬)
for i=0 to n:
    a[0]부터 a[n-i-1]까지 차례로 비교하여 최대값이 있는 a[j]를 찾는다.
a[n-i-1]과 a[j]를 바꾼다.

 

c++로 구현한 코드는 다음과 같다.

void selectionSort(int* arr) {
    cout << "selection sort(min, max sort)" << endl;
    for (int i = 0; i < arr_size; i++) {
        int max_idx = 0;
        for (int j = 0; j < arr_size - i; j++) {
            if (arr[max_idx] < arr[j])
                max_idx = j; // 최대값 찾기
        }
        swap(arr, max_idx, arr_size - 1 - i);
        // 최대값 뒤로 옮겨두기
    }
}

 

시간 복잡도

선택 정렬은 리스트의 사이즈가 들어간 반복문이 2개나 있으므로 O(n^2)의 시간복잡도를 갖는다. 최선, 최악, 평균 시간복잡도가 O(n^2)으로 같다.

 

정확히는 비교 횟수가 n(n-1)/2번으로 O(n^2)이고 이동 횟수가 최대3(n-1)이므로 전체 복잡도가 O(n^2)이다.

 

특징

• 불안정 정렬이다.
  • ex) 5345268 => 5의 위치가 뒤바뀐다.

 

버블 정렬

개념

버블 정렬은 앞에서부터 거품이 튀듯이 튕겨서 큰 수를 뒤로 보내는 정렬이다.

 

 

무작위로 정렬된 데이터 처음부터 두 원소씩 짝을 지어서 대소를 비교한다.

 

 

앞에 배치된 수가 뒤의 수보다 크면 자리를 바꾼다. 큰 수가 뒤로 가게 만드는 것이다.

 

 

이렇게 반복하다보면 리스트에서 가장 큰 수인 9가 맨 뒤로 밀려나게 된다.

 

 

그 후에는 9를 제외하고 남은 원소에 한해서 다시 처음부터 비교한다.

 

구현

의사코드는 다음과 같다.

for i=0 to n:
    for j=0 to n-i:
        arr[i]와 arr[i+1]을 비교한다. arr[i]가 더 크면 두 수를 교환한다.

 

c++로 구현한 코드는 다음과 같다.

void swap(int* arr, int idx1, int idx2) {
    int tmp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = tmp;
}

void bubbleSort(int* arr) {
    cout << "bubble sort" << endl;
    for (int i = 0; i < arr_size-1; i++) {
        for (int j = 0; j < arr_size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1); // 이웃한 두 개의 요소 비교
            }
        }
    }
}

 

시간 복잡도

버블 정렬은 리스트의 사이즈가 들어간 반복문이 2개나 있으므로 O(n^2)의 시간복잡도를 갖는다. 최선, 최악, 평균 시간복잡도가 O(n^2)으로 같다.

 

정확히는 비교 횟수가n(n-1)/2 번으로 O(n^2)이고 이동 횟수가 최대 O(n^2)이므로 전체 복잡도가 O(n^2)이다.

 

특징

• 안정 정렬이다.

 

삽입 정렬

개념

삽입 정렬은 정렬된 요소들과 현재 요소를 비교하여 자신의 위치를 찾아 삽입하는 정렬이다.

 

 

무작위로 정렬된 데이터의 첫번째 요소는 이미 정렬된 요소로 본다.

 

 

정렬할 요소를 이미 정렬된 요소와 비교하여 맞는 위치에 삽입한다.

 

 

정렬되지 않은 요소를 맞는 위치를 찾아 삽입하는 식으로 정렬된 요소로 만드는 작업을 반복하다보면 전체 요소가 정렬된다.

 

구현

의사코드는 다음과 같다.

for i=1 to n:
    for j=i-1 to 0:
        arr[j]가 arr[i]보다 작다면 j+1의 위치에 arr[i]를 삽입한다.

 

c++로 구현한 코드는 다음과 같다.

void insert(int* arr, int idx, int data_idx) {
    if (idx == data_idx)
        return;

    int tmp = arr[data_idx];
    for (int i = data_idx-1; i >= idx; i--) {
        arr[i + 1] = arr[i];
    }
    arr[idx] = tmp;
}

void insertionSort(int* arr) {
    cout << "insertion sort" << endl;
    for (int i = 1; i < arr_size; i++) { // 정렬되지 않은 요소
        int idx = i;
        for (int j = i-1; j >= 0; j--) { // 정렬된 요소
            if (arr[j] > arr[i]) {
                idx = j;
            }
            else
                break;
        }
        insert(arr, idx, i);
    }
}

 

시간 복잡도

 삽입 정렬은 역순 정렬되어있는 최악의 경우 (1+2+...+n-1)번 비교를 수행한다. 이동도 비교와 같이 발생하므로 시간복잡도는 n(n-1)/2 즉 O(n^2)이다.

 

 최선은 이미 정렬되어있는 경우이며, 두번째 반복문이 항상 1번씩만 실행되므로 비교횟수는 n-1 번이며 이동횟수는 0번이므로 O(n)이다.

 

특징

• 안정 정렬이다.