문제

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

입력

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

출력

• 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

---

1. 기본 아이디어 및 소스코드

• 제한시간 1초이다. C++인 경우 시간복잡도가 $O(N)$ 이라고 할 때, $N$이 1억이 되어야 1초가 걸린다고 들었다.
• Bubble Sort의 시간복잡도는 $O(N^2)$ 인데, 문제에서 최대 $N$을 1,000까지만 주기 때문에 버블정렬을 써도 충분하다고 생각해서 버블정렬을 구현하였다.
• 다른 정렬방법들에 비해서는 구현이 간단하지만 비효율적인 방법이다.

#include <iostream> #include <algorithm> using namespace std; void bubbleSort(int numbers[], int N) { int temp = 0; for (int i = 0; i < N - 1; i++) { for (int j = 0; j < N - 1 - i; j++) { if (numbers[j] > numbers[j + 1]) { temp = numbers[j]; numbers[j] = numbers[j + 1]; numbers[j + 1] = temp; } } } } int main() { int N; scanf("%d", &N); int numbers[N]; for (int i = 0; i < N; i++) { scanf("%d", &numbers[i]); } bubbleSort(numbers, N); for (int i = 0; i < N; i++) { printf("%d\n", numbers[i]); } }

2. 다른 아이디어 및 소스코드

• Selection Sort로도 문제를 해결할 수 있다.
• 마찬가지로 이 정렬 알고리즘도 시간복잡도가 $O(N^2)$ 이다.
• 따라서, 다른 정렬 알고리즘에 비해서는 구현이 간단하지만 비효율적이다.

1. 주어진 리스트 중에 (정렬이 되지 않은 남은 부분중에) 최솟값을 찾는다.
2. 그 값을 정렬이 안 된 부분 중 맨 앞의 값과 교체한다.

#include <iostream> #include <algorithm> using namespace std; void selectionSort(int numbers[], int N) { int temp, minidx; for (int i = 0; i < N - 1; i++) { minidx = i; //남은 데이터들 중 최솟값을 가진 인덱스 찾기 for (int j = i + 1; j < N; j++) { if (numbers[minidx] > numbers[j]) { minidx = j; } } //최솟값을 찾았으면 numbers[i]와 자리 바꿔주기 temp = numbers[i]; numbers[i] = numbers[minidx]; numbers[minidx] = temp; } } int main() { int N; scanf("%d", &N); int numbers[N]; for (int i = 0; i < N; i++) { scanf("%d", &numbers[i]); } selectionSort(numbers, N); for (int i = 0; i < N; i++) { printf("%d\n", numbers[i]); } }