[C++] 정렬 알고리즘 - 선택 정렬/삽입 정렬/버블정렬

1.선택 정렬

int a[10] = {7, 5, 2, 10, 8, 4, 3, 1, 6, 9};

선택 정렬은 이 중에서 가장 작은 데이터를 선택해서 맨 앞의 데이터와 바꾸고 그 다음으로 작은 데이터를 선택해서 앞에서 두번째인 데이터와 바꾸는 작업을 반복해서 수행한다. 
항상 가장 작은 데이터를 선택해서 정렬하는 방법이다.  

#include <iostream>
#include <algorithm>
using namespace std;


int a[10] = {7, 5, 2, 10, 8, 4, 3, 1, 6, 9};
int main(void) {
    for (int i = 0; i < 10; i++) {
        int min_value = a[i]; // 우선 i번쨰 값을 mininum으로 설정
        int min_idx = i;
        for (int j = i+1; j < 10; j++) {
            if (min_value > a[j]) {
                min_value = a[j];
                min_idx = j; // min 값 갱신하기
            }
        }
        // 최소값과 배열의 i번째 값과 자리 바꾸기
        swap(a[i], a[min_idx]);
    }
    
    // 출력하기
    for (int i = 0; i < 10; i++) {
        cout << a[i] << " ";
    }
    return 0;
}

2. 삽입 정렬 

첫번쨰 원소는 우선 정렬되었다고 가정한다. 그리고 두번쨰 원소부터 비교를 시작한다. 

7, 5, 2, 10, 8, 4, 3, 1, 6, 9

5, 7, 2, 10, 8, 4, 3, 1, 6, 9 -> 5는 7보다 작으므로 7 과 자리를 바꾼다 

3, 5, 7, 10, 8, 4, 2, 1, 6, 9 -> 3은 5보다 작으므로 5의 앞에 삽입한다 

3, 5, 7, 10, 8, 4, 2, 1, 6, 9 -> 10은 3, 5, 7 보다 크므로 자리 이동을 하지 않는다. 

... 위의 과정을 반복한다. 

즉, 현재 확인 중인 원소가 더 이상 앞으로 갈 수 없으면, 그 곳이 삽입할 위치이다. 즉 자기 자신보다 작은 수를 만나면 삽입할 위치에 대한 탐색을 종료한다. 

#include <iostream>
#include <algorithm>
using namespace std;


int a[10] = {7, 5, 2, 10, 8, 4, 3, 1, 6, 9};
int main(void) {
    
    for (int i = 1; i < 10; i++) {
        for (int j = i; j >= 0; j--) {
            if (a[j] < a[j-1]) { // 자기 자신보다 크면 swap
                swap(a[j], a[j-1]);
            } else { // 더이상 앞으로 갈 수 없으면 그 곳에서 삽입하기 -> 자기 자신보다 작은 수를 만나면 break
                break;
            }
        }
    }
    
    // 출력하기
    for (int i = 0; i < 10; i++) {
        cout << a[i] << " ";
    }
    return 0;
}

 

3. 버블 정렬 

버블 정렬은 매번 배열의 다음 인덱스 값과 자신의 값을 비교하여 자리를 이동시킨다. 

#include <iostream>
#include <algorithm>
using namespace std;


int a[10] = {7, 5, 2, 10, 8, 4, 3, 1, 6, 9};
int main(void) {
    int temp;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10 - i -1; j++) {
            if (a[j] > a[j+1]) { // 현재 위치 값보다 다음 위치의 값이 더 작을 경우 값을 바꾼다
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
    
    // 출력하기
    for (int i = 0; i < 10; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}