* 퀵 정렬 이론과 예시를 토대로 구현
* 여기서 나온 과정과 약간 다르게 구현함
//QuickSort.h
/*
<퀵 정렬>
* 비대칭 정렬
* 최선의 경우에는 가장 빠른 성능을 가지지만
* 최악의 경우에는 매우 느리다.
* 과정 요약
7 9 5 1 3 6 4
Pivot(중심점)을 하나 정함 -> (일반적으로 맨 앞 자리)7
Pivot보다 작은 건 왼쪽, Pivot보다 큰 건 오른쪽
Pivot: 7
5 1 3 6 4 7 9
* Pivot 7 기준 왼쪽 배열부터 정렬(1, 3, 4, 5, 6만 놓고 정렬)
다시 Pivot 설정 -> 5(맨 앞자리)
1 3 4 5 6 7 9
다시 Pivot 설정 -> 1
정렬 필요 없음
다시 Pivot 설정 -> 3
정렬 필요 없음
다시 Pivot 설정 -> 4
정렬 필요 없음
다시 Pivot 설정 -> 5
정렬 필요 없음
* 7 기준 왼쪽 배열 왼쪽부터 정렬 끝. 오른쪽부터 정렬 시작.
Pivot: 6
정렬되어 있음.
* 7 기준 오른쪽 배열 정렬 시작
9밖에 없음 -> 정렬 끝.
*/
#pragma once
template <typename T>
class CQuickSort
{
public:
CQuickSort() :
m_Size(0),
m_Capacity(4)
{
m_Data = new T[m_Capacity];
}
~CQuickSort()
{
delete[] m_Data;
}
private:
int m_Size;
int m_Capacity;
T* m_Data;
bool (*m_Func)(const T&, const T&);
public:
void SetSortFunction(bool (*Func)(const T&, const T&))
{
m_Func = Func;
}
void push(const T& Data)
{
//용량이 꽉 차면 배열의 크기를 늘려주는 함수 구현
if (m_Size == m_Capacity)
{
m_Capacity *= 2;
T* Temp = new T[m_Capacity];
for (int i = 0; i < m_Size + 1; ++i)
{
Temp[i] = m_Data[i];
}
delete[] m_Data;
m_Data = Temp;
}
//배열의 크기가 충분하면 들어온 데이터를 추가
m_Data[m_Size] = Data;
//사이즈 1 증가
++m_Size;
}
//배열을 받는 함수
void push(T* Array, int Count)
{
if (m_Capacity < Count)
{
m_Capacity = Count;
T* Temp = new T[m_Capacity];
delete[] m_Data;
m_Data = Temp;
m_Size = 0;
}
for (int i = 0; i < Count; ++i)
{
m_Data[i] = Array[i];
}
m_Size = Count;
}
int size() const
{
return m_Size;
}
bool empty() const
{
return m_Size == 0;
}
//인자로 들어온 배열에 클래스에 등록된 배열을 옮겨주는 함수
void GetArray(T* Arr, int Count)
{
if (Count < m_Size)
{
std::cout << "Not enough Array Size!!" << std::endl;
return;
}
memcpy(Arr, m_Data, sizeof(T) * m_Size);
/*for (int i = 0; i < m_Size; ++i)
{
Arr[i]87yu6i = m_Data[i];
}*/
}
//CLEAR 함수
void Clear()
{
delete[] m_Data;
m_Capacity = 4;
m_Data = new T[m_Capacity];
m_Size = 0;
}
void Sort()
{
Sort(0, m_Size - 1);
}
private:
void Sort(int Left, int Right)
{
//왼쪽 인덱스가 오른쪽 인덱스보다 작은지 확인해준다.
if (Left < Right)
{
//피벗(중심점)을 Partition 함수를 통해 구해준다.
//Partition 함수에서는
//맨 왼쪽 값을 Pivot으로 설정하여
//해당 값을 정렬되었을때 들어가야 할 위치에 삽입하고
//그 위치를 반환해 준다.
//ex) 3 1 2 4
//3 4 -> Pivot으로 설정
//정렬 -> 2 1 3 4
//3의 인덱스 2를 반환
//쉽게 말해, Partition은 Pivot을 설정하여
//해당 값을 정렬된 위치에 넣은 뒤
// 그 위치를 반환해주는 함수이다.
//그러므로 해당 값은 더이상 건드릴 필요가 없다.
int Pivot = Partition(Left, Right);
//만든 피벗 기준 좌우로 정렬을 재귀 호출하여 시행한다.
Sort(Left, Pivot - 1);
Sort(Pivot + 1, Right);
}
}
int Partition(int Left, int Right)
{
//Pivot을 설정한다(맨 왼쪽 숫자로)
T PivotValue = m_Data[Left];
//Pivot 값은 제외하고 비교한다.
//그러므로 Left와 Low는 +1을 해준다.(피벗 값을 맨 왼쪽으로 설정했으므로)
int left = Left + 1;
int right = Right;
int Low = Left + 1;
int High = Right;
while (Low <= High)
{
//아직 Low값이 오른쪽 끝에 도달하지 았았고,
//비교를 헀을때 true가 나오면,(정렬 기준에 부합하면)
//정렬 기준에 부합하여 정렬할 필요가 없으므로
//Low 값을 하나 올려준다.
while (Low <= right && m_Func(m_Data[Low], PivotValue))
{
++Low;
}
//오른쪽은 방향과 비교기준 모두 반대로 돌려준다.
//피벗은 제외해야 한다.
while (High >= left && m_Func(PivotValue, m_Data[High]))
{
--High;
}
//이 단계가 끝나면, 좌우 포인터의 이동이 모두 정지했다는 뜻임.
//피벗이 멈춘 위치에 따라서 결과를 처리한다.
//만약 Low > High 일 경우(양 포인터가 서로 교차해서 지나쳤을 경우)
//모두 규칙에 부합되었다는 뜻이므로
//최종적으로 PivotValue를 High와 바꿔 준다.
//PivotValue는 그럼 최종 정렬된 위치에 들어간 것이다.
if (Low > High)
{
T Temp = m_Data[Left];
m_Data[Left] = m_Data[High];
m_Data[High] = Temp;
}
//아직 Low가 High와 교차하지 않았다는 것은
//중간에 Low나 High가 정렬되지 않은 숫자에서 멈추었다는 뜻이다.
//이 경우 두 값을 서로 바꾸어 준다.
else
{
T Temp = m_Data[Low];
m_Data[Low] = m_Data[High];
m_Data[High] = Temp;
}
}
return High;
////do-while문을 사용하는 선생님 코드.
//do
//{
// do
// {
// ++Low;
// //무조건 1회는 실행한다.
// } while (Low <= Right && m_Func(PivotValue, m_Data[Low]));
//
// //
// //쉽게 생각해서
// //왼쪽부터 하나하나 차례대로 PivotValue와 비교하여
// //내림차순 or 오름차순 기준에 맞게 정렬이 되어 있다면
// //해당 값은 넘어간다.
// //정렬이 되지 않았다면, 그 값에서 멈춘다.
// do
// {
// --High;
// } while (High >= Left && m_Func(m_Data[High], PivotValue));
// //마찬가지로 오른쪽도 반대 방향으로 하나하나 확인한다.
// if (Low < High)
// {
// //만약 Low가 High보다 작다면,
// //중간에 PivotValue를 기준으로 정렬이 되지 않은 수가 있다는 것이다.
// //그럼 Low와 High의 값을 교체해 준다.
// T Temp = m_Data[Low];
// m_Data[Low] = m_Data[High];
// m_Data[High] = Temp;
// }
//} while (Low < High);
////do-while문이 끝났다는 것은 PivotValue를 기준으로 좌우 정렬이 끝났다는 의미이다.
////그럼 m_Data[Left](==PivotValue)를 High의 위치와 바꾸면
////피벗 값은 정렬된 위치에 들어가게 된다.
//T Temp = m_Data[Left];
//m_Data[Left] = m_Data[High];
//m_Data[High] = Temp;
//return High;
}
};
'C++기초' 카테고리의 다른 글
220420_정렬_병합 정렬(Merge Sort) 구현 (0) | 2022.04.27 |
---|---|
220420_정렬_병합정렬(Merge Sort) 알고리즘 (0) | 2022.04.27 |
220420_정렬_퀵 정렬(Quick Sort) 이론 (0) | 2022.04.27 |
220420_정렬_힙 정렬(Heap Sort) 구현 (0) | 2022.04.27 |
220420_정렬_힙 정렬(Heap Sort) 처리 과정 (0) | 2022.04.27 |