C++기초

220420_정렬_힙 정렬, 퀵 정렬, 병합 정렬 실행

hyrule 2022. 4. 27. 15:25

* 필요 헤더: 힙 정렬, 퀵 정렬, 병합 정렬

https://hyrule.tistory.com/62

 

220420_정렬_힙 정렬(Heap Sort) 구현

* 처리 과정을 바탕으로 구현해 보았음 https://hyrule.tistory.com/61 220420_정렬_힙 정렬(Heap Sort) 처리 과정 hyrule.tistory.com //HeapSort.h /* <힙 정렬> * 힙정렬은 최대힙과 최소힙이 있다. - 최대힙으..

hyrule.tistory.com

 

https://hyrule.tistory.com/64

 

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

* 퀵 정렬 이론과 예시를 토대로 구현 * 여기서 나온 과정과 약간 다르게 구현함 https://hyrule.tistory.com/63 220420_정렬_퀵 정렬(Quick Sort) 이론 hyrule.tistory.com //QuickSort.h /* <퀵 정렬> * 비대칭..

hyrule.tistory.com

 

https://hyrule.tistory.com/66

 

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

* 저번에 그려본 알고리즘 순서를 토대로 구현 https://hyrule.tistory.com/65 220420_정렬_병합정렬(Merge Sort) 알고리즘 hyrule.tistory.com /* [분할 정렬 / 합병 정렬] * 이 정렬방식은 속도가 빠른 대신, 공..

hyrule.tistory.com

 

#include <iostream>
#include <time.h>

#include "HeapSort.h"
#include "QuickSort.h"
#include "MergeSort.h"


//정렬 기준에 부합하면 true를 반환하는 함수.
//오름차순 정배열이면 true를 반환.
bool SortFunc(const int& a, const int& b)
{
	return a >= b;
}

void OriginalArrayOutput(int* Arr, int Size)
{
	std::cout << "< Original Array >" << std::endl;
	for (int i = 0; i < Size; ++i)
	{
		std::cout << " " << Arr[i] << std::endl;
	}

	std::cout << "* Total Size: " << Size << std::endl;
	std::cout << std::endl;
}


int main()
{
	srand((unsigned int)time(0));
	rand();

	int TotalNumbers = 0;
	while (TotalNumbers == 0)
	{
		std::cout << "* 원소 갯수 입력\n>>> ";
		std::cin >> TotalNumbers;
	}

	//값을 역순으로 저장하고, 정상적으로 저장되는지 확인.
	int* TestArr = new int[TotalNumbers];
	for (int i = 0; i < TotalNumbers; ++i)
	{
		//역순
		//TestArr[i] = TotalNumbers - i;

		//랜덤
		TestArr[i] = rand();
	}

	//일부러 중복된 값을 넣어 중복된 값이 있을 때도 잘 동작하는지 확인.
	TestArr[rand() % TotalNumbers] = TestArr[rand() % TotalNumbers];
	TestArr[rand() % TotalNumbers] = TestArr[rand() % TotalNumbers];


	//QuickSort, MergeSort 결과를 저장할 배열
	int* ResultArr = new int[TotalNumbers];



	//1. HeapSort 작동 테스트///////////////////
	CHeapSort<int>* HeapSortTest = new CHeapSort<int>;

	//HeapSortTest 클래스에 대소 판별 함수를 지정
	HeapSortTest->SetSortFunction(SortFunc);

	//삽입기능 확인
	for (int i = 0; i < TotalNumbers; ++i)
	{
		HeapSortTest->push(TestArr[i]);
	}


	OriginalArrayOutput(TestArr, TotalNumbers);
	//추출했을 때 정렬되어 추출되는지 확인
	std::cout << "\n\n< Heap Sort Test >" << std::endl;
	for (int i = 0; i < TotalNumbers; ++i)
	{
		std::cout << " " << HeapSortTest->Top();
		std::cout << " / Size: " << HeapSortTest->size() << std::endl;
		HeapSortTest->Pop();
	}
	std::cout << "* Remain Size: " << HeapSortTest->size() << std::endl;
	///////////////////////////////////////////////////////////////////


	system("pause");
	system("cls");




	//2. Quick Sort 작동 테스트 ///////////////
	CQuickSort<int>* QuickSortTest = new CQuickSort<int>;

	QuickSortTest->SetSortFunction(SortFunc);

	QuickSortTest->push(TestArr, TotalNumbers);	

	QuickSortTest->Sort();

	QuickSortTest->GetArray(ResultArr, TotalNumbers);
	
	OriginalArrayOutput(TestArr, TotalNumbers);
	std::cout << "\n\n< Quick Sort Test >" << std::endl;
	for (int i = 0; i < TotalNumbers; ++i)
	{
		std::cout << " " << ResultArr[i] << std::endl;
	}
	std::cout << "* Total Size: " << QuickSortTest->size() << std::endl;
	//////////////////////////////////////////


	system("pause");
	system("cls");



	////////// 합병 정렬 테스트 ////////////
	CMergeSort<int>* MergeSortTest = new CMergeSort<int>;

	MergeSortTest->SetSortFunction(SortFunc);

	MergeSortTest->push(TestArr, TotalNumbers);

	MergeSortTest->Sort();

	MergeSortTest->GetArray(TestArr, TotalNumbers);

	OriginalArrayOutput(TestArr, TotalNumbers);
	std::cout << "\n\n< Merge Sort Test >" << std::endl;
	for (int i = 0; i < TotalNumbers; ++i)
	{
		std::cout << " " << ResultArr[i] << std::endl;
	}
	std::cout << "* Total Size: " << MergeSortTest->size() << std::endl;
	//////////////////////////////////////////


	delete[] TestArr;
	delete[] ResultArr;
	delete HeapSortTest;
	delete QuickSortTest;
	delete MergeSortTest;
	return 0;
}