Cpp 09 쉽게쉽게 갑시다...

정하나둘·2023년 11월 20일

42Seoul Ford-Johnson algorithm cpp cpp 09 cpp module 09 merge-insertion sort

CPP Module

목록 보기

1/1

뭔가 cpp 과제를 진행하면서 제대로 뭔가 프로그램을 구현해보는 과제였던 것 같다. 마지막인만큼 역시 쉽지않았다. 특히 ford-johnson algorithm(포드존슨 알고리즘)..;

ex00

특정 날짜에 일정량의 비트코인 값을 출력하는 프로그램을 만들어야 합니다.
이 프로그램은 시간 경과에 따른 비트고인 가겨을 나타내는 .csv형식의 데이터베이스를 사용해야 합니다.(subject 아래 첨부파일 참조)
프로그램은 평가할 다양한 가격/날짜를 저장하는 두 번째 데이터베이스를 인자로 사용한다(argv).
프로그램은 다음 규칙을 준수해야 한다.

프로그램 이름은 btc이다.
프로그램은 파일을 인수로 받아야 한다.
이 파일의 각 라인은 다음 형식을 사용해야 한다.: "date | value"
유효한 날짜는 항상 "연-월-일" 형식이다.
유효한 값은 부동 소수점이거나 0에서 1000사이의 양의 정수여야 한다.

이 예제의 유효성을 검사하려면 코드에서 하나 이상의 컨테이너를 사용해야 한다.
적절한 오류 메세지로 가능한 오류를 처리해야 한다.

다음은 input.txt 파일의 예시다.

프로그램은 입력 파일의 값을 사용한다.
프로그램은 데이터베이스에 표시된 날짜에 따라 환율을 곱한 값(해당 날짜의 input.txt의 코인 갯수 * 해당 날짜의 .csv파일의 환율)의 결과를 표준 출력에 표시해야 한다.

입력에 사용된 날짜(input.txt파일의 날짜)가 DB(.csv파일의 날짜)에 없으면 DB에 포함된 가장 가까운 날짜를 사용해야 한다. 상단 날짜가 아닌 하단 날짜를 사용해야 한다.

다음은 프로그램 사용 예시이다.

경고 : 이 예제에서 유효성을 검사하는데 사용된 컨테이너는 이 모듈(cpp 09)의 나머지 부분에서 더 이상 사용할 수 없다.

main.cpp

#include "BitcoinExchange.hpp"

// void	_leaks()
// {
// 	system("leaks btc");
// }

int main(int argc, char **argv)
{
	if (argc != 2)
	{
		std::cerr << "Error: could not open file." << std::endl;
		return (1);
	}
	BitcoinExchange a;
	try
	{
		a.GetTxtFileData(argv);	//input.txt 한 줄 씩 읽으면서 날짜는 key, 코인 갯수는 value로 map에 보관
		a.CheckTxtFile();	//input.txt 유효성 검사
		a.GetCsvFileData();	//data.csv파일 한 줄 씩 읽으면서 날짜는 key, 환율은 value로 map에 보관
		a.PrintResult();	//몇몇 유효성 검사 추가로 한 후 결과값 출력
	}
	catch(std::exception &e)
	{
		std::cout << e.what() << std::endl;
	}
	// atexit(_leaks);
	return (0);
}

BitcoinExchange.cpp

#include "BitcoinExchange.hpp"

BitcoinExchange::BitcoinExchange()
{
}

BitcoinExchange::BitcoinExchange(std::string filename)
{
	this->filename = filename;
}

BitcoinExchange::BitcoinExchange(const BitcoinExchange &obj)
{
	this->filename = obj.filename;
	this->parsed_csv = obj.parsed_csv;
}

BitcoinExchange &BitcoinExchange::operator=(const BitcoinExchange &obj)
{
	if (this == &obj)
		return (*this);
	this->filename = obj.filename;
	this->parsed_csv = obj.parsed_csv;
	return (*this);
}

BitcoinExchange::~BitcoinExchange()
{
}

std::vector<std::string>	BitcoinExchange::SplitArgs(std::string line, char sep)
{
	std::vector<std::string> result;
	std::stringstream ss;
	std::string buf;
	ss.str(line);

	while (getline(ss, buf, sep))
		result.push_back(buf);
	return (result);
}

void	BitcoinExchange::GetTxtFileData(char **av)
{
	std::ifstream txt(av[1]);
	std::string file_in;
	int	i = 0;

	if (!txt.is_open())
		throw std::logic_error("Error: could not open file.");
	while (std::getline(txt, file_in))
	{
		if (i != 0)
		{
			std::vector<std::string> split_args = SplitArgs(file_in, '|');
			if (split_args.size() > 2)
				throw std::logic_error("Wrong txt file!");
			std::string key = split_args[0];
			std::string value = split_args[1];
			if (key[key.size() - 1] == ' ')
				key.pop_back();
			if (value[0] == ' ')
				value.erase(0, 1);
			if (value == "")
				value = "0";
			this->txt_date.push_back(key);
			this->txt_exchange.push_back(value);
		}
		i++;
	}
	if (this->txt_date.size() != this->txt_exchange.size())
		throw std::logic_error("Wrong txt file!");
}

