[게임알고리즘] 2-2강 정렬 실습 예제

 

1. 아이템을 생성하고, 가격순으로 정렬하기

#include "Sort.h"
 
#include <stdlib.h>
#include <time.h>
 
enum ItemType {
    Armour = 0, Sword, Shield, Potion,
    ItemTypeMax
};
 
enum ItemGrade {
    Normal = 0, Rare, Legend,  
    ItemGradeMax
};
 
struct ItemInfo {
    ItemType t;
    ItemGrade g;
    int price;
    int o;
};
 
int main() {
    
    unsigned seed = time(NULL);
    srand(seed);
    
    ItemInfo* itemInfo = new ItemInfo[100];
    for(int i=0; i<100; i++)
    {
        ItemInfo* ii = &itemInfo[i];
        ii->t = (ItemType)(rand() % ItemTypeMax);
        ii->g = (ItemGrade)(rand() % ItemGradeMax);
        ii->price = (1 + rand() % 20) * 500;
        ii->o = i;
    }
    
    const char* strType[] = { "갑옷", "칼", "방패", "포션" };
    const char* strGrade[] = { "노멀", "레어", "전설" };
    
    Sort s;
    s.init(bubble);
    for(int i=0; i<100; i++)
    {
        ItemInfo* ii = &itemInfo[i];
        s.add(ii, ii->price);
    }
    s.update();
    for(int i=0; i<s.num; i++)
    {
        ItemInfo* ii = (ItemInfo*)s.get(i);
        printf("%s%d %s %d\n", 
            strType[ii->t], ii->o, strGrade[ii->g], ii->price);
    }
    
    delete itemInfo;
 
    return 0;
}

 

2. 가격이 순서를 유지한 상태에서 희귀도 정렬하기(문제발생)

등급 정렬 start ~ end가 추가함.

실행하면, 데이터가 엉키는 현상이 발생함.

70 라인을 유심히 볼 필요가 있음.

#include <stdlib.h>
#include <time.h>
#include <string.h>
 
enum ItemType {
    Armour = 0, Sword, Shield, Potion,
    ItemTypeMax
};
 
enum ItemGrade {
    Normal = 0, Rare, Legend,  
    ItemGradeMax
};
 
struct ItemInfo {
    ItemType t;
    ItemGrade g;
    int price;
    int o;
};
 
int main() {
    
    unsigned seed = time(NULL);
    srand(seed);
    
    ItemInfo* itemInfo = new ItemInfo[100];
    for(int i=0; i<100; i++)
    {
        ItemInfo* ii = &itemInfo[i];
        ii->t = (ItemType)(rand() % ItemTypeMax);
        ii->g = (ItemGrade)(rand() % ItemGradeMax);
        ii->price = (1 + rand() % 20) * 500;
        ii->o = i;
    }
    
    const char* strType[] = { "갑옷", "칼", "방패", "포션" };
    const char* strGrade[] = { "노멀", "레어", "전설" };
    
    Sort s;
    s.init(bubble);
    for(int i=0; i<100; i++)
    {
        ItemInfo* ii = &itemInfo[i];
        s.add(ii, ii->price);
    }
    s.update();
    // =========================== 등급 정렬 start
    Sort s2;
    for(int i=0, off=0, curr=500; i<100; i++)
    {
        ItemInfo* ii = (ItemInfo*)s.get(i);
        if(curr != ii->price)
        {
            int a = off;
            int b = i-1;
            off = i;
            
            s2.init(selection);
            int k = b+1;
            for(int j=a; j<k; j++)
            {
                ii = (ItemInfo*)s.get(j);
                s2.add(ii, ii->g);
            }
            s2.update();
            for(int j=0; j<s2.num; j++)
            {
                // s.get(a+j) = s2.get(j)
                memcpy(s.get(a+j), s2.get(j), sizeof(ItemInfo));
            }
        }
    }
    // =========================== 등급 정렬 end
    for(int i=0; i<s.num; i++)
    {
        ItemInfo* ii = (ItemInfo*)s.get(i);
        printf("%s%d %s %d\n", 
            strType[ii->t], ii->o, strGrade[ii->g], ii->price);
    }
    
    delete itemInfo;
 
    return 0;
}

 

