[백준] 2750 : 수 정렬하기 (C++)

🚩 정렬 알고리즘

📌 버블 정렬 (Bubble Sort)

---

📖 문제

BOJ 2750 : 수 정렬하기

---

🖥 코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> arr; // 수열 정의

void bubbleSort(int n){
    int cnt = 0;
    
    for(int i=0; i<n-1; i++){ //마지막 원소는 자동 정렬되므로 n-1까지 반복
        for(int j=0; j<n-1-i; j++){ // i는 이미 정렬된 수의 개수임
            if(arr[j] > arr[j+1]){
                //swap
                swap(arr[j], arr[j+1]);
            }
            cnt++;
        }
    }
    cout << "Count : " << cnt<<"\n";
}

int main()
{
    int n;
    
    //입력
    cin >> n;
    arr.assign(n, 0); //배열 크기 재할당
    for(int i=0; i<n; i++)
    {
        cin >> arr[i];
    }
    //정렬
    bubbleSort(n);
    
    //출력
    for(int i=0; i<n; i++){
        cout << arr[i] <<' ';
    }

    return 0;
}

---

💿 결과

5
5
2
3
4
1
1 2 3 4 5 

위 코드의 bubbleSort에서는 중첩 for문을 사용하므로 효율이 떨어진다.

더 향상된 bubbleSort를 작성하기 위해서 boolean을 이용한다.

---

🖥 더 효율적인 코드

void bubbleSortAdv(int n){
    for(int i = 0; i < n - 1; i++){
        bool isSwap = false; //두 원소가 바뀌었는지 확인
        for(int j = 0; j < n - 1 - i; j++){
            if(arr[j] > arr[j+1]){
                isSwap = true;
                swap(arr[j], arr[j+1])
            }
        }
        if(!isSwap){ //두 원소가 바뀌지 않았다면
            break;
        }
    }
}

---

©️ 출처

• [BOJ 백준 2750]
  https://www.acmicpc.net/problem/2750

• 알튜비튜