void	BitcoinExchange::CheckTxtFile()	//1차적 input.txt 유효성 검사
{
	for (size_t i = 0; i < txt_date.size(); i++)
	{
		std::vector<std::string> split_data = SplitArgs(this->txt_date[i], '-');
		if (split_data.size() != 3)
			throw std::logic_error("Wrong txt file!");
		if (split_data[0].size() != 4)
			throw std::logic_error("Wrong txt file!");
		if (split_data[1].size() != 2 || split_data[2].size() != 2)
			throw std::logic_error("Wrong txt file!");
		for (size_t j = 0; j < split_data.size(); j++)
		{
			for (size_t k = 0; k < split_data[j].size(); k++)
			{
				if (split_data[j][k] >= 58 || split_data[j][k] <= 47)
					throw std::logic_error("Wrong txt file!");
			}
		}
		for (size_t j = 0; j < this->txt_exchange.size(); j++)
		{
			if (this->txt_exchange[j] == "bad input")
				continue ;
			for (size_t k = 0; k < this->txt_exchange[j].size(); k++)
			{
				if (this->txt_exchange[j][k] >= 58 || this->txt_exchange[j][k] <= 47)
				{
					if (this->txt_exchange[j][k] != '.' && this->txt_exchange[j][k] != '+' && this->txt_exchange[j][k] != '-')
						throw std::logic_error("Wrong txt file!");
				}
			}
		}
	}
}

void	BitcoinExchange::GetCsvFileData()	//csv 파일 읽어와서 map에 담음
{
	std::ifstream csv("data.csv");
	std::string	file_in;
	int	i = 0;

	if (!csv.is_open())
		throw	std::logic_error("File doesn't exist");
	while (std::getline(csv, file_in))
	{
		if (i != 0)
		{
			std::vector<std::string> split_args = SplitArgs(file_in, ',');
			std::string key = split_args[0];
			std::string value = split_args[1];
			this->parsed_csv.insert(std::make_pair(key, value));
		}
		i++;
	}
}

int	BitcoinExchange::DateValueCheck(int count)	//년,월,일 유효성 검사
{
	int	year_d;
	int	month_d;
	int	day_d;
	char *temp = NULL;

	std::vector<std::string>	split_args = SplitArgs(this->txt_date[count], '-');
	year_d = static_cast<int>(strtod(split_args[0].c_str(), &temp));
	month_d = static_cast<int>(strtod(split_args[1].c_str(), &temp));
	day_d = static_cast<int>(strtod(split_args[2].c_str(), &temp));
	if (month_d < 1 || month_d > 12)
	{
		std::cout << "Error: bad input => " << this->txt_date[count] << std::endl;
		return (1);
	}
	if (month_d == 1 || month_d == 3 || month_d == 5 || month_d == 7 || month_d == 8 || month_d == 10 || month_d == 12)
	{
		if (day_d > 31 || day_d < 1)
		{
			std::cout << "Error: bad input => " << this->txt_date[count] << std::endl;
			return (1);
		}
	}
	else if (month_d == 2)
	{
		if ((year_d % 4 == 0 && year_d % 100 != 0) || year_d % 400 == 0)
		{
			if (day_d > 29 || day_d < 1)
			{
				std::cout << "Error: bad input => " << this->txt_date[count] << std::endl;
				return (1);
			}
		}
		else
		{
			if (day_d > 28 || day_d < 1)
			{
				std::cout << "Error: bad input => " << this->txt_date[count] << std::endl;
				return (1);
			}
		}
	}
	else if (month_d == 4 || month_d == 6 || month_d == 9 || month_d == 11)
	{
		if (day_d > 30 || day_d < 1)
		{
			std::cout << "Error: bad input => " << this->txt_date[count] << std::endl;
			return (1);
		}
	}
	if (year_d < 2009)
	{
		std::cout << "Invalid period!" << std::endl;
		return (1);
	}
	return (0);
}

int		BitcoinExchange::ExchangeValueCheck(int count)
{
	char *temp = NULL;
	double	exchange = strtod(this->txt_exchange[count].c_str(), &temp);
	std::string	check = temp;
	if (check.size() != 0)	//숫자말고 다른 무언가 있는지 확인
	{
		std::cout << "Error: not a positive number." << std::endl;
		return (1);
	}
	if (exchange <= 0)	//0보다 작거나 같으면 에러
	{
		std::cout << "Error: not a positive number." << std::endl;
		return (1);
	}
	return (0);
}

void	BitcoinExchange::PrintBitcoin(int count)
{
	std::map<std::string, std::string>::iterator iter;
	iter = this->parsed_csv.find(this->txt_date[count]);
	if (iter != this->parsed_csv.end())	//input.txt의 날짜가 data.csv에 있으면
	{
		char *temp;
		double cnt = strtod(this->txt_exchange[count].c_str(), &temp);
		if (cnt > 2147483647)
		{
			std::cout << "Error: too large a number." << std::endl;
			return ;
		}
		double rate = strtod(iter->second.c_str(), &temp);
		double value = cnt * rate;
		std::cout << this->txt_date[count] << " => " << this->txt_exchange[count] << " = " << value << std::endl;
	}
	else	//input.txt의 날짜가 data.csv에 없으면
	{
		iter = this->parsed_csv.upper_bound(this->txt_date[count]);	//upper_bound로 초과한 바로 직후의 값
		iter--;	//에서 --해주면 앞의 날짜로 이동
		char *temp;
		double cnt = strtod(this->txt_exchange[count].c_str(), &temp);
		if (cnt > 2147483647)
		{
			std::cout << "Error: too large a number." << std::endl;
			return ;
		}
		double rate = strtod(iter->second.c_str(), &temp);
		double value = cnt * rate;
		std::cout << this->txt_date[count] << " => " << this->txt_exchange[count] << " = " << value << std::endl;	//해당 날짜의 value값 사용해서 출력
	}
}

void	BitcoinExchange::PrintResult()
{
	for (size_t i = 0; i < txt_date.size(); i++)
	{
		if (this->DateValueCheck(i) == 1)	//년도, 월, 월별 일 유효성 검사(윤년 포함)
			continue ;
		if (this->ExchangeValueCheck(i) == 1)	//input.txt에서 갯수가 0이거나 음수인지 체크
			continue ;
		this->PrintBitcoin(i);	//출력(어쩌면 가장 중요할지도)
	}
}

BitcoinExchange.hpp

#ifndef BITCOINEXCHANGE_HPP
# define BITCOINEXCHANGE_HPP

#include <sstream>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>

