[BOJ] 백준 1517번: 버블소트

 

www.acmicpc.net/problem/1517

1517번: 버블 소트

---

문제

N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.

버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.

---

관련 글

아래 글에서 관련된 내용으로 작성한 글입니다.

2020/08/17 - [알고리즘] - 머지 소트, 머지 소트 트리 및 관련 백준 문제 풀이

머지 소트, 머지 소트 트리 및 관련 백준 문제 풀이

---

풀이.

병합 정렬의 원리를 사용하여 50만개의 데이터에 대하여 빠르게 정렬 및 교차점의 개수를 카운트할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>
using namespace std;


int mst[20][500001];
int n;
int brr[500001];
long long number_of_cross = 0;
void mergesort(int s, int e, int d) { // 시작, 끝, 깊이
	if (s == e) {
		mst[d][s] = brr[s];
		return;
	}
	int mid = (s + e) / 2;
	mergesort(s, mid, d + 1);
	mergesort(mid + 1, e, d + 1); // 절반씩 나눔
	int left = s;
	int right = mid + 1;
	int idx = s;
	while (left < mid + 1 && right < e + 1) { // 병합
		if (mst[d + 1][left] <= mst[d + 1][right]) {
			mst[d][idx] = mst[d + 1][left];
			left += 1;
			idx += 1;
		}
		else {
			number_of_cross += (mid - left + 1);
			mst[d][idx] = mst[d + 1][right];
			right += 1;
			idx += 1;
		}
	}
	while (left < mid + 1) { // 남는것 채워줌
		mst[d][idx] = mst[d + 1][left];
		left += 1;
		idx += 1;
	}
	while (right < e + 1) { // 남는것 채워줌
		mst[d][idx] = mst[d + 1][right];
		right += 1;
		idx += 1;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> brr[i];
	}
	mergesort(0, n-1, 0);
	cout << number_of_cross;
}