버블정렬과 삽입정렬

<헤더파일>

#pragma once
#include <Windows.h>

class Timer
{
public:

	Timer()
	{
		QueryPerformanceFrequency(&tick);
	}
	~Timer()
	{

	}

	void Start()
	{
		QueryPerformanceCounter(&start);
	}

	void End()
	{
		QueryPerformanceCounter(&end);
	}

	float Return_Function()
	{
		return (float)(end.QuadPart - start.QuadPart) / (tick.QuadPart / 1000.f);
	}


private:
	LARGE_INTEGER tick;
	LARGE_INTEGER start, end;
};

<cpp파일>

#include <stdio.h>
#include "Timer.h"

void BubbleSort(int* data, int length)
{	// 매개변수를 데이터셋의 포인터와 배열의 길이로 들고옴
	for (int i = 0; i < length - 1; i++)
	{	// 배열은 0부터 시작하지만, 길이는 1부터 시작하기 때문에 length - 1 을 해준다.
		for (int j = 0; j < length - i - 1; j++)
		{	// i값이 증가함에 따라, length 에서 i를 빼주며, 길이가 1부터 시작하기에 뒤에 1을 더해줌
			if (data[j] > data[j + 1])
			{	// 오름차순으로 정렬할거기 때문에, 앞에 있는 수가 더 크게 되면 바꿔줘야 한다.
				int temp = data[j];
				data[j] = data[j + 1];
				data[j + 1] = temp;
			}
		}
	}
}

void InsertSort(int* data, int length)
{
	// 5, 1, 6, 4, 2, 3
	// 1, 5, 6, 4, 2, 3
	// 1, 5, 6, 4, 2, 3
	// 1, 4, 5, 6, 2, 3
	// 1, 2, 4, 5, 6, 3
	// 1, 2, 3, 4, 5, 6
	for (int i = 1; i < length; i++)
	{
		// 두번째 원소부터 시작함
		if (data[i] >= data[i - 1])
			continue;
		// 해당 원소는 바로 직전 원소랑 비교를 하여 오름차순으로 정렬이 되어있다면
		// 넘어간다.

		int value = data[i];
		// 만약에 오름차순으로 정렬이 되어있지 않고 뒤가 앞보다 작으면..
		// 뒤에있는 원소를 value로 빼버리고

		for (int j = 0; j < i; j++)
		{	// j < i  -> 맨앞에있는 원소부터 뺀거의 전까지 비교를 해야 함
			if (data[j] >= value)
			{	// 예를들어 1, 5, 6, 4, 2, 3 이있는데..
				// 4를 뽑아 버리고
				// 1, 5, 6, 2, 3 에서
				// 4는 1, 5, 6 이랑 비교를 하게 되는데
				// j가 0부터 for문으로 증가하기에
				// 1이랑 비교했는데 4가 더커 그럼 pass
				// 5랑비교했는데 4가 더 작아...
				// 그러면 뽑아버린 4를 5의 앞에 넣어야지
				// 5는 for문에서 증가했던 j이기 때문에,,
				memmove(&data[j], &data[j + 1], sizeof(data[0]) * (i - j));
				// 4는 j번째 원소에 박아주고, 5는 그다음이므로 j + 1번째의 원소로 옮겨줘야 한다.
				value = data[j];
				// data[j]는 4가 되었기 때문에... value로 다시 박아줘야지..
				break;
			}
		}
	}
}

void main()
{
	Timer timer;


	// Bubble
	{
		int data[] = { 5, 1, 6, 4, 2, 3 };
		// 5, 1, 6, 4, 2, 3 을 버블정렬로 오름차순을 해보자..
		int length = sizeof(data) / sizeof(data[0]);
		// dataset = 24(원소가 6개) / dataset[0] = 4(원소 하나는 int형이므로 4바이트)

		printf("버블 정렬\n");

		printf("원래의 데이터 배열 : ");
		for (int i = 0; i < length; i++)
		{
			printf("%d ", data[i]);
		}
		printf("\n");

		timer.Start();
		BubbleSort(data, length);
		// 버블 정렬 실행
		timer.End();

		printf("데이터 배열 : ");
		for (int i = 0; i < length; i++)
		{
			printf("%d ", data[i]);
		}
		printf("\n");

		printf("걸리는 시간 : %f", timer.Return_Function());

		printf("\n\n");
	}

	// Insert
	{
		int data[] = { 5, 1, 6, 4, 2, 3 };
		// 5, 1, 6, 4, 2, 3 을 버블정렬로 오름차순을 해보자..
		int length = sizeof(data) / sizeof(data[0]);
		// dataset = 24(원소가 6개) / dataset[0] = 4(원소 하나는 int형이므로 4바이트)
		
		printf("삽입 정렬\n");

		printf("원래의 데이터 배열 : ");
		for (int i = 0; i < length; i++)
		{
			printf("%d ", data[i]);
		}
		printf("\n");

		timer.Start();
		InsertSort(data, length);
		// 버블 정렬 실행
		timer.End();

		printf("데이터 배열 : ");
		for (int i = 0; i < length; i++)
		{
			printf("%d ", data[i]);
		}
		printf("\n");

		printf("걸리는 시간 : %f", timer.Return_Function());

		printf("\n\n");

	}
}

<실행결과>