코딩 블로그

#include <iostream>
#include <cstring>
using namespace std;

template<typename T, size_t s>
inline size_t arsize(T (&a)[s]){return s;}

void quick_sort(int* arr, int left, int right) {
	
    //단순 삽입 정렬 이용해 처음, 가운데, 끝 요소를 오름차순 정렬함
    int tmp[3]={left, (left+right)/2, right};
    for(int i=1;i<3;i++){
    	int t=arr[tmp[i]], j=i;
    	for(; j>0 && arr[tmp[j-1]]>t; j--)
    		arr[tmp[j]]=arr[tmp[j-1]];
    	arr[tmp[j]]=t;
    }
    //가운데 요소와 끝에서 2번째 요소 교환
    swap(arr[tmp[1]], arr[right-1]);
    //이후 정렬 범위는 축소되고 끝에서 2번째 값을 피벗으로 설정
    int pl=left+1, pr=right-2, pivot=arr[right-1];
    //이유는 위에서 수행한 세요소의 정렬때문에 a[left]는 피벗 이하
    //a[right-1], a[right]는 피벗 이상의 값인게 확정됨
    
    while (pl<= pr) {
        while (arr[pl] < pivot)
            pl++;
        while (arr[pr] > pivot)
            pr--;
        if (pl<= pr)
        {
            swap(arr[pl], arr[pr]);
            pl++;
            pr--;
        }
    }

    if (left < pr)
        quick_sort(arr, left, pr);

    if (pl < right)
        quick_sort(arr, pl, right);
}

int main() {
	// your code goes here
	int a[]={1,5,85,8,0,-10,32};
	cout<<"정렬 전\n";
	for(int i=0;i<arsize(a);i++)
		cout<<a[i]<<' ';
	cout<<'\n';
	
	quick_sort(a, 0, arsize(a)-1);
	
	cout<<"정렬 후\n";
	for(int i=0;i<arsize(a);i++)
		cout<<a[i]<<' ';
	cout<<'\n';	
	return 0;
}

#include <iostream>
#include <cstring>
#include <chrono>
#include <climits>

using namespace std;
//namespace chrono = std::chrono;

//시간 측정용 클래스입니다.
class Timer
{
public:
    void start() //타이머를 가동합니다.
    {
        start_point = chrono::system_clock::now();
    }

    void stop() //타이머를 중단합니다.
    {
        stop_point = chrono::system_clock::now();
    }

    void clear() //값을 초기화합니다.
    {
        start_point = chrono::time_point<chrono::system_clock>::min();
        stop_point = chrono::time_point<chrono::system_clock>::min();
    }

public:
    template<class seconds_t>
    long long get_time() const //측정 메서드의 템플릿입니다.
    {
        return chrono::duration_cast<seconds_t>(stop_point - start_point).count();
    }

    long long get_nano() const //나노세컨드 단위입니다.
    {
        return get_time<chrono::nanoseconds>();
    }

    long long get_micro() const //마이크로세컨드 단위입니다.
    {
        return get_time<chrono::microseconds>();
    }

    long long get_milli() const //밀리세컨드 단위입니다.
    {
        return get_time<chrono::milliseconds>();
    }

    long long get_seconds() const //세컨드 단위입니다.
    {
        return get_time<chrono::seconds>();
    }

    long long get_minutes() const //분 단위입니다.
    {
        return get_time<chrono::minutes>();
    }

    long long get_hours() const //시간 단위입니다.
    {
        return get_time<chrono::hours>();
    }

private:
    chrono::time_point<chrono::system_clock> start_point; //시작지점입니다.
    chrono::time_point<chrono::system_clock> stop_point; //중단지점입니다.

public:
    Timer() = default;
    Timer(const Timer&) = default;
    Timer(Timer&&) = default;
    Timer& operator= (const Timer&) = default;
    Timer& operator= (Timer&&) = default;
    virtual ~Timer() = default;

};

const char* mystrstr (const char * str1, const char * str2)
{
    char *cp = (char *) str1;
    char *s1, *s2;

    if ( !*str2 ) // *str2 != '\0' 
        return((char *)str1);

    while (*cp) // cp != NULL
    {
        s1 = cp;
        s2 = (char *) str2;


        while ( *s1 && *s2 && !(*s1-*s2) ) // (*s1 != '\0') && (*s2 != '\0') && (*s1 == *s2)
                s1++, s2++;

        if (!*s2) // *s2 == '\0'
                return(cp);

        cp++;
    }
    return(NULL);
}

