버블 정렬

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

•

간단하게 구현할 수 있다.

•

시간복잡도는 O(n²) 으로 다른 정렬 알고리즘보다 속도가 느리다.

•

인접한 데이터 간의 swap 연산으로 정렬한다.

•

만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면

•

그 영역 뒤에 있는 데이터가 모두 정렬되었다는 뜻이므로 프로세스를 종료해도 된다.

bool change = false;

for (int i = 1; i <= N + 1; i++) {
  change = false;
  for (int j = 1; j <= N - 1; j++) {
    if(A[j] > A[j + 1]) {
      change = true;
      swap(A[j], A[j + 1]);
    }
  }
  if(change == false) {
    cout << i << endl;
    break;
  }
}
C++
복사
버블 정렬 예제 코드

버블 정렬 심화

•

먼저 sort 함수로 정렬 후

•

정렬 전 index 값에서 정렬 후 index 값을 뺀 후 최댓값을 찾은 후

•

swap이 일어나지 않은 반복문이 한 번 더 실행되는 것을 감안해 1을 더하는 것을 통해

•

정렬이 될 때 까지의 루프가 몇 번이 돌았는지 알 수 있다.

•

구현 코드는 아래와 같다. (백준 1377)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  cin.tie(NULL);
  cout.tie(NULL);
  ios::sync_with_stdio(false);

  int N;
  cin >> N;
  vector<pair<int, int>> A(N);

  for (int i = 0; i < N; i++) {
    cin >> A[i].first;
    A[i].second = i;
  }

  sort(A.begin(), A.end());

  int Max = 0;
  for(int i = 0; i < N; i++) {
    if(Max < A[i].second - i) {
      Max = A[i].second - i;
    }
  }

  cout << Max + 1 << endl;
}
C++
복사