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

걸린 시간: 2m31s

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

풀이

1#include <iostream>
2using namespace std; 
3
4int arr[1001];
5int main() {
6  int t;
7  cin >> t;
8  for(int i=0; i<t; ++i) {
9    cin >> arr[i];
10  }
11
12  for(int i=0; i<t; ++i) {
13    bool swapped = false;
14    for(int j=0; j<t-1-i; ++j) {
15      if(arr[j] > arr[j+1]) {
16        swapped = true;
17        int temp = arr[j];
18        arr[j] = arr[j+1];
19        arr[j+1] = temp;
20      }
21    }
22
23    if(!swapped) break;
24  }
25
26  for(int i=0; i<t; ++i) {
27    cout << arr[i] << endl;
28  }
29  return 0;
30}

시간 복잡도

• Bubble sort: O(N^2)
• 최종 시간 복잡도: O(n^2)

공간 복잡도

• 입력 받은 N개의 입력을 저장: O(N)
• 최종 공간 복잡도: O(n)