Study/자료구조,알고리즘
[알고리즘] Bubble Sort와 Selection Sort 시간 비교
게임 만드는 나무꾼
2022. 10. 20. 13:25
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하다.