3. 가격이 순서를 유지한 상태에서 희귀도 정렬하기(해결)

마지막 목록 가격이 curr과 동일할 경우, 마지막 가격대의 목록은 호출되지 않기 때문에,

시작값off가 99보다 작고, 마지막 목록 i==99일때도 정렬이 호출되도록 함.

 

같은 가격내에 희귀도에 따라 정렬된 목록을 Data* tmp에 복사한 다음,

Data* tmp 원래 목록에 복사하여 문제점 해결함.

#include <stdlib.h>
#include <time.h>
#include <string.h>
 
enum ItemType {
    Armour = 0, Sword, Shield, Potion,
    ItemTypeMax
};
 
enum ItemGrade {
    Normal = 0, Rare, Legend,  
    ItemGradeMax
};
 
struct ItemInfo {
    ItemType t;
    ItemGrade g;
    int price;
    int o;
};
 
int main() {
    
    unsigned seed = time(NULL);
    srand(seed);
    
    ItemInfo* itemInfo = new ItemInfo[100];
    for(int i=0; i<100; i++)
    {
        ItemInfo* ii = &itemInfo[i];
        ii->t = (ItemType)(rand() % ItemTypeMax);
        ii->g = (ItemGrade)(rand() % ItemGradeMax);
        ii->price = (1 + rand() % 20) * 500;
        ii->o = i;
    }
    
    const char* strType[] = { "갑옷", "칼", "방패", "포션" };
    const char* strGrade[] = { "노멀", "레어", "전설" };
    
    Sort s;
    s.init(bubble);
    for(int i=0; i<100; i++)
    {
        ItemInfo* ii = &itemInfo[i];
        s.add(ii, ii->price);
    }
    s.update();
    // =========================== 등급 정렬 start
    Sort s2;
    Data* tmp = new Data[100];// 추가
    for(int i=0, off=0, curr=500; i<100; i++)
    {
        ItemInfo* ii = (ItemInfo*)s.get(i);
        if(curr != ii->price ||
          (i==99 && off<99))// 추가
        {
            if(i==99) i++;// 추가
            
            int a = off;
            int b = i-1;
            off = i;
            curr = ii->price;
 
            s2.init(selection);
            int k = b+1;
            for(int j=a; j<k; j++)
            {
                ii = (ItemInfo*)s.get(j);
                s2.add(ii, ii->g);
            }
            s2.update();
#if 0
            for(int j=0; j<s2.num; j++)
            {
                // s.get(a+j) = s2.get(j)
                memcpy(s.get(a+j), s2.get(j), sizeof(ItemInfo));
            }
#else
            for(int j=0; j<s2.num; j++)
                memcpy(&tmp[j], s2.get(j), sizeof(ItemInfo));
            for(int j=0; j<s2.num; j++)
                memcpy(s.get(a+j), &tmp[j], sizeof(ItemInfo));
#endif
        }
    }
    delete tmp;// 추가
    // =========================== 등급 정렬 end
    for(int i=0; i<s.num; i++)
    {
        ItemInfo* ii = (ItemInfo*)s.get(i);
        printf("%s%d %s %d\n", 
            strType[ii->t], ii->o, strGrade[ii->g], ii->price);
    }
    
    delete itemInfo;
 
    return 0;
}

 

 

4. 우선 순위가 높은 조건 순으로 파라미터를 넣어 정렬

void sortItem(ItemInfo* ii, int n, const char* szFormat, ...);

 

예시) sortItme(itemInfo, 100, "Type\nGrade\nPrice");

itemInfo 100개를 아이템 타입을 최우선으로 정렬하고, 같은 타입내에 아이템들을 다시 등급별 정렬한다.

등급별 정렬된 목록은 최종적으로 가격별로 정렬한다.

 

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