백준 1377 버블소트(c++)

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

1377번: 버블 소트

<코드>

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

int main()
{
	int n;
	cin>>n;
	vector<pair<int,int>>v(n);
	for(int i=0;i<n;i++)
	{
		cin>>v[i].first;
		v[i].second = i;
	}
	sort(v.begin(),v.end());
	int ans = -1;
	for(int i=0;i<n;i++)
	{
		ans = max(ans,v[i].second-i);
	}
	cout<<ans+1;
}

<풀이과정>

버블소트란 ?

인접한 원소와의 비교를 통해 더 작은 값을 한칸 앞으로 이동시키는 알고리즘이다.

한번 비교할 때 마다,  일정 크기의 배열의 최댓값이 가장 마지막 인덱스로 이동하게 된다.

정렬 전(원소 값, 인덱스 값)

10	1	5	2	3
0	1	2	3	4

정렬 후(원소 값, 인덱스 값)

1	2	3	5	10
1	3	4	2	0

 1 3 4 2 0

-0 1 2 3 4

 1 2 2 -1 -4 (각 원소가 인덱스간의 차이가 각 원소의 이동 횟수가 된다)

1은 한번 이동했고, 2는 2번, 3도 2번 이동했다. 5랑 10의 경우는 -값이 나왔는데 버블소트를 왼쪽으로 이동할 때 더 작은 값을 한칸 이동시키는 경우니까 오른쪽으로 이동하는 경우는 신경쓰지 않아도 된다.

특정 값이 몇칸 앞으로 이동했는지 확인하면 그것이 정답이 된다.

i==1                i==2 

10 1 5 2 3     1 5 2 3 10

1 10 5 2 3     1 2 5 3 10

1  5 10 2 3    1 2 3 5 10 (정렬 완료)

1  5  2 10 3

1  5  2  3  10

i==3일때는 check = false가 되기 때문에, 3을 출력해줘야 한다.

각 원소간 이동 횟수의 최댓값 + 1을 했을 경우에 각 원소가 몇 번만에 정렬을 완료했는지 알 수 있다.