[자료구조&알고리즘] 버블 정렬

1. 버블 정렬

버블 정렬은 인접한 두 요소를 비교하여 필요에 따라 서로 위치를 바꾸는 방식이다. 이 알고리즘은 주어진 배열을 처음부터 끝까지 반복하여 정렬을 수행하며, 각 반복마다 가장 큰 (또는 작은) 요소가 배열의 맨 끝으로 이동하고, 이 과정을 배열이 정렬될 때까지 반복한다. 시간복잡도는 O(n^2)으로 다른 알고리즘보다 속도가 느리다. 

 

2. 구현 방식

데이터의 인접 요소끼리 비교하고, swap 연산을 수행하여 진행한다. 

만약 특정한 루프의 전체 영역에서 swap이 한번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료해도 된다. 

 

3. 문제 예제

3.1 백준 1377번

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

 

 

 

3.1.1 구현 방식

1) 주어진 배열을 이중 for문을 통해 처음부터 끝까지 연산을 수행한다면 시간복잡도가 O(n^2)으로 크기 때문에 우선 라이브러리 제공 정렬 함수(sort)를 이용해 nlog(n)의 시간복잡도로 데이터를 정렬한다.

2) 인덱스를 정렬 전과 후로 나눠 저장한다.

3) 인덱스의 차이를 구하고 각 차이만큼 정렬이 일어났기 때문에 정렬이 완료된 1번의 횟수까지 더하면 총 정렬시도의 횟수를 구할 수 있다.

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

using namespace std;

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

	int N;
	cin >> N;

	//value, index
	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++)
	{
		//정렬 전 index - 정렬 후 index
		if (Max < A[i].second - i)
			Max = A[i].second - i;
	}

	cout << Max + 1;
}