class BitcoinExchange
{
	private:
		std::string get_data;
		std::string filename;
		std::vector <std::string> split_result;
		std::vector <std::string> txt_date;
		std::vector <std::string> txt_exchange;
		std::map<std::string, std::string>	parsed_csv;
		int	DateValueCheck(int count);
		int	ExchangeValueCheck(int count);
	public:
		BitcoinExchange();
		BitcoinExchange(std::string filename);
		BitcoinExchange(const BitcoinExchange &obj);
		BitcoinExchange &operator=(const BitcoinExchange &obj);
		~BitcoinExchange();
		std::vector<std::string>	SplitArgs(std::string line, char sep);
		void	GetTxtFileData(char **av);
		void	CheckTxtFile();
		void	GetCsvFileData();
		void	PrintBitcoin(int count);
		void	PrintResult();
};

#endif

다른 분들은 대부분 lower_bound를 사용하시던데 그러면 if 분기를 또 나눠야 할 것 같아서 그냥 upper_bound를 사용해서 바로 다음 값을 찾은 뒤 --해주는 방식을 사용했다. 어쨌든 초과한 바로 다음 값을 반환해주기 때문에 --해주면 그 값과 같거나 그 값 바로 앞에 값으로 갈 수 있다.

그 외에는 윤년 처리가 조금 귀찮았지만 금방 할 수 있었다.

한가지 놓친 부분이 있다면 갯수 부분이 1 ~ 1000 사이여야 한다는 부분을 놓쳐서 처리해주지 못했다. 하지만 평가를 진행하며 나 포함 그 누구도 알지 못했다....(블로그 쓰면서 처음 봄...;;)

ex01

프로그램 이름은 RPN이다.
프로그램은 역폴란드어 수학 표현식을 인수로 취해야한다.
이 작업에 사용되고 인수로 전달되는 숫자는 항상 10보다 작다. 계산 자체와 결과는 이 규칙을 고려하지 않는다.
프로그램은 이 식을 처리하고 표준 출력에 결과를 출력해야 한다.
프로그램 실행 중 오류가 발생하면 표준 출력에 오류 메세지가 표시되어야 한다.
프로그램은 다음 토큰을 이용하여 작업을 처리할 수 있어야 한다: + - * /"

이 예제의 유효성을 검사하려면 코드에서 하나 이상의 컨테이너를 사용해야 한다.
괄호나 십진수를 관리할 필요가 없다.

예시:

이 예제의 유효성을 검사하는데 사용하는 컨테이너는 이 모듈의 나머지 부분에서 사용할 수 없다.

역 폴란드 표기법에 대해선 찾으면 많이 나오니 내 블로그에선 따로 기술하지 않겠다.
다만 수식을 그냥 앞에서부터 읽어 나가면서 부호를 만나면 앞의 두 개의 값을 처리하면 된다는 프로그램적 특징이 있어 해당 특징과 같은 스택 자료구조를 사용해주었다.

프로그램을 실행할 때 받아오는 인자값으로 음수가 들어오면 마이너스(-)와 헷갈릴 수 있어 음수는 예외처리 했다.
물론 숫자나 연산자를 제외한 다른 모든 문자들도 예외처리 했다.

main.cpp

#include "RPN.hpp"

// void	_leaks()
// {
// 	system("leaks RPN");
// }

int main(int ac, char *av[])
{
	if (ac != 2)
	{
		std::cerr << "Argument Error" << std::endl;
		return (1);
	}
	RPN a;
	try
	{
		a.SplitArgs(av[1], ' ');	//인자값을 스페이스 기준으로 자른다.
		a.MakeResult();	//출력^^
	}
	catch(std::exception &e)
	{
		std::cerr << e.what() << std::endl;
	}
	// atexit(_leaks);
	return(0);
}

RPN.cpp

#include "RPN.hpp"

RPN::RPN()
{
}

RPN::RPN(const RPN &obj)
{
	this->num_stack = obj.num_stack;
	this->parsed_av = obj.parsed_av;
}

RPN &RPN::operator=(const RPN &obj)
{
	if (this == &obj)
		return (*this);
	this->num_stack = obj.num_stack;
	this->parsed_av = obj.parsed_av;
	return (*this);
}

RPN::~RPN()
{
}

void	RPN::SplitArgs(std::string line, char sep)	//문자열을 특정 문자 기준으로 잘라주는 함수
{
	std::stringstream ss;
	std::string buf;

	ss.str(line);
	while (getline(ss, buf, sep))
		this->parsed_av.push_back(buf);
}

void RPN::ValidTest(std::string line)	//유효성 검사
{
	if (line.size() != 1)	//10 미만 숫자만 처리할 수 있게
	{
		throw std::logic_error("Error");
	}
	if (!(line[0] >= 48 && line[0] <= 57))	//숫자가 아니면
	{
		if (line[0] != '-' && line[0] != '+' && line[0] != '*' && line[0] != '/')	//숫자가 아닌데 + - * / 도 아니면 에러
		{
			throw std::logic_error("Error");
		}
	}
}

int RPN::FindOperator(std::string line)	//부호 찾기
{
	if (line[0] == '+')
		return (1);
	else if (line[0] == '-')
		return (2);
	else if (line[0] == '*')
		return (3);
	else if (line[0] == '/')
		return (4);
	return (0);
}

