[백준][알고리즘][C++] 2750 수 정렬하기, 버블 정렬, 삽입 정렬

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

2750번: 수 정렬하기

 

 

 

1) 버블 정렬 알고리즘(Bubble sorting)

 

 

버블 정렬은 인접한 두 원소를 비교하여 자리를 교환해가는 알고리즘이다.

시간 복잡도는 O(n^2) (이중 for루프)

 

 

#include <iostream>
#include <vector>

using std::vector;

int main()
{
	int n;
	std::cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; ++i)
	{
		std::cin >> arr[i];
	}
	int temp;
	for (int j = 0; j < n - 1; ++j)
	{
		for (int i = 0; i < n - j - 1; ++i)
		{
			if (arr[i] > arr[i + 1])
			{
				temp = arr[i + 1];
				arr[i + 1] = arr[i];
				arr[i] = temp;
			}
		}
	}
	for (int i = 0; i < n; ++i) std::cout << arr[i] << '\n';
}

 

 

 

---

 

2) 삽입 정렬 알고리즘(Insertion sorting)

 

 

2번째 원소부터 시작하여 왼쪽의 원소들과 비교하며 알맞은 위치에 삽입시킨다. 

 

i번째 원소를 삽입시키려면 그 원소의 값을 temp에 따로 저장한 뒤, i-1번째 원소부터 비교해가며, temp가 i-1번째 원소보다 작으면 i-1번째 원소를 오른쪽으로 미룬다.(어차피 i번째 원소는 따로 저장해 뒀으니)

i-2, i-3과 같이 줄여나가다가 0번째 원소가 되거나 temp보다 더 작은 원소를 만나면 오른쪽으로 미루는 것을 멈추고 해당 자리에 temp를 끼워넣는다. 

 

시간 복잡도는 최악의 경우 O(n^2)이며, 최선의 경우 O(n)이다.

 

 

#include <iostream>
#include <vector>

using std::vector;

int main()
{
	int n;
	std::cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; ++i)
	{
		std::cin >> arr[i];
	}
	int temp;
	for (int i = 1; i < n; ++i)
	{
		temp = arr[i];
		int j;
		for (j = i - 1; j >= 0 && temp < arr[j]; --j)
		{
			arr[j + 1] = arr[j];
		}
		arr[j + 1] = temp;
	}

	for (int i = 0; i < n; ++i) std::cout << arr[i] << '\n';
}