std::sort의 정의와 기초 사용법
std::sort는 지정된 범위에 있는 데이터 요소를 기본적인 오름차순 또는 지정한 정렬 기준에 따라 정렬하는 함수입니다.
이 함수를 사용하기 위해서는 우선 다음과 같은 헤더파일을 포함해야 합니다.
#include <algorithm>이 함수의 정의는 다음과 같습니다.
template<class RandomAccessIterator>
void sort(
RandomAccessIterator first,
RandomAccessIterator last);위의 첫 번째 인자 first는 정렬할 범위의 첫 번째 요소의 주소를 지정하는 임의 액세스 Iterator입니다.
두 번째 인자 last는 정렬할 범위의 마지막 요소 다음 위치의 주소를 지정하는 임의 액세스 Iterator입니다.
정의에 사용된 단어를 보면 복잡한 것 같지만, 실제로 사용하는 코드를 보면 그렇지 않다는 걸 알게 될 것입니다.
정수 배열을 오름차순으로 정렬하는 예를 들어보겠습니다.
#include <iostream>
#include <algorithm>
using namespace std;
void print( int* arr, int N){
for(int i = 0; i < N; i++){
cout << arr[i] << " ";
}
cout << "\n";
}
int main() {
int arr1[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
sort(arr1, arr1+10); // 첫 번째부터 마지막까지 정렬
print(arr1, 10);
int arr2[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
sort( arr2+4, arr2+10); // 5번째부터 마지막까지 정렬
print(arr2, 10);
}우선 sort 함수에 필요한 정수 배열 요소의 주소를 지정하려면 어떤 값이 필요할까요?
이런 질문을 던져 보신다면 스치듯 떠오르는 단어가 생각이 날 겁니다.
바로 "포인터( pointer )"죠.
이 포인터가 위의 sort 함수 정의에 나오는 임의 액세스 Iterator입니다.
정수 배열을 정렬하기 위해선 원하는 데이터를 가리키는 포인터를 인자로 사용하면 됩니다.
위의 예문을 보면 첫 번째 정렬에서는 arr1 배열의 첫 번째 요소 주소( arr1 )부터 마지막 요소 다음의 위치( arr1+10 )를 인자로 주면 첫 번째부터 마지막 요소까지 오름차순으로 정렬합니다. ( 아래에서 얘기하겠지만, std::sort 함수는 오름차순으로 정렬하는 것이 기본 동작으로 정해져 있습니다. )
▼출력
1 2 3 4 5 6 7 8 9 10
두 번째 정렬에서는 5번째 요소에 접근하기 위해서 5번째 요소를 가리키는 포인터 arr2+4를 인자로 주었습니다.
그래서, 이번에는 5번째 요소부터 마지막 요소까지의 부분 데이터들만 정렬합니다.
▼출력
10 9 8 7 1 2 3 4 5 6
std::vector, std::list의 정렬
sort 함수의 인자인 Iterator(반복자)는 컨테이너의 요소에 접근하고, 접근하고자 하는 요소 간의 이동에 관한 기능을 갖고 있는 C++ 객체입니다.
Iterator를 구현하고 있는 기능에 따라 다음과 같이 나눠볼 수 있습니다.
- 입력 반복자(input iterator) : 읽기만 가능, 순방향 이동, 현 위치의 원소를 한 번만 읽을 수 있는 반복자
- 출력 반복자(output iterator) : 쓰기만 가능, 순방향 이동, 현 위치의 원소를 한 번만 쓸 수 있는 반복자
- 순방향 반복자(forward iterator) : 읽기/쓰기 모두 가능, 순방향 이동(
++)이 가능한 재할당될 수 있는 반복자 - 양방향 반복자(bidirectional iterator) : 읽기/쓰기 모두 가능, 순방향(
++)/역방향(--) 이동이 가능한 반복자 - 임의 액세스 반복자(random access iterator) : 읽기/쓰기 모두 가능, 임의 접근, 양방향 반복자 기능에
+, -, += , -=, []연산이 가능
이 중 sort 함수는 임의 액세스 Iterator를 인자로 받습니다.
이것은 sort에 사용되는 알고리즘이 임의 액세스 Iterator가 지원하는 기능을 필요로 하기 때문입니다.
그리고, 이전 항목의 C-style 배열에 대해 임의 액세스가 가능한 포인터( pointer )도, 이러한 배열에 대한 임의 액세스 반복자( random access iterator )라고 할 수 있습니다.
std::vector의 정렬
std::vector는 이 컨테이너의 첫 번째 요소를 지정하기 위해서 begin() 함수를 사용하고, 이 함수가 반환하는 객체가 임의 액세스 Iterator입니다.
그리고, end() 함수는 std::vector의 끝을 가리키는 임의 액세스 Iterator를 반환합니다.
vector<int> vec;
vec.push_back(10);
vector<int>::iterator iter = vec.begin();
vector<int>::iterator iterEnd = vec.end();
while( iter != iterEnd ){ // 모든 데이터를 순환하는 코드
cout << *iter;
iter++;
}여기서 주의할 점은 end() 함수가 가리키는 위치는 std::vector의 마지막 요소가 아니고 마지막 요소 다음의 위치라는 것입니다.
이 사실을 이용해 위의 코드와 같이 모든 멤버를 차례로 출력할 수도 있습니다.
만일, std::vector에 멤버가 하나도 없는 경우 이 vector의 begin()과 end()의 결과 값이 같습니다.
다음은, 10부터 1까지를 멤버로 갖고 있는 std::vector의 값들을 오름차순으로 정렬하는 예문입니다.
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> vec;
for(int i = 10; i > 0; i--){
vec.push_back(i);
}
sort( vec.begin(), vec.end()); // 오름차순으로 정렬
vector<int>::iterator iter = vec.begin();
vector<int>::iterator iterEnd = vec.end();
while( iter != iterEnd ){ // 출력
cout << *iter;
iter++;
}
}
std::list의 정렬
std::list의 정렬 방법도 std::vector의 경우와 아주 흡사합니다.
그렇지만, std::list의 begin()과 end() 함수가 되돌려주는 Iterator는 임의 접근 반복자가 아니라, 양방향 Iterator라는 차이가 있습니다.
list<int> li;
li.push_back(10);
sort(li.begin(), li.end()); // compile error그래서, 위의 코드는 불행하게도 컴파일되지 않습니다.
왜냐하면, sort는 인자로 임의 액세스 Iterator를 받기 때문입니다.
그래서, std::list는 sort 멤버 함수를 따로 제공해서 이 문제를 해결했습니다.
위 vector를 정렬하기 위해 사용했던 예문을 변경하면 다음과 같습니다.
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> li;
for(int i = 10; i > 0; i--){
li.push_back(i);
}
li.sort(); // 멤버 함수를 사용해서 정렬
list<int>::iterator iter = li.begin(); // 양방향 Iterator를 반환
list<int>::iterator iterEnd = li.end();
while( iter != iterEnd ){
cout << *iter;
iter++;
}
}
비교 함수를 이용한 정렬
지금까지의 예들은 배열의 멤버가 기본값인 오름차순으로만 정렬되었습니다.
만약 내림차순으로 정렬하고자 하면 어떻게 해야 될까요?
std::sort 함수의 두 번째 정의가 필요한 때입니다.
template<class RandomAccessIterator, class Compare>
void sort(
RandomAccessIterator first,
RandomAccessIterator last,
Compare pred);첫 번째, 두 번째 인자는 위에서 설명한 내용과 같습니다.
세 번째 인자 pred 연속적인 요소들의 위치를 비교하는 사용자 정의 함수 개체입니다.
두 개의 인자 A와 B를 받아서 A 다음에 B가 위치하면 true를 리턴하고, B 다음에 A가 위치하여야 하면 false를 리턴하는 사용자 정의 함수입니다.
int 타입의 내림차순 사용자 정의 함수는 다음과 같이 작성할 수 있습니다.
bool compare_by_descending(int A, int B){
return A > B;
}B가 A보다 작으면 true를 리턴해서, A 뒤에 B가 위치하는 순서가 맞다는 것을 알려주는 함수입니다.
위의 사용자 정의 함수를 사용하여 정수 배열을 내림차순으로 정렬하는 코드는 다음과 같습니다.
#include <algorithm>
void print( int* arr, int N){
for(int i = 0; i < N; i++){
cout << arr[i] << " ";
}
cout << "\n";
}
bool compare_by_descending(int A, int B){
return A > B;
}
int main() {
int arr1[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
sort(arr1, arr1+10, compare_by_descending); // 내림차순 정렬
print( arr1, 10 );
return 0;
}▼출력
10 9 8 7 6 5 4 3 2 1근데 우리는 정수뿐만이 아니라, 소수도 내림차순으로 정렬하고 싶을 겁니다.
그러자면 float, double 타입의 데이터 값들을 비교하는 함수를 만들어야 하니까, 위 compare_by_descending 함수와 비슷한 버전의 코드를 계속 작성해야 할 겁니다.
좀 더 효율적인 방법은 없을까요?
● C++에서는 위와 같은 문제를 해결하기 위해 greater<Type> 함수 개체( function object )를 제공합니다.
[C++] 함수 객체( function object, functor ) : operator()를 구현한 타입
함수 객체( function Object ) 함수 객체( function object )는 operator() 함수를 구현한 타입( type )을 말합니다. C++ 표준 라이브러리에서는, 펑터( functor )라고도 불리는, 이 타입을 주로 컨테이너나 알고리즘
codingbonfire.tistory.com
여기서 Type은 operator >를 지원하는 모든 형식입니다.
template <class Type = void>
struct greater : public binary_function <Type, Type, bool>
{
bool operator()(const Type& Left, const Type& Right) const;
};이 개체를 사용해서 타입이 변경되더라도 같은 코드를 사용해서 내림차순으로 정렬할 수 있게 됩니다.
마찬가지로, 오름차순 정렬을 쉽게 하기 위한 less<Type> 개체도 제공합니다. ( Type은 operator <를 지원하는 모든 형식 )
위 개체를 사용하면 위의 예제는 다음과 같이 간단하게 변경할 수 있습니다.
#include <functional> // for greater, less
int main() {
int arr1[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
sort(arr1, arr1+10, greater<int>()); // 내림차순 정렬( greater 함수객체 사용 )
return 0;
}예를 들어, float 형의 데이터를 내림차순으로 정렬하려면 greater<float> 개체를 사용하면 됩니다.
사용자 정의 클래스의 정렬
사용자 정의 데이터는 어떻게 처리해야 할까요?
학생들의 기말고사 성적을 수학이 가장 높은 학생이 위로 오고, 같은 성적인 경우 한국사 성적을 높은 순으로 정렬하여 게시판에 공개한다고 가정을 해 봅시다.
우선 다양한 성적을 저장할 클래스가 필요합니다.
class cStudant{
public:
cStudant(const string& str, int A, int B){
name = str; math = A; history = B;
}
string name;
int math;
int history;
};그리고 클래스가 담고 있는 성적을 원하는 방식으로 정렬하는 함수가 필요합니다.
정렬을 위한 사용자 비교 함수는 다음과 같을 것입니다.
bool compre_studant( const cStudant& A, const cStudant& B){
if ( A.math == B.math){
return A.history > B.history;
}
else{
return A.math > B.math;
}
}이제 sort 함수를 호출하면 클래스 데이터를 정렬할 수 있습니다.
int main() {
vector<cStudant> vec;
vec.push_back( cStudant("A", 95, 98));
vec.push_back( cStudant("B", 90, 85));
vec.push_back( cStudant("C", 83, 80));
vec.push_back( cStudant("D", 95, 92));
vec.push_back( cStudant("E", 95, 95));
sort( vec.begin(), vec.end(), compare_studant);
}
● 다른 방식으로는, 클래스 내에 operator를 정의하는 방법이 있습니다.
이 방식의 장점은 데이터의 순서를 결정하는 알고리즘을 클래스 내부로 감출 수 있고, 이전 항목에서 설명한 greater, less 함수 객체를 사용해 오름차순에서 내림차순으로 변경도 간단히 할 수 있습니다.
먼저, less 객체( 오름차순, 기본값 )를 사용하기 위해선 클래스가 operator < 을 지원해야 합니다.
less 객체를 사용하지 않더라도, sort 함수는 내부적으로 오름차순 정렬을 합니다.
그렇기 때문에 sort 함수 호출 시 사용자 함수를 따로 사용하지 않으면, 반드시 사용자 클래스에서 operator <를 지원해야 합니다. ( 이 연산자를 지원하지 않으면, sort 함수 호출 시 컴파일 오류가 발생됩니다. )
class cStudant{
public:
cStudant(const string& str, int A, int B){
name = str; math = A; history = B;
}
string name;
int math;
int history;
// < 연산자 지원
bool operator < (const cStudant& other) const {
if ( math == other.math){
return history < other.history;
}
else{
return math < other.math;
}
}
};이제, cStudant 객체를 std::sort 함수를 이용해 오름차순으로 정렬할 수 있습니다.
vector<cStudant> vec;
vec.push_back( cStudant("A", 90, 85));
vec.push_back( cStudant("B", 90, 85));
vec.push_back( cStudant("C", 83, 80));
vec.push_back( cStudant("D", 95, 92));
vec.push_back( cStudant("E", 95, 95));
sort( vec.begin(), vec.end()); // 오름차순으로 정렬된다
그리고, greater( 내림차순 ) 객체를 사용하기 위해선, 클래스가 operator >을 지원해야 합니다.
bool operator > (const cStudant& other) const {
if ( math == other.math){
return history > other.history;
}
else{
return math > other.math;
}
}
학생 성적 정렬 코드 전체
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class cStudant{
public:
cStudant(const string& str, int A, int B){
name = str; math = A; history = B;
}
string name;
int math;
int history;
// 오름차순 (less)
bool operator < (const cStudant& other) const {
if ( math == other.math){
return history < other.history;
}
else{
return math < other.math;
}
}
// 내림차순 (greater)
bool operator > (const cStudant& other) const {
if ( math == other.math){
return history > other.history;
}
else{
return math > other.math;
}
}
};
int main() {
vector<cStudant> vec;
vec.push_back( cStudant("A", 95, 98));
vec.push_back( cStudant("B", 90, 85));
vec.push_back( cStudant("C", 83, 80));
vec.push_back( cStudant("D", 95, 92));
vec.push_back( cStudant("E", 95, 95));
//sort( vec.begin(), vec.end(), less<cStudant>()); // default (오름차순)
sort( vec.begin(), vec.end(), greater<cStudant>()); // 내림차순
vector<cStudant>::iterator iter = vec.begin(); // 출력
while(iter != vec.end()){
cout << iter->name << " " << iter->math << " " << iter->history << "\n";
iter++;
}
return 0;
}
