[알고리즘] Bubble Sort와 Selection Sort 시간 비교

Bubble Sort와 Insertion Sort를 구현, 시간을 비교해봤다.

 

Bubble Sort

void BubbleSort(const vector<int>& input)
{
	cout << "After Bubble Sort : ";

	vector<int> out(input);

	chrono::system_clock::time_point start = chrono::system_clock::now();

	for (int i = 0; i < out.size(); ++i)
	{
		for (int j = 1; j < out.size() - i; ++j)
		{
			if (out[j] > out[j - 1])
			{
				swap(out[j], out[j - 1]);
			}
		}
	}

	chrono::duration<double> sec = chrono::system_clock::now() - start;

	for_each(out.begin(), out.end(), print_vec);
	cout << endl;

	cout << "Time : " << sec.count() << endl;
}

 

Selection Sort

void SelectionSort(const vector<int>& input)
{
	cout << "After Selection Sort : ";

	vector<int> out(input);

	chrono::system_clock::time_point start = chrono::system_clock::now();

	for (int i = 0; i < out.size(); ++i)
	{
		int minIdx = i;
		for (int j = i + 1; j < out.size(); ++j)
		{
			if (out[minIdx] < out[j])
			{
				minIdx = j;
			}
		}

		if (i != minIdx)
		{
			std::swap(out[i], out[minIdx]);
		}
	}

	chrono::duration<double> sec = chrono::system_clock::now() - start;

	for_each(out.begin(), out.end(), print_vec);
	cout << endl;

	cout << "Time : " << sec.count() << endl;
}

 

성능 비교

int main()
{
	std::vector<int> origin(10000);

	for (int i = 9999; i >= 0; --i)
	{
		origin[i] = i + 1;
	}

	for_each(origin.begin(), origin.end(), print_vec);
	cout << endl;

	BubbleSort(origin);
	SelectionSort(origin);

	return 0;
}

사이즈 10000의 내림차순 배열을 오름차순으로 정렬하고 비교했다.

이론적 시간복잡도는 O(n^2)으로 동일하지만, Bubble Sort가 swap을 더 많이 함으로 인해 시간이 상당히 차이가 많이 난다.

 

버블 정렬은 Stable, 선택 정렬은 Unstable하다.