코딩 테스트 공부 - 버블 정렬(백준 1337번)

버블 정렬 - 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식

장점 : 구현이 쉽다.

단점 : 상대적으로 다른 정렬 알고리즘보다 시간이 오래 걸린다.

시간 복잡도 - $ O(n^{2}) $

 

버블 정렬 코드 스니펫

#include <algorithm>
#include <vector>
using namespace std;

int main() {
  int N = 1000;
  vector<int> A(N, 0);
  bool change = false;
  for (int i = 1; i <= N + 1; i++) {
    change = false;
    for (int j = 1; j <= N - i; j++) {
      if (A.at(j) > A.at(j + 1)) { // 오름차순
        change = true;
        swap(A.at(j), A.at(j + 1));
      }
    }
    if (!change) // 더 이상 swap이 일어나지 않으면 종료
      break;
  }
  return 0;
}

 

이러한 버블 정렬을 $ O(n\log(n)) $ 으로 변경할 수 있도록 한 것이 백준 1337번 문제다.

 

백준 1377번

시간 제한 : 2초

메모리 제한 : 128 MB

 

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<pair<int, int>> A(N, {0, 0}); // 데이터 값, 각 배열의 인덱스를 저장
  for (int i = 0; i < N; i++) {
    cin >> A.at(i).first; // 값 저장
    A.at(i).second = i; // 값에 해당하는 인덱스를 저장
  }

  sort(A.begin(), A.end()); // 정렬

  int max = -1;
  for (int i = 0; i < N; i++) {
    if (max < A.at(i).second - i) // 정렬된 인덱스 - 현재 인덱스 = swap 된 횟수
      max = A.at(i).second - i; // swap 된 횟수의 최대 값 찾기
  }
  cout << max + 1 << endl; // swap 된 횟수 + 1 이 최종 출력

  return 0;
}

 

이 문제는 버블 정렬이 진행된 수 + 1을 출력하는 것인데, 이는 swap 연산이 진행된 횟수 + 1 과 같다.

또한, swap 연산이 진행된 횟수 = $ max(버블\ 정렬된\ 인덱스 - 현재\ 인덱스) $ 이므로 시간 복잡도를 $ O(n^{2}) $ 가 아닌 $ O(n\log(n)) $ 으로 푸는 문제였다.

 

버블 정렬의 핵심은 두 가지다.

첫 째, 인접한 두 값끼리 비교하여 swap 연산을 통해 정렬 진행 - 시간 복잡도 $ O(n^{2}) $

둘 째, 버블 정렬이 진행된 수 = swap 연산이 진행된 횟수 = $ max(버블\ 정렬된\ 인덱스 - 현재\ 인덱스) $