220420_정렬_힙정렬, 퀵정렬, 병합정렬 성능 비교

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

https://hyrule.tistory.com/62

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

 

https://hyrule.tistory.com/64

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

 

https://hyrule.tistory.com/66

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

 

 

* 시간을 측정하기 위해 time.h와 windows.h가 필요하다.

//PerformanceTest.cpp
//기존의 main.cpp를 컴파일에서 제외하고 실행할 것.

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

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


bool SortFunc(const int& a, const int& b)
{
	return a < b;
}


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();
	}



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

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


	//측정 준비
	LARGE_INTEGER	StartTime = {};
	LARGE_INTEGER	Second = {};
	LARGE_INTEGER	EndTime = {};


	//타이머의 초당 진동수를 등록
	QueryPerformanceFrequency(&Second);

	//타이머의 시작 타임을 기록
	QueryPerformanceCounter(&StartTime);

	//삽입 후 추출
	for (int i = 0; i < TotalNumbers; ++i)
	{
		HeapSortTest->push(TestArr[i]);
	}
	for (int i = 0; i < TotalNumbers; ++i)
	{
		HeapSortTest->Pop();
	}

	//타이머의 종료 타임을 기록
	QueryPerformanceCounter(&EndTime);

	//기록 출력: {(종료시각) - (시작시각)} / 초당 진동수 
	float	Result = (EndTime.QuadPart - StartTime.QuadPart) / (float)Second.QuadPart;
	std::cout << "* Heap Sort Speed: " << Result << std::endl;
	////////////////////////////////////////////////////


	//2. Quick Sort 작동 테스트 ///////////////
	CQuickSort<int>* QuickSortTest = new CQuickSort<int>;
	QuickSortTest->SetSortFunction(SortFunc);
	QuickSortTest->push(TestArr, TotalNumbers);


	QueryPerformanceCounter(&StartTime);
	QuickSortTest->Sort();
	QueryPerformanceCounter(&EndTime);

	Result = (EndTime.QuadPart - StartTime.QuadPart) / (float)Second.QuadPart;
	std::cout << "* Quick Sort Speed: " << Result << std::endl;
	//////////////////////////////////////////


	////////// 합병 정렬 테스트 ////////////
	CMergeSort<int>* MergeSortTest = new CMergeSort<int>;
	MergeSortTest->SetSortFunction(SortFunc);
	MergeSortTest->push(TestArr, TotalNumbers);


	QueryPerformanceCounter(&StartTime);
	MergeSortTest->Sort();
	QueryPerformanceCounter(&EndTime);


	Result = (EndTime.QuadPart - StartTime.QuadPart) / (float)Second.QuadPart;
	std::cout << "* Merge Sort Speed: " << Result << std::endl;
	//////////////////////////////////////////


	////추가: 버블정렬?
	////이걸 실행시킬때는 높은 수를 입력하지 말것(오래걸림)
	//QueryPerformanceCounter(&StartTime);

	//for (int i = 0; i < TotalNumbers - 1; ++i)
	//{
	//	for (int j = i + 1; j < TotalNumbers; ++j)
	//	{
	//		if (TestArr[i] > TestArr[j])
	//		{
	//			int Temp = TestArr[i];
	//			TestArr[i] = TestArr[j];
	//			TestArr[j] = Temp;
	//		}
	//	}
	//}
	//QueryPerformanceCounter(&EndTime);

	//Result = (EndTime.QuadPart - StartTime.QuadPart) / (float)Second.QuadPart;

	//std::cout << Result << std::endl;
	/////////////////////////////////


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

 

* 일반적으로 퀵정렬이 병합정렬보다 속도가 좀 더 빠른 편이라고 하는데 내가 짠 코드의 경우 크게 차이가 났다.

* 왜 그런지 알아봐야 할듯