[Algorithm] Bubble sort, Selection sort, Insertion sort

1-1. Bubble sort / 버블 정렬

• 인접한 두 원소를 비교해서 정렬이 잘못되어 있으면 서로 바꾸는 방식으로 정렬한다.
• 한번 큰 for문을 돌 때마다 탐색 범위 중에서 가장 큰 값을 가지는 원소가 뒤로 이동한다(오름차순 정렬일 경우)
• 돌 때마다 큰 숫자 하나는 무조건 정렬되기 때문에 (전체 원소의 갯수 - 큰 for문을 돈 횟수)만큼 돌아주면 된다.
• 시간복잡도 : O(N^2)

1-2. Code

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> arr;

void Print() {
    for (int a : arr) {
        cout << a << " ";
    }
    cout << "\n";
}

void bubbleSort() {
    clock_t start, finish;
    double duration;

    start = clock();

    for (int i = 0; i < arr.size() - 1; i++) {
        bool isSwap = false;
        // 뒤에서 i개는 정렬이 무조건 되기 때문에 i씩 빼주기
        for (int j = 0; j < arr.size() - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                isSwap = true;
            }
        }
        if (!isSwap)
            break;
    }

    finish = clock();

    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    //Print();
    cout << "Bubble sort로 " << n << "개 원소 정렬에 걸린 시간 " << duration << "초" << "\n";
}

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) {
        arr.push_back(rand() % 100);
    }

    bubbleSort();
}

2-1. Selection sort / 선택 정렬

• 순환을 하며 범위 중 최솟값을 선택하여 정렬시키는 방법이다.(오름차순 정렬일 경우)
• 버블 정렬은 뒤쪽부터 값이 정렬된 반면 선택 정렬은 앞에서부터 값이 정렬된다.
• 시간복잡도 : O(N^2)

2-2. Code

#include<bits/stdc++.h>

using namespace std;

int n;

vector<int> arr;

void Print() {
    for(int a : arr) {
        cout << a << " ";
    }
    cout << "\n";
}

void selectionSort() {
    clock_t start, finish;
    double duration;
    
    start = clock();

    for(int i = 0; i < arr.size(); i++) {
        int minValueIdx = i;
        for(int j = i+1; j < arr.size(); j++) {
            if(arr[minValueIdx] > arr[j]) {
                minValueIdx = j;
            }
        }
        if(minValueIdx != i) {
            swap(arr[i], arr[minValueIdx]);
        }
    }

    finish = clock();
    
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    //Print();
    cout << "Selection sort로 " << n << "개 원소 정렬에 걸린 시간 " << duration << "초" << "\n";
}

int main() {
    cin >> n;

    for(int i = 0; i < n; i++) {
        arr.push_back(rand() % 100);
    }

    selectionSort();
}

---

3-1. Insertion sort / 삽입 정렬

• 삽입 정렬은 현재 위치부터 이전까지 값들을 비교하면서 다른 배열들은 밀어주고 자기가 들어갈 배열의 위치를 찾으면 삽입하는 정렬 알고리즘이다.
• 정렬된 데이터셋의 경우 while문이 실행되지 않고 넘어가기 떄문에 시간복잡도가 O(N)으로 나올 수 있다.하지만 시간복잡도는 항상 최악의 경우를 전제로 한다
• 시간복잡도 : O(N^2)

3-2. Code

#include <bits/stdc++.h>

using namespace std;

int n;

vector<int> arr;

void Print() {
    for (int a : arr) {
        cout << a << " ";
    }
    cout << "\n";
}

void Insertion_sort() {
    clock_t start, finish;
    double duration;

    start = clock();

    for (int i = 1; i < arr.size(); i++) {
        int target = arr[i];
        int j = i - 1;
        
        while(j >= 0 && arr[j] > target) {
            arr[j+1] = arr[j];
            j = j - 1;
        }
        arr[j+1] = target;
    }

    finish = clock();

    duration = (double)(finish - start) / CLOCKS_PER_SEC;

    //Print();
    cout << "Insertion sort로 " << n << "개 원소 정렬에 걸린 시간 " << duration << "초" << "\n";
}

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) {
        arr.push_back(rand() % 100);
    }

    Insertion_sort();
}