void	RPN::MakeResult()
{
	double	data;
	char	*temp;

	for (size_t i = 0; i < this->parsed_av.size(); i++)
	{
		ValidTest(this->parsed_av[i]);
		if (this->parsed_av[i][0] >= 48 && this->parsed_av[i][0] <= 57)	//부호가 아닌 숫자면
		{
			data = strtod(parsed_av[i].c_str(), &temp);
			this->num_stack.push(data);	//스택에 저장
		}
		else	//부호면
		{
			if (!(this->num_stack.size() >= 2))	//스택에 반드시 2개 이상의 숫자가 존재해야 함 그렇지 않으면 에러
				throw std::logic_error("Error");
			double second = num_stack.top();	//최상위 값을 연산자 뒤 값으로 둠
			num_stack.pop();	//최상위 값 삭제
			double first = num_stack.top();	//최상위 값 연산자 앞 값으로 둠
			num_stack.pop();	//최상위 값 삭제
			int opt = this->FindOperator(this->parsed_av[i]);	//부호에 따라 결과값 스택에 저장
			if (opt == 1)
				num_stack.push(first + second);
			else if (opt == 2)
				num_stack.push(first - second);
			else if (opt == 3)
				num_stack.push(first * second);
			else if (opt == 4)
				num_stack.push(first / second);
		}
	}
	if (this->num_stack.size() != 1)	//종료 후 스택에 남은 값이 하나가 아니라 더 있으면 에러
		std::logic_error("Error");
	if (this->num_stack.top() >= 2147483647 || this->num_stack.top() <= -2147483648)
	{
		std::cout << "Over INT_MAX or under INT_MIN" << std::endl;
		return ;
	}
	std::cout << static_cast<long long>(this->num_stack.top()) << std::endl;
}

RPN.hpp

#ifndef RPN_HPP
# define RPN_HPP

#include <iostream>
#include <stack>
#include <vector>
#include <sstream>

class RPN
{
	private:
		std::stack<double> num_stack;
		std::vector<std::string> parsed_av;
	public:
		RPN();
		RPN(const RPN &obj);
		RPN &operator =(const RPN &obj);
		~RPN();
		void	SplitArgs(std::string line, char sep);
		void	ValidTest(std::string line);
		void	MakeResult();
		int	FindOperator(std::string line);
};

# endif

ex02

프로그램 이름은 PmergeMe이다.
프로그램은 양의 정수 시퀀스를 인수로 사용할 수 있어야 한다.
프로그램은 병합-삽입 정렬 알고리즘을 사용하여 양의 정수 시퀀스를 정렬해야 한다. 포드존슨 알고리즘을 사용해야 한다.
프로그램 실행 중 오류가 발생하면 표준 출력에 오류 메세지가 표시되어야 한다.

이 예제의 유효성을 검사하려면 코드에서 두 개 이상의 컨테이너를 사용해야 한다. 프로그램은 적어도 3000개의 서로 다른 정수를 처리할 수 있어야 한다.
각 컨테이너에 대해 알고리즘을 구현하여 일반 함수를 사용하지 않는 것이 좋다.

다음은 표준 출력에 표시해야 하는 정보에 대한 추가 사항이다. 이 정보는 다음과 같이 줄 단위로 표시되어야 한다.

첫 번째 줄에는 명시적인 텍스트와 함께 정렬되지 않은 양의 정수 시퀀스를 표시해야 한다.
두 번째 줄에는 명시적인 텍스트와 함께 정렬된 양의 정수 시퀀스를 표시해야 한다.
세 번째 줄에는 알고리즘이 사용한 시간을 첫 번째 컨테이너를 사용하여 양의 정수 시퀀스를 정렬하는데 걸린 시간을 명시하는 텍스트를 표시해야 한다.
마지막 줄에는 알고리즘이 사용한 시간을 두 번째 컨테이너를 사용하여 양의 정수 시퀀스를 정렬하는데 걸린 시간을 명시하는 텍스트를 표시해야 한다.

정렬을 수행하는데 사용되는 시간 표시 형식은 자유지만 선택한 정밀도는 사용된 두 컨테이너 간의 차이를 명확하게 볼 수 있어야 한다.

예시:

예제에서 시간 표시는 고의적으로 이상하게 되어 있다. 당연히 모든 작업을 수행하는데 걸린 시간을 표시해야 한다. 정렬 부분과 데이터 관리 부분 모두 포함된다.
주의 : 이전 예제에서 사용한 컨테이너들은 여기서 사용이 금지되어 있다.
중복과 관련된 오류 처리는 너가 결정해라

가장 난관이였던 과제였다. 구글을 통해 포드존슨 알고리즘에 대해 찾아봐도 자료가 딱히 존재하지 않아 미칠 지경이였다.
그럼에도 여기저기 물어보고 줍줍해서 어떻게든 짜 보았다.

해당 과제를 진행하면서 가장 도움이 되었던 글은 아래 블로그이다.
https://80000coding.oopy.io/6880ebc0-acb3-4225-809f-37fc419adf71

merge-insertion sort는 정렬을 수행함에 있어 최대연산횟수를 줄일 수 있는 최고의 알고리즘이다.
일단 과정에 대해 알아보자

무작위로 섞여있는 정수 배열(11 7 5 3 20 22)들을 앞에서부터 2개씩 묶는다.([11 7][5 3] [20 22])만약 배열 수가 홀수라면 마지막 하나는 남겨놓는다.
묶음 안에서 비교를 수행해 큰 원소가 앞에 오도록 한다. ([11 7][5 3] [22 20])
각 쌍의 앞에 위치한 더 큰 원소를 기준으로 정렬한다.(본인은 merge-insertion sort라서 merge sort에 집착해서 해당 정렬을 merge-sort로 구현했는데 이건 그냥 vector나 deque의 sort함수를 써도 상관없다. 어짜피 위에서 묶음을 나눠서 정렬을 수행하고 아래에서 합치는 부분들이 merge-sort이기 때문에 굳이 merge-sort를 따로 구현해서 사용할 필요가 없다)
([5 3][11 7] [22 20])

아래에서 알아보기 편하게 각각의 원소에 별칭을 부여해주었다.

