C++ / 백준 / 1517 / 버블 소트

문제

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

1517번: 버블 소트

문제풀이

버블 소트는 https://terms.naver.com/entry.naver?docId=2270437&cid=51173&categoryId=51173 

버블 정렬

오름차순으로 정렬할 때, 맨 앞 인덱스부터 뒤로 가면서 값을 비교하고 값이 작은 수를 발견하면 바꾸고, 아니면 멈춘다.

다시 처음으로 가 정렬이 될 때까지 계속 반복하는 정렬이다.

버블 소트: O(n^2)

합병 정렬: O(n log n)의 시간 복잡도를 가진다.

이 문제를 버블 소트를 하면서 바꾸는 개수를 세게 되면 시간 초과가 나게 된다.

그러므로 합병 정렬을 이용하여, 숫자를 바꾸는 개수를 세면 된다.

else if (Arr[i] > Arr[j]) {
			if (Arr[mid] > Arr[j]) cnt += (mid - i + 1);

합병 정렬 코드에서 왼쪽 부분과 오른쪽 부분을 비교할 때, 왼쪽 부분이 더 크면 i부터 mid번째까지의 개수를 cnt에 더한다.

합병 정렬은 수가 모두 분해되고 모일 때마다 정렬을 하므로 왼쪽 부분과 오른쪽 부분은 각각 정렬이 되어있는 상태이다.

 

i가 0이고 j가 3이면 Arr[0]=1, Arr[3]=4이다.

1 <4이므로 swap을 하지 않으므로 패스,

i가 1이면 Arr[1]=5, 5>4이므로 swap을 하게 된다.

당연히 각각 배열은 정렬이 되어있으므로 i가 mid까지는 모두 4보다 큰 수들만 있기 때문에

i부터 mid번째까지의 개수인 mid-i+1 값을 swap개수에 더하면 된다.

 

코드

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

vector<long long>Arr;
vector<long long>temp;

long long cnt = 0;
void Merge(int start, int end) {
	if (start == end) return;
	int mid =(start + end) / 2;
	int i = start, j = mid + 1, now = start;
	while (now <= end) {
		if (i > mid)
			temp[now] = Arr[j++];
		else if (j > end)
			temp[now] = Arr[i++];
		else if (Arr[i] <= Arr[j])
			temp[now] = Arr[i++];
		else if (Arr[i] > Arr[j]) {
			if (Arr[mid] > Arr[j]) cnt += ((long long)mid - i + 1);
			temp[now] = Arr[j++];
		}
		now++;
	}
	for (now = start; now <= end; ++now)
		Arr[now] = temp[now];
}

void MergeSort(int start, int end) {
	if (start >= end) return;
	else {
		int mid = (start + end) / 2;
		MergeSort(start, mid);
		MergeSort(mid + 1, end);
		Merge(start, end);
	}
}

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

	int N = 0;
	int idx = 0;
	cin >> N;

	Arr = vector<long long>(N, 0);
	temp = vector<long long>(N, 0);
	for (idx = 0; idx < N; ++idx)
		cin >> Arr[idx];
	MergeSort(0, N - 1);
	cout << cnt;
}