정렬 - 선택정렬, 버블정렬

선택정렬

 

선택정렬 이론 :

이렇게 정렬하는 알고리즘이다.

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