[게임알고리즘] 2-1강 정렬 다듬기 최종

수업시간에 작성한 코드를 백업하기 전, 강의실 컴퓨터가 오후 5시에 갑작스러운 셧다운이 발생해서 최대한 기억을 더듬어 코드를 재현했기 때문에 수업시간에 작성한 코드가 다를 수 있으니 양해부탁드립니다.

 

1-4강 정렬 함수에 전달하는 파라미터에 따라, 동일한 함수를 사용할 수 없고 유사 코드를 중복 사용하는 경우가 발생함.

정렬을 사용하기 편하기 만들고, 원하는 정렬 방식을 실행할때 선택할 수 있도록 개선.

 

1. Sort.h, Sort.cpp 사용하기 편하게 제작

Sort.h 파일

#include <stdio.h>
 
struct Data {
    void* data;
    float y;
};
 
struct Sort
{
    Sort(int max = 300);
    virtual ~Sort();
    
    void init();
    void add(void* data, float y);
    void* get(int index);
    void update();
    
    Data* data;
    int num;
};
 

 

Sort.cpp 파일

#include "Sort.h"
 
Sort::Sort(int max)
{
    data = new Data[max];
    num = 0;
}
Sort::~Sort()
{
    delete data;
}
void Sort::init()
{
    num = 0;
}
void Sort::add(void* data_, float y)
{
    Data* d = &data[num];
    num++;
    
    d->data = data_;
    d->y = y;
}
void* Sort::get(int index)
{
    return data[index].data;    
}
void Sort::update()
{
    int k = num-1;
    for(int i=0; i<k; i++)
    {
        for(int j=1+i; j<num; j++)
        {
            if( data[i].y > data[j].y )
            {
                Data t = data[i];
                data[i] = data[j];
                data[j] = t;
            }
        }
    }
}
 

main.cpp

#include "Sort.h"
 
int main() {
    
    struct Monster {
        const char* name;
        float x, y;
        int att, def, dex;
    };
    Monster monster[] = {
        { "남기현",   7,  20, },
        { "양민석",  10,   5, },
        { "이보현", 120, 180, },
        { "팽재성", -80, 800, },
        { "전성준",  -5, 120, }
    };
    
    Sort s;
    s.init();
    for(int i=0; i<5; i++)
    {
        Monster* m = &monster[i];
        s.add(m, m->y);
    }
    s.update();
    for(int i=0; i<s.num; i++)
    {
        Monster* m = (Monster*)s.get(i);
        printf("%s %.f\n", m->name, m->y);
    }
    return 0;
}
 

 

 

2. 원하는 정렬 방식을 실행할때 선택할 수 있게 개선

s.init(bubble) 호출시, 원하는 SortType을 지정 가능.

 

Sort.h 파일

#include <stdio.h>
 
struct Data {
    void* data;
    float y;
};
 
typedef void (*MethodSort)(Data* d, int n);
 
enum SortType
{
    bubble = 0, selection, insertion,
    merge, quick, heap, counting,
};
 
struct Sort
{
    Sort(int max = 300);
    virtual ~Sort();
    
    void init(SortType st = bubble);
    void add(void* data, float y);
    void* get(int index);
    void update();
    
    Data* data;
    int num;
    
    MethodSort ms;
    SortType st;
    
    static void methodBubble(Data* d, int n);
    static void methodSelection(Data* d, int n);
    static void methodInsertion(Data* d, int n);
    static void methodMerge(Data* d, int n);
    static void methodQuick(Data* d, int n);
    static void methodHeap(Data* d, int n);
    static void methodCounting(Data* d, int n);
};

 

Sort.cpp 파일

#include "Sort.h"
 
Sort::Sort(int max)
{
    data = new Data[max];
    num = 0;
}
 
Sort::~Sort()
{
    delete data;
}
 
void Sort::init(SortType st)
{
    num = 0;
    MethodSort m[] = {
        methodBubble, methodSelection, methodInsertion,
        methodMerge, methodQuick, methodHeap, methodCounting,
    };
    ms = m[st];
    this->st = st;
}
 