(나는 묶음에서 앞의 원소들을 main이라고 하고 뒤의 원소들을 remain이라고 정의했다. main은 이미 정렬되어있는 상태이고 remain은 이제 main에서 위치를 찾아 넣어줘야 하는데 앞에서부터 순차적으로 main 에 넣는게 아니라 최대 연산 횟수를 고려해서 집어넣을 순서를 정해야한다.)우선 b1은 반드시 a1보다 작으므로 a1 앞에 넣어준다.
여기서 b2말고 b3먼저 위치를 찾아 넣어주는데 그 이유는 다음과 같다.

b3는 a3보다 작으므로, b2가 먼저 삽입되었다면 [b1, a1, a2, b2] 중에 이진탐색을 하기 때문에 최대 탐색횟수가 늘어나게 된다. 반면 b2는 b3가 먼저 삽입되어도 어짜피 a2보다 작기 때문에 탐색구간이 변경되지 않는다.
(최대 탐색횟수의 수가 줄어드는 것이지 항상 빠르게 삽입된다는 것은 아니다)

이런 구조이고 뒤에서부터 앞으로 위치를 찾아 삽입하지만
뒤의 정의는 야콥스탈 수를 따른다.
야콥스탈 수는 0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, 87381, 174763, 349525, … 등으로 아래와 같은 규칙을 따르는 수열이다.

따라서 b1(1)은 시작할 때 이미 a1 앞에 넣어주므로 3, 2, 5, 4, 11, 10, 9, 8, 7, 6, 21,...순으로 main에 삽입한다.

그렇다면 왜 야콥스탈 수를 따르는지 알아보자.
아까 위에서 설명했듯이 이진탐색의 최대탐색 횟수는 log 2^n + 1로 2의 n승이 될 때 마다 1씩 늘어난다.

최대 탐색 횟수가 1번인 원소 수(n) = 2, 3(2개가 동일)
최대 탐색 횟수가 2번인 원소 수(n) = 4, 5, 6, 7(4개가 동일)
최대 탐색 횟수가 3번인 원소 수(n) = 8, 9, 10, 11, 12, 13, 14, 15(8개가 동일)]
최대 탐색 횟수가 4번인 원소 수(n) = 16, ..., 31(16개가 동일)
...

앞선 예시를 좀 더 확장시켜보면 이해가 좀 더 수월할 것이다.

21개의 원소가 앞선 구조대로 구성되어있고 b3까지 삽입하고 그 이후를 알아볼 것이다.

(b3까지 삽입한 후의 모습)
그 다음 삽입할 원소는 b5이다.
이유는 b4는 탐색할 원소 수가 6개, b5는 7개(c1~c6 + a4)로 최대 탐색횟수가 2회로 같고 위에서 해당 경우 맨 뒤에서부터 앞으로 삽입한다고 말했다.

위와 같은 원리로 b5, b4순으로 정렬을 마치면(야콥스탈 1,3,5,11, ... 중 5) b6부터 비교할 원소 수가 10개가 되고 최대 탐색 횟수가 3번이 되므로 그중 가장 큰 원소 수를 가진 비교 원소 수가 15개가 되는 11번으로 가서 11, 10, 9, 8, 7, 6순번으로 삽입하게 되는 것이다.

이쯤했으면 이해했을거라 생각하고 코드를 보자.

main.cpp

#include "PmergeMe.hpp"

// void _leaks()
// {
// 	system("leaks PmergeMe");
// }

int main(int ac, char **av)
{
	if (ac == 1)
	{
		std::cerr << "Error" << std::endl;
		return (1);
	}
	PmergeMe::PmergeVec	vec;
	PmergeMe::PmergeDeq deq;
	try
	{
		clock_t vec_start = clock();
		vec.MergeInsertionSortVec(ac, av);	//vector 정렬
		vec_start = clock() - vec_start;

		clock_t deq_start = clock();
		deq.MergeInsertionSortDeq(ac, av);	//deque 정렬
		deq_start = clock() - deq_start;

		vec.PrintBefore();	//정렬 전 배열 출력
		vec.PrintAfter();	//정렬 후 배열 출력
		std::cout << "Time to process a range of " << ac - 1 << " element with std::vector : " << (float)vec_start * 1000 / CLOCKS_PER_SEC << " ms" << std::endl;	//vector 시간 출력
		std::cout << "Time to process a range of " << ac - 1 << " element with std::deque : " << (float)deq_start * 1000 / CLOCKS_PER_SEC << " ms" << std::endl;	//deque 시간 출력
	}
 	catch(std::exception &e)
	{
		std::cerr << e.what() << std::endl;
	}
	// atexit(_leaks);
	return(0);
}

PmergeMe.hpp

#ifndef PMERGEME_HPP
# define PMERGEME_HPP

#include <iostream>
#include <vector>
#include <deque>
#include <sys/time.h>
#include <ctime>

class PmergeMe
{
	public:
		PmergeMe();
		PmergeMe(const PmergeMe &obj);
		PmergeMe &operator=(const PmergeMe &obj);
		~PmergeMe();
		class PmergeVec
		{
			private:
				std::vector<std::string> args;
				std::vector<int> args_int;
				std::vector<std::pair<int, int> > pair_av;
				std::vector<std::pair<int, int> > global;
				std::vector<int> main;
				std::vector<int> remain;
				std::vector<int> jacob_arr;
				std::vector<int> position;
				// int rest;
			public:
				PmergeVec();
				~PmergeVec();
				void	MergeInsertionSortVec(int ac, char **av);
				void	ArgsToVec(int argc, char **argv);
				void	ValidCheck();
				void	MakePairVec();
				void	merge(std::vector<std::pair<int, int> > &array, int begin, int mid, int end);
				void	MergeSort(std::vector<std::pair<int, int> > &array, int begin, int end);
				void	MainAndRemain();
				void	GeneratePos();
				void	InsertionSortBegin();
				void	MakeJacobArr();
				int	Jacobsthal(int n);
				int	BinarySearch(std::vector<int> array, int target, int low, int high);
				void	PrintBefore();
				void	PrintAfter();
		};

