[백준] 2750번 : 수 정렬하기 | C++

1. 문제 상세

 

https://www.acmicpc.net/problem/2750

 

 

 

2. 문제 접근

 

주어진 수들을 정렬하기 위해 버블 정렬 알고리즘을 사용해보자.

 

■ 버블 정렬

버블 정렬 알고리즘은 인접한 원소를 비교하여 순서를 정렬해가는 정렬 알고리즘이다.

 

버블 정렬은 인접한 두 값을 비교하여 큰 값을 뒤로 보낸다.

정렬의 크기가 N 이라고 해보자.

첫 번째 원소와 두 번째 원소를 비교하고, 두 번째 원소와 세 번째 원소,

이 순서대로 N - 1번 원소와 N 번 원소까지 비교한다.

이 과정을 한 번 마치고 나면 제일 큰 원소가 맨 뒤로 가게 된다.

따라서 두 번째 과정에서는 맨 마지막 원소를 제외하고 값을 비교해가고, 이 과정을 총 N - 1 번 반복한다.

 

아래는 버블 정렬의 예시이다.

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

 

 

버블 정렬의 시간복잡도를 확인해보자.

먼저 비교 횟수는 최선, 평균, 최악의 경우 모두 1부터 N - 1 까지의 합이므로

위 처럼 되고,

 

교환 횟수는 최악의 경우 1부터 N - 1 까지의 합에 교환횟수인 3을 곱해

위와 같이 된다.

 

따라서 버블 정렬의 시간복잡도는 O(N²)이다.

 

아래 사진을 통해 버블 정렬의 시간복잡도를

다른 정렬의 시간복잡도와 비교해보면 꽤 비효율적이라는 것을 볼 수 있다.

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

 

문제풀이를 통해 버블 정렬을 구현해보자.

 

 

 

3. 문제 풀이

 

#include <iostream>
using namespace std;

int main() {
    int n, a[1000], temp;

    cin >> n;

    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (a[j] > a[j + 1]) {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }

    for (int i = 0; i < n; i++) cout << a[i] << endl;
}

 

정수형 변수 n, temp 와 크기가 1000인 배열 a 를 선언한다.

 

cin 으로 정수(입력받을 정수의 개수)를 입력받아 n 에 저장한다.

 

for문으로 i 가 0부터 n 보다 작을 때 1씩 더하며 반복하도록 하고,

반복에서는 cin 으로 a 의 i 번 인덱스의 값을 입력받는다. // 정렬할 숫자 배열을 입력받는다

 

for문으로 i 가 n - 1 부터 0보다 클 때 1씩 빼며 반복 한다. // n - 1 번의 비교 과정 실행

다시 for문으로 j 가 0부터 i 보다 작을 때 1씩 더하며 반복한다.

// 과정에서 맨 앞부터 정렬된 원소 전까지 비교하며 교환 하도록 반복

위 반복에서 if문으로 a 의 j 번 원소가 j + 1 번 원소보다 크다면,

temp 에 j 번 원소를 저장, j 번 원소에 j + 1 번 원소의 값을 저장, j + 1 번 원소에 temp 값을 저장한다.

// 두 값을 비교하여 뒤의 원소가 크면 두 값을 교환하도록 한다.

 

모든 반복이 끝나면 for문으로 i 가 0부터 n 보다 작을 때 반복하며,

cout 으로 a 의 i 번 원소를 개행문자와 함께 출력한다. // 정렬이 끝나면 숫자 배열을 출력.

 

 

 

4. 성능 확인

 

 

 

 

5. 마무리

 

이미지 및 참고 글 출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

 

정렬 알고리즘 중 하나인 버블 정렬을 사용해 보았다.

전공 수업때 버블, 삽입, 선택, 퀵, 머지(합병), 셸, 힙 등 여러 정렬을 배웠었는데 거의 다 까먹은것같다...

정렬 단계 문제들을 통해 다시 한번 공부해보고 데이터 구조 글로 따로 정리해둬야겠다..