본문 바로가기
BaekJoon/C++

2750 : 수 정렬하기 (C)

by GrayChoi 2021. 1. 11.
반응형

 

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

댓글