void Sort::add(void* data_, float y)
{
    Data* d = &data[num];
    num++;
    
    d->data = data_;
    d->y = y;
}
 
void* Sort::get(int index)
{
    return data[index].data;    
}
 
void Sort::update()
{
    ms(data, num);
}
 
void Sort::methodBubble(Data* d, int n)
{
    int k = n-1;
    for(int i=0; i<k; i++)
    {
        for(int j=1+i; j<n; j++)
        {
            if( d[i].y > d[j].y )
            {
                Data t = d[i];
                d[i] = d[j];
                d[j] = t;
            }
        }
    }
}
void Sort::methodSelection(Data* d, int n){ methodBubble(d, n); }
void Sort::methodInsertion(Data* d, int n){ methodBubble(d, n); }
void Sort::methodMerge(Data* d, int n){ methodBubble(d, n); }
void Sort::methodQuick(Data* d, int n){ methodBubble(d, n); }
void Sort::methodHeap(Data* d, int n){ methodBubble(d, n); }
void Sort::methodCounting(Data* d, int n){ methodBubble(d, n); }
 

 

3. 정렬 속도 개선

Data* _data와 Data** data를 별도로 관리.

add 호출시 주소 대입 횟수 1번 늘어나지만, Swap시 주소값으로 변경되어 복사량이 절반(1/2)으로 줄어둘어 속도 향상.

 

Sort.h 파일

#include <stdio.h>
 
struct Data {
    void* data;
    float y;
};
 
typedef void (*MethodSort)(Data** d, int n);
 
enum SortType
{
    bubble = 0, selection, insertion,
    merge, quick, heap, counting,
};
 
struct Sort
{
    Sort(int max = 300);
    virtual ~Sort();
    
    void init(SortType st = bubble);
    void add(void* data, float y);
    void* get(int index);
    void update();
    
    Data* _data;
    Data** data;
    int num;
    
    MethodSort ms;
    SortType st;
    
    static void methodBubble(Data** d, int n);
    static void methodSelection(Data** d, int n);
    static void methodInsertion(Data** d, int n);
    static void methodMerge(Data** d, int n);
    static void methodQuick(Data** d, int n);
    static void methodHeap(Data** d, int n);
    static void methodCounting(Data** d, int n);
};
 

 

 

Sort.cpp 파일

#include "Sort.h"
 
Sort::Sort(int max)
{
    _data = new Data[max];
    data = new Data*[max];
    num = 0;
}
 
Sort::~Sort()
{
    delete _data;
    delete data;
}
 
void Sort::init(SortType st)
{
    num = 0;
    MethodSort m[] = {
        methodBubble, methodSelection, methodInsertion,
        methodMerge, methodQuick, methodHeap, methodCounting,
    };
    ms = m[st];
    this->st = st;
}
 
void Sort::add(void* data_, float y)
{
    Data* d = &_data[num];
    data[num] = d;
    num++;
    
    d->data = data_;
    d->y = y;
}
 
void* Sort::get(int index)
{
    return data[index]->data;    
}
 
void Sort::update()
{
    ms(data, num);
}
 
void Sort::methodBubble(Data** d, int n)
{
    int k = n-1;
    for(int i=0; i<k; i++)
    {
        for(int j=1+i; j<n; j++)
        {
            if( d[i]->y > d[j]->y )
            {
                Data* t = d[i];
                d[i] = d[j];
                d[j] = t;
            }
        }
    }
}
void Sort::methodSelection(Data** d, int n){ methodBubble(d, n); }
void Sort::methodInsertion(Data** d, int n){ methodBubble(d, n); }
void Sort::methodMerge(Data** d, int n){ methodBubble(d, n); }
void Sort::methodQuick(Data** d, int n){ methodBubble(d, n); }
void Sort::methodHeap(Data** d, int n){ methodBubble(d, n); }
void Sort::methodCounting(Data** d, int n){ methodBubble(d, n); }

 

 

4. Sort 함수 수정

static 함수들을 정렬 유형에 맞게 수정.

 

매일 매일 열심히 게임 개발하고 있습니다