백준 02750 - 수 정렬하기

출처 : https://www.acmicpc.net/problem/2750 

2750번: 수 정렬하기

 

고려사항

• n^2 의 시간 복잡도를 지닌 기본적인 버블, 선택, 삽입 정렬을 구현해보았다.
• 같은 n^2 임에도, 다른 특징들을 가진다.
• 버블정렬을 기준으로 선택 정렬은 swap 연산이 더 적고,
  삽입 정렬은 일반적으로 더 빠르게 여겨지며, 최선의 경우 n 시간 복잡도를 지닌다.
• 버블, 삽입은 stable sort 이며, 선택 정렬은 unstable sort 이다.
• stable sort 는 같은 값을 지닌 원소들이 있을 때, 그 순서가 정렬되고 나서도 유지됨을 보장하는 정렬 기법이다.
• 선택 정렬 같은 경우 예를 들어 2 2 1 3 과 같은 배열을 선택 정렬을 하면, 1 2 2 3 이다. 
  이 때, 2 2 1 3 을 B b A C 라 치면, 선택 정렬 결과는 B와 A가 swap 되어 A b B C 가 된다.
  같은 값인 2 2 가 정렬되고 나서 기존의 순서 B b에서 b B 순서로 변경되었기 때문에 선택정렬은
  unstable sort 라고 한다. unstable 하다라는 뜻은 항상 순서가 변경된다가 아닌, 순서 유지를 보장하지 못한다는 뜻이다.
• 대표적인 정렬 알고리즘을 stable과 unstable로 나누면 아래와 같다.
  stable - 버블, 삽입, 머지
  unstable - 선택, 퀵, 힙

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n){
    int tmp;

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

void selectionSort(int arr[], int n){
    int tmp;
    int minIdx;

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

        tmp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = tmp;
    }
}

void insertionSort(int arr[], int n){
    int tmp;
    int idx;

    for(int i=1;i<n;++i){
        tmp = arr[i];
        idx = i-1;
        while(idx >= 0 && arr[idx] > tmp){
            arr[idx+1] = arr[idx];
            --idx;
        }

        arr[idx+1] = tmp;
    }
}

int main() {
    int arr[1000];
    int n, tmp;

    cin>>n;
    for(int i=0;i<n;++i){
        cin>>tmp;
        arr[i] = tmp;
    }

    insertionSort(arr, n);
    //selectionSort(arr, n);
    //bubbleSort(arr, n);

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