배열의 정렬

#include <algorithm>

int N=배열길이;

// 기본 오름차순
std::sort(arr, arr+N); 

// 내림차순
bool comp(int a, int b){return a>b;}
std::sort(arr, arr+N, comp); //comp 함수 기준

벡터의 정렬

#include <algorithm>

std::sort(vec.begin(), vec.end());

클래스의 정렬(연산자 오버로딩)

클래스는 연산자 오버로딩으로 해당 연산자를 쓸때 수행할 기능을 정해둘 수 있다. 연산자도 일종의 함수이므로 오버로딩이 가능한 것이다. sort함수에서는 ‘<’연산자로 두 원소의 우선순위를 비교한다.

#include <algorithm>

class A{
public:
    int x;
    int y;
    bool operator<(const A& a) const{ //연산자 오버로딩
        return this->x < a.x; //오름차순
    }
};

A a[100];
std::sort(A,A+100);

2차원 데이터의 정렬

하위 배열을 원소로 보고 정렬을 하는 것이다. 원소의 수가 일정하고 적다면 pair나 위처럼 class를 사용하자.

pair 정렬

#include <algorithm>
#include <utility> //pair가 존재

vector<pair<int,int>> v;

bool comp(pair<int,int> &p1, pair<int,int> &p2){return p1.first<p2.first;}
sort(v.begin(), v.end(), comp);

포인터 배열 정렬

하지만 위에 2차원 배열의 정렬이나 클래스의 정렬에서 원소의 크기가 클 때 발생하는 문제가 있다. 바로 원소의 위치가 바뀔때 복사 연산을 하는데 이때 원소의 크기에 따라 오버헤드가 생길 수 있다는 것이다. 64bit 운영체제에서는 포인터는 8바이트이다. 이는 int 2개에 해당하는데 그것보다 크다면 원소를 포인터로 저장하는 것은 고려해볼만한 일이다.

#include <iostream>
#include <algorithm>
using namespace std;

class A{
public:
    int x,y,z,a,b,c;
	A(int x, int y, int z, int a, int b, int c):x(x),y(y),z(z),a(a),b(b),c(c){}
};

bool comp(A *a, A *b){
    return a->x < b->x;
}

int main(){
	//배열 생성
	A *arr[100];
	for(int i=0; i<100; i++){
		arr[i] = new A(i%5,i%5,i%5,i%5,i%5,i%5);
		cout<<arr[i]->x; //처음에는 정렬되지 않았다
	}

    //정렬
	sort(arr, arr+100, comp);

	cout<<'\n';
	//배열 소멸
	for (int i = 0; i < 100; ++i) {
		cout<<arr[i]->x; //정렬이 되었다
		delete arr[i]; 
	}
	return 0;
}