Bubble Sort, Select Sort, Insert Sort

출처 : https://www.bigocheatsheet.com/

❓ Bubble Sort란?

void Bubble_Sort(int *arr){

    for(int i=1;i<10;i++){
        for(int j=0;j<10-i;j++){
            if(arr[j] > arr[j+1]){
                swap(arr[j], arr[j+1]);
            }
        }
    }
}

int main(){
    int arr[10] = {1,7,3,5,4,50,24,8,9,6};

    Bubble_Sort(arr);

    for(int i=0;i<10;i++){
        cout << arr[i] << " ";
    }
}

인접한 두 개의 수를 비교하며 왼쪽의 수가 오른쪽의 수보다 크면 swap하는 방법
Stable한 방식

Time Complexity : (n), (n^2), O(n^2) (Best, Average, Worst)
Space Complexity : O(1)

❓ Select Sort란?

void Select_Sort(int *arr){

    for(int i=0;i<10;i++){
        int min_idx = i;
        for(int j=i+1;j<10;j++){
            if(arr[j] < arr[min_idx])
                min_idx = j;
        }

        if(min_idx != i)
            swap(arr[min_idx], arr[i]);
    }
}

int main(){
    int arr[10] = {1,7,3,5,4,50,24,8,9,6};

    Select_Sort(arr);

    for(int i=0;i<10;i++){
        cout << arr[i] << " ";
    }
}

남은 숫자들 중에서 가장 작은 수 를 선택하여 swap하는 방법
UnStable한 방식

Time Complexity : (n^2), (n^2), O(n^2) (Best, Average, Worst)
Space Complexity : O(1)

❓ Insert Sort란?

void Insert_Sort(int *arr){

    for(int i=1;i<10;i++){
        int key = arr[i];
        int j = i-1;

        while(j>=0 && arr[j] > key){
            arr[j+1] = arr[j];
            j = j-1;
        }
        arr[j+1]=key;
    }
}

int main(){
    int arr[10] = {1,7,3,5,4,50,24,8,9,6};

    Insert_Sort(arr);

    for(int i=0;i<10;i++){
        cout << arr[i] << " ";
    }
}

해당 자리의 알맞는 숫자(작은 수)를 선택하여 앞에 정렬했던 수들을 오른쪽으로 밀고, 자리에 넣는 방법
Stable한 방식

Time Complexity : (n), (n^2), O(n^2) (Best, Average, Worst)
Space Complexity : O(1)

❓ Bubble, Select, Insert는 언제 사용해야 할까?

구현이 간단하다.
모두 O(n^2)으로 시간 복잡도는 포기하고, 공간 복잡도가 O(1)이기 때문에 메모리를 잡아먹지 않는다.