둥지/알고리즘
퀵 정렬
by 까닭
2023. 2. 26.
#include <iostream>
#include <vector>
template<typename T>
class DataManager
{
public:
DataManager() {};
DataManager(size_t _Size)
{
Datas.resize(_Size);
};
~DataManager() {};
void Swap(T& _Left, T& _Right)
{
T Temp(_Left);
_Left = _Right;
_Right = Temp;
}
size_t Partition(size_t _Left, size_t _Right)
{
T Pivot = Datas[_Left];
size_t Low = _Left;
size_t High = _Right;
while (Low < High)
{
while (Pivot < Datas[High])
{
--High;
}
while (Low < High && Pivot >= Datas[Low])
{
++Low;
}
Swap(Datas[Low], Datas[High]);
}
Datas[_Left] = Datas[Low];
Datas[Low] = Pivot;
return Low;
}
//분할 정복 방식
void QuickSort(size_t _Left, size_t _Right)
{
if (_Right <= _Left)
{
return;
}
size_t Pivot = Partition(_Left, _Right);
QuickSort(_Left, Pivot - 1);
QuickSort(Pivot + 1, _Right);
}
size_t Size()
{
return Datas.size();
}
public:
std::vector<T> Datas;
};
int main()
{
DataManager<int> Manager(5);
for (size_t i = 0; i < Manager.Size(); ++i)
{
std::cin >> Manager.Datas[i];
}
Manager.QuickSort(0, Manager.Size() - 1);
for (size_t i = 0; i < Manager.Size(); ++i)
{
std::cout << Manager.Datas[i];
}
return 0;
}