반응형

2750번: 수 정렬하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
#include<stdio.h> void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } int main() { int n, min, index; scanf("%d", &n); int a[n]; for(int i = 0; i < n; i++) { scanf("%d", &a[i]); } for(int i = 0; i < n; i++) { min = 1001; for(int j = i; j < n; j++) { if(min > a[j]) { min = a[j]; index = j; } } swap(&a[i], &a[index]); } for(int i = 0; i < n; i++) { printf("%d\n", a[i]); } return 0; }
- 선택 정렬을 사용하여 구현한 알고리즘.
배열에서 가장 작은 값을 탐색 O(N), 그리고 앞으로 보내는데 O(N)의 시간복잡도를 가짐으로
O(N^2)의 시간 복잡도를 가진다.
#include<stdio.h> void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } int main() { int n, min, index; scanf("%d", &n); int a[n]; for(int i = 0; i < n; i++) { scanf("%d", &a[i]); } for(int i = 0; i < n - 1; i++) { int j = i; while(j >= 0 && a[j] > a[j + 1]) { swap(&a[j], &a[j + 1]); j--; } } for(int i = 0; i < n; i++) { printf("%d\n", a[i]); } return 0; }
- 삽입 정렬을 이용하여 구현한 알고리즘.
배열의 첫 값과 다음 값을 계속 비교하여 앞으로 보낸다.
이것도 마찬가지로 O(N^2)의 시간 복잡도를 가진다.
반응형
'BaekJoon > C++' 카테고리의 다른 글
10799 : 쇠막대기 (C++) (0) | 2021.01.18 |
---|---|
2751 : 수 정렬하기 2 (C) (0) | 2021.01.11 |
1874 : 스택 수열 (C) (0) | 2021.01.10 |
11866 : 요세푸스 문제 (C) (0) | 2021.01.10 |
10845 : 큐 (C) (0) | 2021.01.10 |
댓글