문제 링크

오름차순으로 정렬하는 프로그램

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄부터 N개의 줄에는 수 주어진다.
이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

시간 제한 : 1 초
메모리 제한 : 128 MB

시간 복잡도가 O(n²)인 삽입 정렬 또는 버블 정렬 알고리즘으로 풀 수 있다.

삽입 정렬

삽입 정렬이란?

#include <iostream>

using namespace std;

void insertion_sort(int arr[], int N)
{
    int i, j;

    for (i = 1; i < N; i++)
    {
        int key = arr[i]; // 삽입할 요소

        for(j=i-1;j>=0;j--)
        {
            if(arr[j] > key) // 비교값이 key보다 클 경우 
            {
                arr[j+1] = arr[j]; // 해당 값을 한칸씩 뒤로 이동
            }
            else // 비교값이 key보다 작을 경우
                break; // 반복문 탈출
        }

        arr[j+1] = key; // 탈출한 j번째 요소 다음 순서에 key 삽입
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

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

    insertion_sort(arr, N);

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

    return 0;
}

버블 정렬

버블 정렬이란?

최악의 성능으로 패스.