		class PmergeDeq
		{
			private:
				std::deque<std::string> args;
				std::deque<int> args_int;
				std::deque<std::pair<int, int> > pair_av;
				std::deque<std::pair<int, int> > global;
				std::deque<int> main;
				std::deque<int> remain;
				std::deque<int> jacob_arr;
				std::deque<int> position;
			public:
				PmergeDeq();
				~PmergeDeq();
				void	MergeInsertionSortDeq(int ac, char **av);
				void	ArgsToDeq(int argc, char **argv);
				void	ValidCheck();
				void	MakePairDeq();
				void	merge(std::deque<std::pair<int, int> > &array, int begin, int mid, int end);
				void	MergeSort(std::deque<std::pair<int, int> > &array, int begin, int end);
				void	MainAndRemain();
				void	GeneratePos();
				void	InsertionSortBegin();
				void	MakeJacobArr();
				int	Jacobsthal(int n);
				int	BinarySearch(std::deque<int> array, int target, int low, int high);
				void	PrintBefore();
				void	PrintAfter();
		};
	private:
};

#endif

PmergeMe.cpp

#include "PmergeMe.hpp"
#include <unistd.h>

PmergeMe::PmergeMe()
{
}

PmergeMe::PmergeMe(const PmergeMe &obj)
{
	(void)obj;
}

PmergeMe &PmergeMe::operator=(const PmergeMe &obj)
{
	if (this == &obj)
		return (*this);
	return (*this);
}

PmergeMe::~PmergeMe()
{
}

PmergeMe::PmergeVec::PmergeVec()
{
}

PmergeMe::PmergeVec::~PmergeVec()
{
}

void	PmergeMe::PmergeVec::ArgsToVec(int argc, char **argv)
{
	std::vector<std::string>	temp(argv + 1, argv + argc);
	this->args = temp;
}

void	PmergeMe::PmergeVec::ValidCheck()
{
	int	push;
	double	data;
	char	*temp;
	std::string	check;

	for (size_t i = 0; i < this->args.size(); i++)
	{
		for (size_t j = 0; j < this->args[i].size(); j++)
		{
			if (this->args[i][j] > 57 || this->args[i][j] < 48)
				throw std::logic_error("Error");
		}
		data = strtod(this->args[i].c_str(), &temp);
		check = temp;
		if (check.size() != 0)
			throw std::logic_error("Error");
		if (data < 0)
			throw std::logic_error("Error");
		if (data > 2147483647)
			throw std::logic_error("Error");
		push = static_cast<int>(data);
		this->args_int.push_back(push);
	}
}

void	PmergeMe::PmergeVec::MakePairVec()
{
	int	pair_size = this->args_int.size() / 2;
	int i = 0;
	while (pair_size != 0)
	{
		if (this->args_int[i] < this->args_int[i + 1])
		{
			int	tmp = this->args_int[i];
			this->args_int[i] = this->args_int[i + 1];
			this->args_int[i + 1] = tmp;
		}
		this->pair_av.push_back(std::make_pair(this->args_int[i], this->args_int[i + 1]));
		this->global.push_back(std::make_pair(this->args_int[i], this->args_int[i + 1]));
		i += 2;
		pair_size--;
	}
}

// void	PmergeMe::PmergeVec::merge(std::vector<std::pair<int, int> > &array, int begin, int mid, int end)
// {
// 	size_t left_index = 0;
// 	size_t right_index = 0;
// 	size_t merged_index = begin;

// 	std::vector<std::pair<int, int> > left_array(array.begin() + begin, array.begin() + mid + 1);
// 	std::vector<std::pair<int, int> > right_array(array.begin() + mid + 1, array.begin() + end + 1);

// 	while (left_index < left_array.size() && right_index < right_array.size())
// 	{
// 		if (left_array[left_index].first <= right_array[right_index].first)
// 		{
// 			array[merged_index] = left_array[left_index];
// 			left_index++;
// 		}
// 		else
// 		{
// 			array[merged_index] = right_array[right_index];
// 			right_index++;
// 		}
// 		merged_index++;
// 	}
// 	while (left_index < left_array.size())
// 	{
// 		array[merged_index] = left_array[left_index];
// 		left_index++;
// 		merged_index++;
// 	}
// 	while (right_index < right_array.size())
// 	{
// 		array[merged_index] = right_array[right_index];
// 		right_index++;
// 		merged_index++;
// 	}
// }

void	PmergeMe::PmergeVec::merge(std::vector<std::pair<int, int> > &array, int begin, int mid, int end)
{
	int i, j, k, l;
	i = begin;
	j = mid + 1;
	k = begin;

	while (i <= mid && j <= end)
	{
		if (array[i].first <= array[j].first)
			this->global[k++] = array[i++];
		else
			this->global[k++] = array[j++];
	}
	if (i > mid)
	{
		for (l = j; l <= end; l++)
			this->global[k++] = array[l];
	}
	else
	{
		for (l = i; l <= mid; l++)
			this->global[k++] = array[l];
	}
	for (l = begin; l <= end; l++)
		array[l] = this->global[l];
}

void	PmergeMe::PmergeVec::MergeSort(std::vector<std::pair<int, int> > &array, int begin, int end)
{
	int	mid;

	if (begin >= end)
		return ;
	mid = (begin + end) / 2;
	this->MergeSort(array, begin, mid);
	this->MergeSort(array, mid + 1, end);
	this->merge(array, begin, mid, end);
}

void	PmergeMe::PmergeVec::MainAndRemain()
{
	size_t i = 0;

	this->main.push_back(this->pair_av[0].second);	//remain의 첫 번째 수를 main 맨 앞에 넣음
	while (i < this->pair_av.size())
	{
		this->main.push_back(this->pair_av[i].first);	//main의 값들을 넣어줌
		this->remain.push_back(this->pair_av[i].second);	//remain의 값들을 넣어줌
		i++;
	}
	//주의: main으로 보낸 remain의 첫 번째 값 지우지 않고 그대로 놔둠
}

