220420_정렬_병합 정렬(Merge Sort) 구현

* 저번에 그려본 알고리즘 순서를 토대로 구현

https://hyrule.tistory.com/65

220420_정렬_병합정렬(Merge Sort) 알고리즘

 

/*

[분할 정렬 / 합병 정렬]

* 이 정렬방식은 속도가 빠른 대신, 공간이 두 배 필요하다.
* 먼저 분할부터 한 후, 다시 병합하면서 정렬하는 과정을 가진다.
* 이 때, 정렬된 데이터를 복사본에 저장하기 때문에 새 공간이 필요한 것이다.
* 분할-정복 알고리즘
* 오름차순 정렬 예시
8 3 5 9 1 6 7

8 3 5 9		1 6 7

8 3		5 9		1 6		7

8	3	5	9	1	6	7

3 8		5 9		1 6		7
↑		↑
* 3 5 비교 -> 3이 더 작으므로 3을 배열에 등록하고
포인터를 이동
3

3 8		5 9		1 6		7
  ↑		↑
* 8 5 비교 -> 5가 더 작으므로 5를 배열에 등록하고
포인터를 이동
3 5

3 8		5 9		1 6		7
  ↑		  ↑
* 8 9 비교 -> 8이 더 작으므로 8을 배열에 등록하고
포인터를 이동
3 5 8 

* 마지막 포인터를 등록
3 5 8 9
 

* 1 6 / 7도 같은 순서로 비교해줌 -> 1 6 7


3 5 8 9		1 6 7

* 3 1 비교: 스왑 -> 1 5 8 9		3 6 7
	- 스왑이 일어났으므로 바로 통과
* 5 3 비교: 스왑 -> 1 3 8 9		5 6 7
	- 스왑이 일어났으므로 마찬가지로 통과.
*/



#pragma once
#include <iostream>

template <typename T>
class CMergeSort
{

public:
	CMergeSort() :
		m_Size(0),
		m_Capacity(4)
	{
		m_Data = new T[m_Capacity];

	}
	~CMergeSort()
	{
		delete[] m_Data;
	}

private:
	int m_Size;
	int m_Capacity;
	T* m_Data;
	
	//sort를 시행할 경우 만들 복사본 저장용
	T* m_CopyData;
	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] = m_Data[i];
		}*/
	}

	//CLEAR 함수
	void Clear()
	{
		delete[] m_Data;
		m_Capacity = 4;
		m_Data = new T[m_Capacity];
		m_Size = 0;
	}
	
	void Sort()
	{
		m_CopyData = new T[m_Size];

		

		Divide(0, m_Size - 1);

		delete m_Data;
		m_Data = m_CopyData;
		m_CopyData = nullptr;
	}

private:
	//분할 -> 합병 함수
	void Divide(int Left, int Right)
	{
		if (Left < Right)
		{
			int Mid = (Right + Left) / 2;

			Divide(Left, Mid);
			Divide(Mid + 1, Right);

			Merge(Left, Mid, Right);
		}

	}

	void Merge(int Left, int Mid, int Right)
	{
		//복사본 배열에 데이터가 들어가야 할 곳 위치 저장
		int Pivot = Left;

		//병합될 왼쪽 배열의 시작 지점
		int LeftArrIndex = Left;

		//병합될 오른쪽 배열의 시작 지점
		int RightArrIndex = Mid + 1;

		//좌우 배열의 시작지점이 각 배열의 끝을 넘지 않고,
		while (LeftArrIndex <= Mid && RightArrIndex <= Right)
		{
			//비교 함수에 집어넣었을때
			//정렬 기준에 부합하면(True) 
			if (m_Func(m_Data[LeftArrIndex], m_Data[RightArrIndex]))
			{
				m_CopyData[Pivot] = m_Data[LeftArrIndex];
				++LeftArrIndex;
			}
			else
			{
				m_CopyData[Pivot] = m_Data[RightArrIndex];
				++RightArrIndex;
			}

			//피벗 값은 다음 값이 들어갈 위치에 주차
			++Pivot;
		}

		//while문을 빠져나왔으면 두 인덱스 중 하나는 
		//끝에 도달했다는 뜻
		//남은 값들을 끝까지 밀어넣어준다.
		for (; LeftArrIndex <= Mid; ++LeftArrIndex)
		{
			m_CopyData[Pivot] = m_Data[LeftArrIndex];
			++LeftArrIndex;
			++Pivot;
		}
		for (; RightArrIndex <= Right; ++RightArrIndex)
		{
			m_CopyData[Pivot] = m_Data[RightArrIndex];
			++RightArrIndex;
			++Pivot;
		}
	}
};