문제
N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
정렬하는 방법은 선택정렬입니다.
💡 입력설명
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.
💡 출력설명
오름차순으로 정렬된 수열을 출력합니다.
💡 입력예제
6
13 5 11 7 23 15
💡 출력예제
5 7 11 13 15 23
코드
첫 번째 풀이
#include <stdio.h>
#include <vector>
using namespace std;
int main() {
int n, i, j, cnt;
vector<int> a(n);
vector<int> ch(n);
scanf("%d", &n);
for(i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
for(i = 0; i < n; i++) {
cnt = 0;
for(j = 0; j < n; j++) {
if(a[i] < a[j]) {
cnt++;
}
}
ch[n-cnt-1] = a[i];
}
for(i = 0; i < n; i++) {
printf("%d ", ch[i]);
}
return 0;
}사용자로부터 자연수를 입력받을 a배열과 오름차순으로 정렬하기 위한 ch배열을 선언한다.
N개의 입력을 a배열에 할당하고 arr 2중 for문으로 순회하여 해당 자연수가 다른 자연수보다 클 경우를 counting한다.
사용자로부터 받은 N에서 counting - 1한 값을 뺀 값을 index로 하는 ch배열에 해당 자연수를 할당해나간다.
최종 풀이
#include <stdio.h>
#include <vector>
using namespace std;
int main() {
int n, i, j, idx, tmp;
scanf("%d", &n);
vector<int> a(n);
for(i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
for(i = 0; i < n - 1; i++) {
idx = i;
// 가장 작은 값의 idx를 구함.
for(j = i + 1; j < n; j++) {
if(a[j] < a[idx]) {
idx = j;
}
}
// idx로 스왑.
tmp = a[i];
a[i] = a[idx];
a[idx] = tmp;
}
for(i = 0; i < n; i++) {
printf("%d ", a[i]);
}
return 0;
}
설명
사용자로부터 입력받은 N만큼의 크기를 갖는 배열 a를 선언하고 자연수들을 입력받아 할당한다.
N-1 만큼의 for문을 작성하여 각 자연수의 index를 idx에 할당하고 i+1 ~ n까지 반복하는 2중 for문을 작성하여 a[j]가 a[idx]보다 작을 때 마다 idx를 j로 할당한다.
2중 for문에 빠져나오면 idx는 가장 작은 값의 위치로 할당되어 있으므로 해당 idx와 i의 위치로 갖는 값을 swap하여 이를 반복한다.
배운 점
선택정렬
개념
원소를 넣을 위치가 고정되어 있고 나머지 원소들과 비교한 후 선택하여 정렬하는 알고리즘 기법이다.
시간복잡도
(n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2이므로, O(n^2) 이다.
공간복잡도
하나의 배열 안에서 swap이 이루어지며 정렬이 되므로 O(n)이다.
장점
1. 구현이 간단하다.
2. 다른 메모리 공간이 필요하지 않다.
단점
1. 시간복잡도가 좋지 않아 비효율적이다.
해당 내용은 김태원님의 'it 취업을 위한 알고리즘 문제풀이' 강의를 듣고 작성한 글입니다.
