알고리즘...15

삽입 정렬 구현

배열 arr과 배열의 길이 n을 입력으로 받는 함수를 구현한다.

 

InsertionSort.hpp

#pragma once
#include "../Common.hpp"

/// <summary>
/// 주어진 배열을 정렬한다.
/// </summary>
/// <param name="arr">정렬을 진행할 배열</param>
/// <param name="n">배열의 길이</param>
/// <param name="printData">중간 결과 출력 여부</param>
void InsertionSort(int arr[], int n, bool printData = false)
{
	if (printData)
	{
		Common::PrintArray(arr, n);
	}

	for (int i = 1; i < n; i++)
	{
		int curIdx{ i };
		for (int j = i - 1; j >= 0; j--)
		{
			if (arr[curIdx] < arr[j])
			{
				Common::Swap(arr, curIdx, j);
				curIdx = j;
			}
			else
			{
				break;
			}
		}

		if (printData)
		{
			Common::PrintArray(arr, n);
		}
	}
}

 

arr = [ 2, 4, 6, 8, 10, 9, 7, 5, 3, 1 ], n = 10 을 입력하여 실행한 과정은 다음과 같다.

2 4 6 8 10 9 7 5 3 1
2 4 6 8 10 9 7 5 3 1
2 4 6 8 10 9 7 5 3 1
2 4 6 8 10 9 7 5 3 1
2 4 6 8 10 9 7 5 3 1
2 4 6 8 9 10 7 5 3 1
2 4 6 7 8 9 10 5 3 1
2 4 5 6 7 8 9 10 3 1
2 3 4 5 6 7 8 9 10 1
1 2 3 4 5 6 7 8 9 10

 

난수 1,000,000개에 대한 수행 시간은 다음과 같다.

total time is 313s ( 313474ms )