#2550번 수 정렬하기 (c++)

#include <iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    cin >> T;
    int arr[T];
    int i,j = 0;
    
    for(int i=0; i<T; i++)
        cin >> arr[i];
    
    for(i=1; i<T; i++){
        int key = arr[i];
        for(j=i-1; j>=0; j--){
            if(arr[j]>key) arr[j+1] = arr[j];
            else break;
        }
        arr[j+1] = key;
    }
    
    for(int i=0; i<T; i++)
        cout << arr[i] << " ";
    
    return 0;
}

1. 버블 정렬

: 본문에 충실하게 버블정렬로 풀어보았다. 

핵심 키워드는 key값을 정하고, 해당 키 값의 왼쪽 숫자 들과 비교하여 key값보다 큰 값이 있으면 자리를 바꿔주는 형식. 

처음에는 비교횟수가 적다가 점점 비교횟수가 커지는게 특징이다. 

 

#include <iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    cin >> T;
    int arr[T];
    
    for(int i=0; i<T; i++)
        cin >> arr[i];
    
    for(int i=0; i<T-1; i++){
        for(int j=0; j<T-1-i; j++){
            if(arr[j]>arr[j+1])
                swap(arr[j],arr[j+1]);
        }
    }
    
    for(int i=0; i<T; i++)
        cout << arr[i] << " ";
    
    return 0;
}

2. 삽입 정렬

: 마찬가지로 본문에 충실하게 삽입 정렬로 풀어보았다. 

핵심 키워드는 왼쪽부터 차례로 서로 값을 비교해서, 큰 값이 있으면 자리를 바꿔주는 형식. 

처음에는 비교횟수가 많다가 점점 비교횟수가 작아지는게 특징이다. 

 

여기에는 언급되지 않은 선택정렬을 비롯하여, 위의 두 정렬의 기본 개념에 대한 요약은 

하단에 기입되어있다. 

 

https://astrid-dm.tistory.com/15?category=831188

정렬 - 선택 정렬 / 버블 정렬 / 삽입 정렬