[BaekJoon/백준] 2750번

Bubble Sort와

Insert Sort를 각각 이용해서 문제 해결

#include <iostream>
using namespace std;

void Bubble_sort(int* arr, int N) {
    int temp;
    for(int i = N-1; i>0; i--) {
        for(int j = 0; j<i; j++) {
            if(arr[j]>arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

void insert_sort(int* arr, int N) {
    for(int i=1; i<N; i++) { //index 1부터 시작해야함.
        int k=i; int v = arr[k];
        //이중포문 대신에 간단한 while문
        while(k) {
            if(v<arr[k-1]) { //선택값과 아랫값들을 차례로 비교
                arr[k] = arr[k-1]; //밀어넣기
                k--;
            } else
                break;
        }
        // 최종적으로 k-1 인덱스에 넣는 것이 목적이므로, 밀어넣기 후 k--해서 넘겨온 값을 그대로 이용하는 것.
        if(k!=i) //위치변경이 있었을 경우에만 실행
            arr[k]=v;
    }
}

int main() {
    int N;
    cin >> N;
    int* arr = new int[N];
    
    for(int i=0; i<N; i++) {
        cin >> arr[i];
    }
    
    insert_sort(arr, N);
    //or
    Bubble_sort(arr, N);
    
    for(int i=0; i<N; i++) {
        cout << arr[i] << endl;
    }
}

시간복잡도 : 각각 O(n^2)