int	PmergeMe::PmergeVec::Jacobsthal(int n)	//일반 야콥스탈 구현
{
	if (n == 0)
		return (0);
	else if (n == 1)
		return (1);
	int i = Jacobsthal(n - 1) + 2 * Jacobsthal(n - 2);
	return (i);
}

int		PmergeMe::PmergeVec::BinarySearch(std::vector<int> array, int target, int low, int high)
{
	int mid;

	while (low <= high)
	{
		mid = low + (high - low) / 2;
		if (target == array.at(mid))
			return (mid);

		if (target > array.at(mid))
			low = mid + 1;
		else
			high = mid - 1;
	}
	if (target > array.at(mid))
		return (mid + 1);
	else
		return (mid);
}

void	PmergeMe::PmergeVec::MakeJacobArr()
{
	size_t	remain_size;
	size_t	jacobsthal_idx;
	int	index;

	remain_size = this->remain.size();
	index = 3;	//이미 remain의 첫 번째는 처리했으므로 3(그 다음 최소 야콥스탈 수)부터 처리한다.

	while ((jacobsthal_idx = this->Jacobsthal(index)) < remain_size)	//remain의 갯수보다 작을 때까지 반복해서 돌리며 배열에 넣어준다.
	{
		this->jacob_arr.push_back(jacobsthal_idx);
		index++;
	}
}

void	PmergeMe::PmergeVec::GeneratePos()
{
	size_t	value;
	size_t	pos;
	size_t	last_pos;
	size_t	i;

	if (this->remain.empty())
		return ;
	this->MakeJacobArr();	//야콥스탈 배열을 만드는 함수 ex: 3 5 11 21 43 ...
	last_pos = 1;
	value = 1;
	i = 0;
	while (i < this ->jacob_arr.size())
	{
		value = this->jacob_arr[i];
		this->position.push_back(value);	//해당 야콥스탈 수를 맨 먼저 넣고
		pos = value - 1;
		while (pos > last_pos)	//앞선 야콥스탈 수보다 클 동안 1씩 빼서 배열에 넣어준다.
		{
			this->position.push_back(pos);
			pos--;
		}
		last_pos = value;
		i++;
	}

	value = this->remain.size();
	while (value > last_pos)
	{
		this->position.push_back(value);
		value--;
	}

	// while (value++ < this->remain.size())
		// this->position.push_back(value);
}

void	PmergeMe::PmergeVec::InsertionSortBegin()
{
	int target;
	size_t end_pos;
	size_t pos;
	size_t addedCount;
	std::vector<int>::iterator it;

	this->GeneratePos();	//야콥스탈 수를 이용해 순차적으로 삽입해야 하는 배열의 목록을 만드는 함수 ex: 3 2 5 4 11 10 9 8 7 6
	addedCount = 0;
	for(it = this->position.begin(); it < this->position.end(); it++)
	{
		target = this->remain[*it - 1];	//it가 가리키는 숫자들은 실제 인덱스 값보다 1이 크기 때문에 빼준다.(인덱스는 0번부터)
		end_pos = *it + addedCount;	//해당 remain의 수는 main보다 작기 때문에 end_pos를 다음과 같이 설정해주고 이진탐색한다.
		pos = this->BinarySearch(this->main, target, 0, end_pos);
		this->main.insert(this->main.begin() + pos, target);	//찾은 위치에 값을 삽입한다.
		addedCount++;
	}
	if (this->args_int.size() % 2 != 0)	//정렬해야할 수가 홀수인 경우 맨 마지막 인자는 묶음에 속하지 못하기 떄문에 따로 처리한다.
	{
		target = this->args_int[this->args_int.size() - 1];
		pos = this->BinarySearch(this->main, target, 0, this->main.size() - 1);
		this->main.insert(this->main.begin() + pos, target);
	}
}

void	PmergeMe::PmergeVec::MergeInsertionSortVec(int ac, char **av)
{
	this->ArgsToVec(ac, av);	//char ** to string vector
	this->ValidCheck();			//string to int
	this->MakePairVec();		//make pair(big, small)
	this->MergeSort(this->pair_av, 0, this->pair_av.size() - 1);	//merge-sort with bigger numbers
	this->MainAndRemain();
	this->InsertionSortBegin();
}

void	PmergeMe::PmergeVec::PrintBefore()
{
	size_t	i;
	for (i = 0; i < this->args.size() - 1; i++)
	{
		std::cout << this->args[i] << " ";
	}
	std::cout << this->args[i] << std::endl;
}

void	PmergeMe::PmergeVec::PrintAfter()
{
	size_t i;
	for (i = 0; i < this->main.size() - 1; i++)
	{
		std::cout << this->main[i] << " ";
	}
	std::cout << this->main[i] << std::endl;
}

PmergeMe::PmergeDeq::PmergeDeq()
{
}

PmergeMe::PmergeDeq::~PmergeDeq()
{
}

void	PmergeMe::PmergeDeq::ArgsToDeq(int argc, char **argv)
{
	std::deque<std::string>	temp(argv + 1, argv + argc);
	this->args = temp;
}

void	PmergeMe::PmergeDeq::ValidCheck()
{
	int	push;
	double	data;
	char	*temp;
	std::string	check;

	for (size_t i = 0; i < this->args.size(); i++)
	{
		data = strtod(this->args[i].c_str(), &temp);
		check = temp;
		if (check.size() != 0)
			throw std::logic_error("Error");
		if (data < 0)
			throw std::logic_error("Error");
		if (data > 2147483647)
			throw std::logic_error("Error");
		push = static_cast<int>(data);
		this->args_int.push_back(push);
	}
}

