정렬 알고리즘 개요

  정렬 알고리즘 

정렬이란?

n개의 원소를 순서대로 배열하는 것으로 실생활에 다양하게 사용되는 알고리즘이다. 가령 학생을 키 순서대로 줄을 세운다거나 세무서에서 고지서를 날리기 위해 주민등록 번호순으로 정렬하는 것 등을 예로 들 수 있다.

 

정렬의 종류

정렬에는 여러 종류가 있으며 대표적으로 다음과 같은 정렬이 존재한다.

• 선택 정렬 가장 큰 원소 또는 가장 작은 원소를 찾아 첫 위치 또는 마지막 위치와 자리를 바꾸는 정렬, 평균 Ο(n²)
• 버블 정렬 두 개의 원소를 비교하여 정렬 방향에 따라 서로 자리를 바꾸는 연산을 반복하는 정렬, 평균 Ο(n²)
• 병합 정렬 원소를 두 구역으로 나누는 것을 반복한 뒤 병합하며 자리를 바꾸는 연산을 반복하는 정렬, 평균 Ο(nlogn)
• 퀵 정렬 특정 값을 기준으로 영역을 나누어 자리를 바꾸는 연산을 반복하는 정렬, 평균 Ο(nlogn)
• 힙 정렬 최대 힙 또는 최소 힙을 생성하여 원소를 삽입하고 인출하는 정렬, 평균 Ο(nlogn)

 

※ 퀵 정렬이 평균적인 성능이 좋기 때문에 많이 사용된다.

 

정렬 알고리즘 테스트 코드

알고리즘의 효율성 테스트를 위해 1,000,000 개의 난수를 생성하여 텍스트 파일로 저장하는 함수와 해당 파일을 불러오는 함수를 구현한다.

 

Common.h

#pragma once
#include <iostream>
#include <fstream>
#include <ctime>

//#define MAKE_RANDOM_NUMBERS

#ifdef MAKE_RANDOM_NUMBERS
#include <random>
#include <limits>
#endif

namespace Common
{
#ifdef MAKE_RANDOM_NUMBERS
	int* GenerateRandomNumber(int n = 100'000);
	void MakeRandomNumbersFile(int n = 100'000);
#endif

#pragma region 파일 입출력
	int LoadRandomNumbersInFile(int** arr);
#pragma endregion
	
#pragma region 시간 측정
	static std::clock_t startTime;
	static std::clock_t endTime;

	void StartClock();
	void StopClock();
	void PrintElapsedTime();
#pragma endregion
	
	void PrintArray(int arr[], int n);
	void Swap(int arr[], int a, int b);
}

 

Common.cpp

#include "Common.h"

namespace Common
{
#ifdef MAKE_RANDOM_NUMBERS
	/// <summary>
	/// 난수 배열을 생성하여 반환한다.
	/// </summary>
	/// <param name="n">생성할 난수의 개수</param>
	/// <returns>생성된 난수 배열</returns>
	int* GenerateRandomNumber(int n)
	{
		std::default_random_engine randomEngine;
		std::uniform_int_distribution<int> distribution(0, INT_MAX);

		int* arr = new int[n];
		for (int i = 0; i < n; ++i)
		{
			arr[i] = distribution(randomEngine);
		}

		return arr;
	}

	/// <summary>
	/// 난수를 생성하여 파일에 저장한다.
	/// </summary>
	/// <param name="n">생성할 난수의 개수</param>
	void MakeRandomNumbersFile(int n)
	{
		int* arr = GenerateRandomNumber(n);

		std::ofstream ofs("./Randoms.txt");

		ofs << n << ' ';
		for (int i = 0; i < n; ++i)
		{
			ofs << arr[i] << ' ';
		}

		ofs.close();
	}
#endif


#pragma region 파일 입출력
	/// <summary>
	/// 파일에 있는 난수를 불러와 입력된 포인터에 저장한다.
	/// </summary>
	/// <param name="arr">불러온 난수 배열을 반환할 포인터</param>
	/// <returns>불러온 난수의 개수</returns>
	int LoadRandomNumbersInFile(int** arr)
	{
		std::ifstream ifs("./Randoms.txt");

		int n;
		ifs >> n;

		*arr = new int[n];
		for (int i = 0; i < n; ++i)
		{
			ifs >> (*arr)[i];
		}

		ifs.close();

		return n;
	}
#pragma endregion

#pragma region 시간 측정
	/// <summary>
	/// 시간 측정을 시작한다.
	/// </summary>
	void StartClock()
	{
		startTime = std::clock();
	}

	/// <summary>
	/// 시간 측정을 종료한다.
	/// </summary>
	void StopClock()
	{
		endTime = std::clock();
	}

	/// <summary>
	/// 측정한 시간을 계산하여 출력한다.
	/// </summary>
	void PrintElapsedTime()
	{
		std::clock_t elapsed = endTime - startTime;

		double timeSecond = static_cast<double>(elapsed / CLOCKS_PER_SEC);

		std::cout << "total time is " << timeSecond << "s ( " << elapsed << "ms )\n";
	}
#pragma endregion
	/// <summary>
	/// 입력된 배열을 출력한다.
	/// </summary>
	/// <param name="arr">출력할 배열</param>
	/// <param name="n">배열의 길이</param>
	void PrintArray(int arr[], int n)
	{
		for (int i = 0; i < n; i++)
		{
			std::cout << arr[i] << ' ';
		}
		std::cout << '\n';
	}

	/// <summary>
	/// 주어진 인덱스의 값을 서로 바꾼다.
	/// </summary>
	/// <param name="arr">값이 들어있는 배열</param>
	/// <param name="a">첫 번째 인덱스</param>
	/// <param name="b">두 번째 인덱스</param>
	void Swap(int arr[], int a, int b)
	{
		int temp{ arr[a] };
		arr[a] = arr[b];
		arr[b] = temp;
	}
}

 

NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소 (github.com)

GitHub - NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소

 

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