220420_정렬_퀵 정렬(Quick Sort) 구현

* 퀵 정렬 이론과 예시를 토대로 구현

* 여기서 나온 과정과 약간 다르게 구현함

https://hyrule.tistory.com/63

220420_정렬_퀵 정렬(Quick Sort) 이론

 

//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;
		
	}
};