const char* bf_match(const char* txt, const char* pat){
	int pt=0, pp=0;

	while(txt[pt] && pat[pp]){
		if(txt[pt]==pat[pp])
			pt++, pp++;
		else{
			pt=pt-pp+1;
			pp=0;
		}
	}

	if(!pat[pp])
		return txt+(pt-pp);

	return NULL;
}

const char* kmp_match(const char* txt, const char* pat){
	int pt=1, pp=0, skip[1024];

	skip[pt]=0;

	while(pat[pt]){
		if(pat[pt]==pat[pp])
			skip[++pt]=++pp;
		else if(pp==0)
			skip[++pt]=pp;
		else
			pp=skip[pp];
	}

	pt=pp=0;

	while(txt[pt] && pat[pp]){
		if(txt[pt]==pat[pp])
			pt++, pp++;
		else if(pp==0)
			pt++;
		else
			pp=skip[pp];
	}

	if(!pat[pp])
		return txt+(pt-pp);

	return NULL;

}

const char* bm_match(const char* txt, const char* pat){
	int pt, pp, txt_len=strlen(txt), pat_len=strlen(pat);

	int skip[UCHAR_MAX + 1];

	for(pt=0; pt<=UCHAR_MAX; pt++)
		skip[pt]=pat_len;

	for(pt=0; pt<pat_len-1; pt++)
		skip[pat[pt]]=pat_len-pt-1;

		

	while(pt<txt_len){
		pp=pat_len-1;
		while(txt[pt]==pat[pp]){
			if(!pp)
				return txt+pt;

			pp--;
			pt--;

		}
		pt+=(skip[txt[pt]] > pat_len-pp) ? skip[txt[pt]] : pat_len-pp;
	}

	return NULL;
}

int main() {
	// your code goes here
	const char* txt="KinggodZero";
	const char* pat="godZ";

	int len=strlen(pat);

	cout<<"원본 텍스트 : "<<txt<<'\n';

	Timer timer;
	timer.start();
	const char* rslt1=mystrstr(txt, pat);
	timer.stop();

	cout<<"mystrstr 함수\n";
	if(rslt1){
		cout<<"찾은 패턴 : ";
		for(int i=0;i<len;i++)
			cout<<rslt1[i];
		cout<<'\n';
	}
	else
		cout<<"패턴을 찾지 못하였습니다.\n";

	cout<<"수행시간 (nano second) : "<<timer.get_nano()<<" nanoseconds\n";

	timer.start();
	rslt1=strstr(txt, pat);
	timer.stop();

	cout<<"\nstrstr 함수\n";
	if(rslt1){
		cout<<"찾은 패턴 : ";
		for(int i=0;i<len;i++)
			cout<<rslt1[i];
		cout<<'\n';

	}
	else
		cout<<"패턴을 찾지 못하였습니다.\n";

	cout<<"수행시간 (nano second) : "<<timer.get_nano()<<" nanoseconds\n";

	timer.start();
	rslt1=bf_match(txt, pat);
	timer.stop();

	cout<<"\nbf_match 함수\n";

	if(rslt1){
		cout<<"찾은 패턴 : ";
		for(int i=0;i<len;i++)
			cout<<rslt1[i];
		cout<<'\n';
	}
	else
		cout<<"패턴을 찾지 못하였습니다.\n";

	cout<<"수행시간 (nano second) : "<<timer.get_nano()<<" nanoseconds\n";

	timer.start();
	rslt1=kmp_match(txt, pat);
	timer.stop();

	cout<<"\nkmp_match 함수\n";

	if(rslt1){
		cout<<"찾은 패턴 : ";
		for(int i=0;i<len;i++)
			cout<<rslt1[i];
		cout<<'\n';

	}
	else
		cout<<"패턴을 찾지 못하였습니다.\n";

	cout<<"수행시간 (nano second) : "<<timer.get_nano()<<" nanoseconds\n";

	timer.start();
	rslt1=bm_match(txt, pat);
	timer.stop();

	cout<<"\nbm_match 함수\n";

	if(rslt1){
		cout<<"찾은 패턴 : ";
		for(int i=0;i<len;i++)
			cout<<rslt1[i];
		cout<<'\n';
	}
	else
		cout<<"패턴을 찾지 못하였습니다.\n";

	cout<<"수행시간 (nano second) : "<<timer.get_nano()<<" nanoseconds\n";

	return 0;
}