C++ sort 인덱스도 정렬하기

프로그래밍을 배우면서 아마도 가장 처음 접하게 되는 알고리즘이 바로 정렬 알고리즘이 아닌가 생각되네요.

 

C++ 에서는 algorithm 헤더에 sort, stable_sort, partial_sort 와 같은 함수들이 정의되어 있습니다.

 

C++ STL 이 참 좋긴 하더군요. ㅋㅋㅋㅋ

 

partial_sort 는 말 그대로 일부를 정렬하겠다는 거로 이해하시면 될 것 같고

 

저는 처음에 sort 와 stable_sort 가 좀 헷갈리더군요. 무슨 차이일까… 하고요.

 

차이는 간단한데요. 동일한 값이 있을 경우 stable_sort 의 경우에는 정렬 하기 전의 순서가 정렬후에도 유지된다고 하더군요.

 

위 함수들의 사용법 등에 대해서는 아래 주소의 예제들을 참조하시면 쉽게 이해하실 겁니다.

 

http://www.cplusplus.com/reference/algorithm/sort/

http://www.cplusplus.com/reference/algorithm/stable_sort/

http://www.cplusplus.com/reference/algorithm/partial_sort/

 

저는 오늘 MATLAB 의 sort() 결과와 마찬가지로 정렬 결과 뿐만 아니라 인덱스도 정렬되어 나올 수 있도록 구성해 보도록 하겠습니다.

 

C++ 에서는 이런 경우 인덱스와 값을 pair 로 묶은 후에 정렬하는 방법이 있더군요.

 

예제는 다음과 같습니다. 아래 예제처럼 comparator 만 오름 차순 내림 차순에 따라 잘 설정하면 되더군요.

 

#include <iostream>

#include <vector>

#include <algorithm>

#include <random>

#include <ctime>

 

 

using namespace std;

 

 

#define N_SIZE (10)

 

 

typedef std::pair<int,int> int_int_pair;

 

bool comparator ( const int_int_pair& l, const int_int_pair& r) // 첫번째 값을 기준으로 내림차순 비교하는 comparator

{

return l.first > r.first;

}

 

 

 

int main()

{

vector<int_int_pair> A; // vector setting

 

srand( unsigned(time (NULL)));

 

for (int i=0; i<N_SIZE ; i++)

{

A.push_back(int_int_pair(i,i)); // (value, index) setting

}

 

random_shuffle(A.begin(), A.end()); // 마구 마구 섞기

 

 

cout << "정렬전\nValue\tIndex\n" ;

 

for (int i=0; i<N_SIZE ; i++) // 섞인거 확인하기

{

cout << A[i].first << "\t" << A[i].second << endl;

}

 

cout << "\n\n" ;

 

 

stable_sort(A.begin(),A.end(), comparator); // 정렬 하기

 

cout << "정렬후\nValue\tIndex\n" ;

for (int i=0; i<N_SIZE ; i++) // 정렬됐나 확인하기

{

cout << A[i].first << "\t" << A[i].second << endl;

}

 

return 0;

}

 

위 코드에 따라 다음과 같이 내림 차순 정렬 되게 됩니다.