C++ 다양한 타입의 collection들의 정렬은 어떤 식으로 되는건지 직접해보고, 몇 가지 내용을 정리해 볼 것이다.
실험 1) 배열에 무작위 int 값 넣고 sorting
#include <iostream>
using namespace std;
#include <time.h>
#include <string>
int compareInt(const void *x, const void *y) // 값 읽기만
{
int *p = (int *)x;
int *q = (int *)y;
return *p - *q;
}
void main()
{
int x[10];
srand((int)time(NULL)); //seeding - time, process id
for (int i = 0; i < 10; i++) {
x[i] = rand() % 100; // pseudo random number
}
for (int i = 0; i < 10; i++) cout << x[i] << " ";
cout << endl;
qsort(x, 10, sizeof(int), compareInt);
for (int i = 0; i < 10; i++) cout << x[i] << " ";
cout << endl;
}10개의 무작위 수를 넣어줄 배열 x를 하나 만들어준다.
무작위 수를 생성하려면 rand() 함수를 통해 얻어올 수 있는데, 수가 크므로 100미만의 수들로 만들어준다.
여기서 rand() 함수로만 난수를 얻어온다면 무작위의 수처럼 보이긴 하지만 진정한 의미의 무작위 수는 아니다. 무슨 의미냐면 이렇게 얻어온 랜덤 수는 무작위임에도 불구하고 규칙이 있기 때문에 다른 시간, 다른 장소에서도 똑같은 랜덤 수들을 만들어 낼 수 있다.
그래서 진정한 랜덤 숫자를 얻고자 한다면 seeding 이라는 작업을 거쳐줘야 한다. 씨를 뿌려준다/깔아준다 정도로 해석이 가능한데, srand()라는 함수로 seeding이 가능하다. 함수안에 들어갈 인자로는 값이 항상 고정되어 있지는 않은 프로세스 id라던지, 계속 바뀌는 시간 같은 수를 넣어주면 예측 불가능한 난수를 얻을 수 있게 된다. 만약 srand()에 고정된 수를 넣어준다면 seeding은 시행하지만 다른곳에서 같은 수로 seeding을 할 경우 같은 결과 값을 얻게 되므로 이 역시 예측 가능한 랜덤 수를 만들어낸다.
이제 랜덤 수가 담긴 배열 x를 출력시켜주고 정렬을 한 후 다시 출력 시켜볼것이다.
qsort() 라는 함수를 사용할 것인데, 파라미터로는 위에 명시된 대로 자료구조/요소의 수/요소의 사이즈/compare를 시행할 FunctionPointer를 넘겨주게 된다.
compareInt() 함수를 보면, formal parameter로 들어온 값들이 const로 설정되는데, void *x와 void *y를 상수화 시켜서 수정할수 없게 만들어주는 것이다.
int의 포인터로 casting한 x와 y를 각각 *p, *q에 넣고 그 *p, *q를 빼줌으로써 sorting함수의 역할을 한다.
여기서 p와 q를 dereferencing 하지 않는다면 주소값을 sorting하게 되므로 역참조를 반드시 해준다.
실험 2) char 포인터의 array를 만들어 글자 sorting하기
#include <iostream>
using namespace std;
#include <time.h>
#include <string>
int compareCharPointer(const void *x, const void *y)
{
char *p = *(char **)x;
char *q = *(char **)y;
return strcmp(p, q);
}
void main()
{
char* x[5];
x[0] = "grape";
x[1] = "peach";
x[2] = "mango";
x[3] = "apple";
x[4] = "banana";
for (int i = 0; i < 5; i++) cout << x[i] << " ";
cout << endl;
qsort(x, 5, sizeof(char*), compareCharPointer);
for (int i = 0; i < 5; i++) cout << x[i] << " ";
cout << endl;
}배열 x에 문자들을 넣고 알파벳 사전순으로 정렬할 것이다. 전체적인 윤곽은 int 정렬할때와 같다. 다만 이제 compareCharPointer() 함수에서 *p에 x의 포인터를 가리키는 char 포인터로 타입캐스팅한 곳의 값을 넣어주고 *q도 같은 작업을 해준다.
그리고 strcmp를 통해 값 비교를 해준다.
실험 3) string의 array와 string pointer의 array의 값 sorting
#include <iostream>
using namespace std;
#include <time.h>
#include <string>
int compareString(const void *x, const void *y)
{
string p = *(string *)x;
string q = *(string *)y;
if (p > q) return 1;
else if (p < q) return -1;
else return 0;
}
int compareStringPointer(const void *x, const void *y)
{
string *p = *(string **)x;
string *q = *(string **)y;
if (*p > *q) return 1; //dereferencing 안하면 주소값 sorting
else if (*p < *q) return -1;
else return 0;
}
void main()
{
/*
string* x[5];
x[0] = new string("사과");
x[1] = new string("가지");
x[2] = new string("복숭아");
x[3] = new string("포도");
x[4] = new string("애호박");
for (int i = 0; i < 5; i++) cout << *x[i] << " ";
cout << endl;
qsort(x, 5, sizeof(string*), compareStringPointer);
for (int i = 0; i < 5; i++) cout << *x[i] << " ";
cout << endl;*/
string x[5];
x[0] = string("사과");
x[1] = string("가지");
x[2] = string("복숭아");
x[3] = string("포도");
x[4] = string("애호박");
for (int i = 0; i < 5; i++) cout << x[i] << " ";
cout << endl;
qsort(x, 5, sizeof(string), compareString);
for (int i = 0; i < 5; i++) cout << x[i] << " ";
cout << endl;
}
string과 string pointer의 배열을 각각 정렬해보겠다.
값을 다루는 메모리 영역이 다르기에 포인터를 가리키는 것에 있어서 차이가 있다.
결과는 둘다 아래와 같다.
실험 5) 클래스의 member 값 sorting
#include <iostream>
using namespace std;
#include <time.h>
#include <string>
class Student
{
static int method;
string name;
int score;
public:
Student()
{
name = "";
score = 0;
}
Student(string name, int score)
{
this->name = name;
this->score = score;
}
static void sortBy(int m) {
method = m;
}
friend ostream& operator<<(ostream& out, Student &st);
friend int compareStudent(const void *x, const void *y);
};
#define NAME (0)
#define SCORE (1)
int Student::method = NAME;
int compareStudent(const void *x, const void *y)
{
Student p = *(Student *)x;
Student q = *(Student *)y;
if (Student::method == NAME) {
if (p.name > q.name) return 1;
else if (p.name < q.name) return -1;
else return 0;
}
else if (Student::method == SCORE) {
return p.score - q.score;
}
}
ostream& operator<<(ostream& out, Student &st)
{
out << st.name << ", " << st.score << "; ";
return out;
}
void main()
{
Student st[5];
st[0] = Student("kim", 30);
st[1] = Student("lee", 50);
st[2] = Student("park", 10);
st[3] = Student("kwon", 70);
st[4] = Student("oh", 40);
for (int i = 0; i < 5; i++) cout << st[i] << " ";
cout << endl;
Student::sortBy(NAME);
qsort(st, 5, sizeof(Student), compareStudent);
for (int i = 0; i < 5; i++) cout << st[i] << " ";
cout << endl;
Student::sortBy(SCORE);
qsort(st, 5, sizeof(Student), compareStudent);
for (int i = 0; i < 5; i++) cout << st[i] << " ";
cout << endl;
}이름과 점수를 데이터 변수로 가지는 Student 클래스가 있다.
이 Student를 이름과 점수에 따라 각각 정렬해보겠다.
먼저 배열 st에 다섯명의 Student 정보를 저장한다. 다른건 다 같지만 무엇을 기준으로 sorting할지 정하기 위해서 Student 클래스에 있는 sortBy() 함수를 sorting 전 시행해준다.
Student 클래스에 static 멤버 값으로 method라는 것을 두고, NAME과 SCORE를 매크로로 미리 정의한 후, sorting이 필요할 때마다 method 값을 해당 매크로 값으로 바꿔서 처리해 줄 수 있게 한다. 디폴트 값으로는 NAME이 되도록 메인함수 바깥에 초기화 시켜준다.
compareStudent() 메서드에선 method 값에 따라 각각의 데이터 멤버를 비교하게 하면 된다.
operator overloading <<으로 클래스 내용을 출력해주는 form을 만들어주고 실행시켜보면
다음과 같은 결과가 나온다.
첫번째 라인은 원본 값이 입력된 순서대로의 출력결과이고, 두번째 라인은 이름순으로 정렬한 결과이며, 세번째 라인은 점수 오름차순의 결과이다.
실험 6) LinkedList에 클래스 데이터를 담아 정렬하기
#include <iostream>
#include <list>
#include <string>
using namespace std;
template <class T>
ostream& operator<<(ostream& out, list<T> &l1)
{
list<T>::iterator it = l1.begin();
while (it != l1.end()) {
out << *it << " ";
it++;
}
out << endl;
return out;
}
#define NAME (0)
#define GRADE (1)
class Student
{
static int method;
string name;
int grade;
public:
Student()
{
name = "";
grade = 0;
}
Student(string n, int g)
{
name = n;
grade = g;
}
bool operator>(Student other)
{
if (method == NAME)
return name > other.name;
if (method == GRADE)
return grade > other.grade;
}
bool operator<(Student other)
{
if (method == NAME)
return name < other.name;
if (method == GRADE)
return grade < other.grade;
}
static void sortBy(int m)
{
method = m;
}
friend ostream& operator<<(ostream& out, Student &l1);
};
int Student::method = NAME;
ostream& operator<<(ostream& out, Student &st)
{
out << st.name << ", " << st.grade << " ;";
return out;
}
void main()
{
list<Student> st;
st.push_back(Student("kim", 20));
st.push_back(Student("park", 50));
st.push_back(Student("lee", 70));
st.push_back(Student("oh", 30));
st.push_back(Student("choi", 40));
cout << st;
Student::sortBy(NAME);
st.sort();
cout << st;
Student::sortBy(GRADE);
st.sort();
cout << st;
/*
list<string> l2;
l2.push_back(string("kim"));
l2.push_back(string("lee"));
l2.push_back(string("park"));
l2.push_back(string("kwon"));
l2.push_back(string("oh"));
cout << l2;
l2.sort();
cout << l2;*/
/*list<int> l1;
for (int i = 0; i < 10; i++) l1.push_back(rand()%100);
cout << l1;
l1.sort();
cout << l1;*/
/*
list<int>::iterator it = l1.begin();
while (it != l1.end()) {
cout << *it << " ";
it++;
}
cout << endl;*/
}마지막으로 리스트에 다양한 타입들의 데이터들을 넣고 위의 내용들과 마찬가지의 방식들로 정렬해보았다.
정렬 후 리스트 내용 출력하는 부분만 보자면
리스트의 템플릿 타입의 레퍼런스 l1을 받아 traverse하며 it 값들을 출력시켜준다.
댓글