정렬 - 선택정렬, 버블정렬
선택정렬
선택정렬 이론 :
이렇게 정렬하는 알고리즘이다.
for문 i 안에서 for문 j가 탐색을 하며 가장 작은 수를 찾아 현재 위치랑 교환(swap)하는 것을 반복한다.
이중 반복문이고, 끝까지 탐색을 해야 하기 때문에 O(N*N)인 시간복잡도를 가지고 있다.
비효율적인 정렬이라고 할 수 있다.
O(NlogN)의 시간복잡도를 가진 sort함수를 나두고 이걸 사용할 필요가 있나 싶지만 알아두기로 하자
코드는 이런 느낌으로 작성된다.
for(i= ..) {
idx = i;
for(j=i+1; j<n; j++) {
if(a[j] < a[idx]) idx = j;
}
}
tmp = a[i];
a[i] = a[idx]
a[idx] = tmp;
선택정렬 문제 1 : 단순 오름차순 정렬
문제 :
N개의 숫자 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
정렬하는 방법은 선택정렬입니다.
첫 번째 줄에 자연수 N(1<=N<=100) 주어지고, 두 번째 줄에 N개의 자연수가 공백 사이에 두고 입력된다.
입력예제 1
6
13 5 11 7 23 15
출력예제 1
5 7 11 13 15 23
소스코드 :
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m, idx, i, j, tmp;
vector<int> v;
cin >> n;
for(i=0; i<n; i++) {
cin >> m;
v.push_back(m);
}
for(i=0; i<n-1; i++) {
idx = i;
for(j=i+1; j<n; j++) {
if(v[j]<v[idx]) idx = j;
}
tmp = v[i];
v[i] = v[idx];
v[idx] = tmp;
}
for(i=0; i<n; i++) {
cout << v[i] << " ";
}
return 0;
}
선택정렬 문제 2 : 3등의 성적 구하기
문제 :
N명의 수학성적 주어지면 3등을 한 수학성적 출력하는 프로그램을 작성하세요.
100점 3명, 99점 2명, 98점 5명일 경우 1등 3명, 2등 2명, 3등 5명이 되고 98점이 3등이 됩니다.
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 수학성적 점수가 공백 사이에 두고 입력됩니다.
수학성적 점수는 100점 만점 기준으로 입력됩니다.
입력예제 1
7
80 96 75 82 96 92 100
출력예제 1
92
대략 이런 느낌으로 작성하면 된다.
cnt로 등수를 구할 수 있다.
소스코드 :
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m, idx, tmp;
int cnt = 0;
vector<int> v;
cin >> n;
for(int i=0; i<n; i++) {
cin >> m;
v.push_back(m);
}
for(int i=0; i<n-1; i++) {
idx = i;
for(int j=i+1; j<n; j++) {
if(v[j] > v[idx]) idx = j;
}
tmp = v[i];
v[i] = v[idx];
v[idx] = tmp;
}
for(int i=1; i<n; i++) {
if(v[i-1] != v[i]) cnt++;
if(cnt == 2) {
cout << v[i];
break;
}
}
return 0;
}
버블정렬
버블정렬 이론 :
버블정렬은 이웃한 두 수를 계속 비교하는 방식이다.
위 그림에서 i는 4까지 돌고, j는 0번부터 끝까지 돌린다.
i 반복문 안에서 j 반복문을 돌리는 방식이다.
j 반복문이 끝까지 돌면서 a[j] 와 a[j+1]를 비교한다.
a[j] > a[j+1]일 경우 두 수를 swap하면 된다.
당연하지만, 버블정렬 역시 이중 반복문을 끝까지 돌려야 하므로
시간복잡도는 O(N*N)인 시간복잡도를 가지고 있다.
코드는 이런 느낌으로 작성된다.
for(int i=0; i<n-1; i++) {
for(int j=0; j<n-i-1; j++) {
if(a[j] > a[j+1]) swap
}
}
버블정렬 문제 1 : 단순 오름차순 정렬
문제 :
N개의 숫자 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
정렬하는 방법은 버블정렬입니다.
첫 번째 줄에 자연수 N(1<=N<=100) 주어지고, 두 번째 줄에 N개의 자연수가 공백 사이에 두고 입력된다.
입력예제 1
6
13 23 11 7 5 15
출력예제 1
5 7 11 13 15 23
소스코드 :
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m, tmp;
vector<int> v;
cin >> n;
for(int i=0; i<n; i++) {
cin >> m;
v.push_back(m);
}
for(int i=0; i<n-1; i++) {
for(int j=0; j<n-i-1; j++) {
if(v[j]>v[j+1]) {
tmp = v[j];
v[j] = v[j+1];
v[j+1] = tmp;
}
}
}
for(int i=0; i<n; i++) {
cout << v[i] << " ";
}
return 0;
}
버블정렬 문제 2 : Special Sort ( 버블정렬 응용 : 구글 인터뷰 )
문제 :
N개의 숫자 입력되면 당신은 입력된 값을 정렬해야 한다.
음의 정수는 앞쪽에, 양의 정수는 뒷쪽에 있어야 한다.
또한 양의정수와 음의정수의 순서에는 변함이 없어야 한다.
첫 번째 줄에 자연수 N(1<=N<=100) 주어지고,
두 번째 줄부터 음수를 포함한 정수가 주어진다. 숫자 0은 입력되지 않는다.
입력예제 1
8
1 2 3 -3 -2 5 6 -6
출력예제 1
-3 -2 -6 1 2 3 5 6
풀이 :
양수 앞에 음수가 있을 경우 swap해주는 것을 반복하면 된다. 이를 위해 버블정렬을 사용한다.
소스코드 :
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m, tmp;
vector<int> v;
cin >> n;
for(int i=0; i<n; i++) {
cin >> m;
v.push_back(m);
}
for(int i=0; i<n-1; i++) {
for(int j=0; j<n-i-1; j++) {
if(v[j]>0 && v[j+1]<0) {
tmp = v[j];
v[j] = v[j+1];
v[j+1] = tmp;
}
}
}
for(int i=0; i<n; i++) {
cout << v[i] << " ";
}
return 0;
}
출처 (학습 자료) :
it 취업을 위한 알고리즘 문제풀이
https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#curriculum