[C++ 자/알 Note] 정렬 - 버블, 선택, 삽입

버블정렬

버블정렬의 핵심은 순서대로 앞뒤로 비교해 가며

정렬을 진행을 하는 것이다

 

버블정렬 예시

 

버블정렬 구현

void BubbleSort(vector<int>& v)
{
	const int n = (int)v.size();

	// (N-1) + (N-2) + ... + 2 + 1
	// 등차수열의 합 = N * (N-1) / 2
	// O(N^2)
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < (n - 1 - i); j++)
		{
			if (v[j] > v[j + 1])
			{
				int temp = v[j];
				v[j] = v[j + 1];
				v[j + 1] = temp;
			}
		}
	}
}

 

---

 

선택정렬

선택정렬의 핵심은 순회하면서 가장 최소값을 찾아내서

정렬을 진행하는 것이다

 

선택정렬 예시

선택정렬 구현

void SelectionSort(vector<int>& v)
{
	const int n = (int)v.size();

	// O(N^2)
	for (int i = 0; i < n - 1; i++)
	{
		int bestIdx = i;

		for (int j = i + 1; j < n; j++)
		{
			if (v[j] < v[bestIdx])
				bestIdx = j;
		}

		// 교환
		int temp = v[i];
		v[i] = v[bestIdx];
		v[bestIdx] = temp;
	}
}

 

---

 

삽입정렬

삽입정렬의 핵심은 값을 하나씩 추가해 가며

본인이 들어갈 위치에 들어가는 것이다

 

삽입정렬 예시

 

삽입정렬 구현

void InsertionSort(vector<int>& v)
{
	const int n = (int)v.size();

	// O(N^2)
	for (int i = 1; i < n; i++)
	{
		int insertData = v[i];

		int j;
		for (j = i - 1; j >= 0; j--)
		{
			if (v[j] > insertData)
				v[j + 1] = v[j];
			else
				break;
		}

		v[j + 1] = insertData;
	}
}

 

---

정렬 시/공간복잡도

버블, 선택, 삽입은 모두 시간복잡도는 평균 O(N^2)이고

공간복잡도는 O(1)이다