c언어 1377번 버블 소트 (백준)

#include <stdio.h>

typedef struct Node {
	int value;
	int index;
}Node;

Node arr[500000];
Node tmp[500000];

void merge(int l, int m, int r) {
	int i=l, j=m+1, k=l;
	while(i<=m && j<=r) tmp[k++] = (arr[i].value <= arr[j].value) ? arr[i++] : arr[j++]; 
	while(i<=m) tmp[k++] = arr[i++];
	while(j<=r) tmp[k++] = arr[j++];
	while(l<=r) {
		arr[l] = tmp[l];
		l++;
	} 
	return;
}

void mergeSort(int l, int r) {
	int m;
	if(l<r) {
		m = (l+r)/2;
		mergeSort(l, m);
		mergeSort(m+1, r);
		merge(l, m, r);
	} return;
}

int main(void) {
	int n, gap=0;
	scanf("%d", &n);
	for(int i=0; i<n; i++) {
		scanf("%d", &arr[i].value);
		arr[i].index = i;
	}
	mergeSort(0, n-1);
	for(int i=0; i<n; i++) {
		if(arr[i].index-i > gap) gap = arr[i].index-i;
	} 
	printf("%d", gap+1);
}

풀이 : stable sort (예 : mergesort)

 

문제에서 물어보는 것은

bool changed = false;
for (int i=1; i<=N+1; i++) {
    changed = false;
    for (int j=1; j<=N-i; j++) {
        if (A[j] > A[j+1]) {
            changed = true;
            swap(A[j], A[j+1]);
        }
    }
    if (changed == false) {
        cout << i << '\n';
        break;
    }
}

이러한 코드에서 i가 얼마인지, 즉 정렬하기 위해선 몇번의 for(int i=1; i<=N+1; i++)을 돌려야 하는지(i가 몇일때 반복문을 탈출하는지)에 대한 문제입니다.

(위의 버블정렬은 오름차순 정렬)

 

버블 정렬에서 최소 몇번을 돌려야 완전히 정렬되는가?

 

ex) 10 1 2 3 4

위를 정렬 했을 경우 1 2 3 4 10 이다.

for(int i=1; i<=N+1; i++)을 한번만 돌리면 정렬이 된다.

 

ex) 2 3 4 10 1

위를 정렬 했을 경우 1 2 3 4 10 이다.

for(int i=1; i<=N+1; i++)을 4번 돌려야지 1이 맨 앞으로 오게 된다.

 

위의 예를 통해 알 수 있는 것은 버블정렬은, 가장 앞에 있는 요소가, 뒤로 가야 할 때, 한 번 만 반복하면, 바로(1번) 옮길 수 있으며, 뒤에 있는 요소가 앞으로 가야할땐, 정렬하기전 위치-정렬했을 때의 위치 만큼 반복해야 함을 알 수 있다.

 

ex) 10 1 5 2 3

정렬 : 1 2 3 5 10

10을 옮기려면 1번 (정렬하기 전의 위치가 정렬했을때의 위치보다 앞에 있으니 계산하지 않아도 된다)

1을 옮기려면 1-0 1번

2을 옮기려면 3-1 2번

3을 옮기려면 4-2 2번

5을 옮기려면 2번

 

ex) 5 4 3 2 1

정렬 1 2 3 4 5

1을 옮기려면 4-0 4번

2을 옮기려면 3-1 2번

3을 옮기려면 0번

4을 옮기려면 2번

5을 옮기려면 1번

 

정렬하기전 위치 > 정렬 후 위치, 정렬 후 위치 > 정렬하기전 위치

이렇게 두가지 경우를 구해야 하나, 위의 예시를 보면

 

정렬 후 위치 > 정렬하기전 위치 인 경우의 반복 횟수 <= 정렬하기전 위치 > 정렬 후 위치 인 경우 반복 횟수

임을 알 수 있다 (이유 : 정렬 후 위치 > 정렬하기전 위치인 경우, 정렬과정에서 자신보다 앞에 있는 곳이 모두 정렬이 되었다면 다음번에 바로 정렬 후 위치로 갈 수 있으나, 정렬하기전 위치 > 정렬 후 위치 인 경우 두 위치의 차이만큼 반복해야 한다)

 

그러므로 정렬하기전 위치 > 정렬 후 위치 인 경우 만 구하면 된다.

 

ex) 1 2 2 1 처럼 값이 같으나 index가 다른 경우가 존재할 수 있기 때문에, 만약 unstable sort (ex shell sort)같은 것을 해버린다면, 1 1 2 2 이렇게 순서가 섞여버릴 수도 있다. (버블정렬은 순서가 변하지 않는 stable sort) 고로 unstable sort을 사용해서 정렬 한다음, 입력받았을 때의 index(순서)와 비교해서 그 때의 최댓값을 찾아야 한다.

 

 

 

 

---

1. 값과, 순서를 담을 구조체를 만듭니다.

2. n, 그리고 n개의 수를 입력받습니다.

3. 입력받은 것을 값을 중심으로 stable sort의 일종인 merge sort을 합니다.

4. 정렬하기전 위치 > 정렬 후 위치인 경우 중(정렬 했을 때의 index 값이 더 작은 수) 가장 차이가 큰 값을 구합니다.

5. 문제에서 주어진 코드는 i가 1부터 시작하기 때문에 가장 차이가 큰 값에 1을 더해준 뒤 출력합니다.

(ex : 구한 최댓값이 3이라면, for(int i=1; i<=N+1; i++)을 3번 돌린다음, 반복문을 종료한다는 의미하므로, i의 값은 3이 아니라 4입니다)

 

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

1377번: 버블 소트