void	PmergeMe::PmergeDeq::MakePairDeq()
{
	int	pair_size = this->args_int.size() / 2;
	int i = 0;
	while (pair_size != 0)
	{
		if (this->args_int[i] < this->args_int[i + 1])
		{
			int	tmp = this->args_int[i];
			this->args_int[i] = this->args_int[i + 1];
			this->args_int[i + 1] = tmp;
		}
		this->pair_av.push_back(std::make_pair(this->args_int[i], this->args_int[i + 1]));
		this->global.push_back(std::make_pair(this->args_int[i], this->args_int[i + 1]));
		i += 2;
		pair_size--;
	}
}

void	PmergeMe::PmergeDeq::merge(std::deque<std::pair<int, int> > &array, int begin, int mid, int end)
{
	int i, j, k, l;
	i = begin;
	j = mid + 1;
	k = begin;

	while (i <= mid && j <= end)
	{
		if (array[i].first <= array[j].first)
			this->global[k++] = array[i++];
		else
			this->global[k++] = array[j++];
	}
	if (i > mid)
	{
		for (l = j; l <= end; l++)
			this->global[k++] = array[l];
	}
	else
	{
		for (l = i; l <= mid; l++)
			this->global[k++] = array[l];
	}
	for (l = begin; l <= end; l++)
		array[l] = this->global[l];
}

void	PmergeMe::PmergeDeq::MergeSort(std::deque<std::pair<int, int> > &array, int begin, int end)
{
	int	mid;

	if (begin >= end)
		return ;
	mid = (begin + end) / 2;
	this->MergeSort(array, begin, mid);
	this->MergeSort(array, mid + 1, end);
	this->merge(array, begin, mid, end);
}

void	PmergeMe::PmergeDeq::MainAndRemain()
{
	size_t i = 0;

	this->main.push_back(this->pair_av[0].second);
	while (i < this->pair_av.size())
	{
		this->main.push_back(this->pair_av[i].first);
		this->remain.push_back(this->pair_av[i].second);
		i++;
	}
}

int	PmergeMe::PmergeDeq::Jacobsthal(int n)
{
	if (n == 0)
		return (0);
	else if (n == 1)
		return (1);
	int i = Jacobsthal(n - 1) + 2 * Jacobsthal(n - 2);
	return (i);
}

int		PmergeMe::PmergeDeq::BinarySearch(std::deque<int> array, int target, int low, int high)
{
	int mid;

	while (low <= high)
	{
		mid = low + (high - low) / 2;
		if (target == array.at(mid))
			return (mid);

		if (target > array.at(mid))
			low = mid + 1;
		else
			high = mid - 1;
	}
	if (target > array.at(mid))
		return (mid + 1);
	else
		return (mid);
}

void	PmergeMe::PmergeDeq::MakeJacobArr()
{
	size_t	remain_size;
	size_t	jacobsthal_idx;
	int	index;

	remain_size = this->remain.size();
	index = 3;

	while ((jacobsthal_idx = this->Jacobsthal(index)) < remain_size)
	{
		this->jacob_arr.push_back(jacobsthal_idx);
		index++;
	}
}

void	PmergeMe::PmergeDeq::GeneratePos()
{
	size_t	value;
	size_t	pos;
	size_t	last_pos;
	size_t	i;

	if (this->remain.empty())
		return ;
	this->MakeJacobArr();
	last_pos = 1;
	value = 1;
	i = 0;
	while (i < this ->jacob_arr.size())
	{
		value = this->jacob_arr[i];
		this->position.push_back(value);
		pos = value - 1;
		while (pos > last_pos)
		{
			this->position.push_back(pos);
			pos--;
		}
		last_pos = value;
		i++;
	}

	value = this->remain.size();
	while (value > last_pos)
	{
		this->position.push_back(value);
		value--;
	}
}

void	PmergeMe::PmergeDeq::InsertionSortBegin()
{
	int target;
	size_t end_pos;
	size_t pos;
	size_t addedCount;
	std::deque<int>::iterator it;

	this->GeneratePos();
	addedCount = 0;
	for(it = this->position.begin(); it < this->position.end(); it++)
	{
		target = this->remain[*it - 1];
		end_pos = *it + addedCount;
		pos = this->BinarySearch(this->main, target, 0, end_pos);
		this->main.insert(this->main.begin() + pos, target);
		addedCount++;
	}
	if (this->args_int.size() % 2 != 0)
	{
		target = this->args_int[this->args_int.size() - 1];
		pos = this->BinarySearch(this->main, target, 0, this->main.size() - 1);
		this->main.insert(this->main.begin() + pos, target);
	}
}

void	PmergeMe::PmergeDeq::MergeInsertionSortDeq(int ac, char **av)
{
	this->ArgsToDeq(ac, av);	//char ** to string deque
	this->ValidCheck();			//string to int
	this->MakePairDeq();		//make pair(big, small)
	this->MergeSort(this->pair_av, 0, this->pair_av.size() - 1);
	this->MainAndRemain();
	this->InsertionSortBegin();
}

void	PmergeMe::PmergeDeq::PrintBefore()
{
	size_t	i;
	for (i = 0; i < this->args.size() - 1; i++)
	{
		std::cout << this->args[i] << " ";
	}
	std::cout << this->args[i] << std::endl;
}

void	PmergeMe::PmergeDeq::PrintAfter()
{
	size_t i;
	for (i = 0; i < this->main.size() - 1; i++)
	{
		std::cout << this->main[i] << " ";
	}
	std::cout << this->main[i] << std::endl;
}

vector 코드를 먼저 만들고 그대로 복사해서 deque로 바꿔줬기 때문에 코드에 차이가 없다.
사실 deque는 양방향 접근이 가능해 vector 보다 시간이 짧아야하지만 vector에서 그대로 복붙해서 그런지 몇 개만 넣어줘도 시간이 오래걸리는 현상이 있었다.(물론 신경쓰지 않았다). ㅎㅎ