[알고리즘 개념정리] 1. 정렬 (sort STL), 특정 변수 기준으로 정렬하기

**본 포스팅은 22Winter 신촌캠프 초급반 강사 dart님의 강의를 참고하여 작성하였습니다.**

 

 

sort 함수

시간복잡도 : O(nlogn)을 보장함.

정렬방식 : 퀵정렬

              원소 개수가 특정 이하이면 삽입정렬, 중간이면 퀵정렬, 이상이면 힙정렬 사용

 

 

 

오름차순 정렬

  sort([배열의 시작 주소], [배열의 마지막 주소+1]);

sort(arr,arr+N);

내림차순 정렬

 

 방법 1. sort([배열의 시작 주소], [배열의 마지막 주소+1], greater <>());

sort(arr, arr+N, greater<>());

 

 방법 2. sort() 후 reverse();

sort(arr, arr+N);
reverse(arr, arr+N);

 

 방법 3. compare함수 구현 

bool compare (int a, int b){
	return a > b;
}
...
sort(arr, arr+N, compare);

 

 

 

 

특정 변수 기준으로 정렬하기

 

방법 1. 비교 함수 정의

struct Point{
    int x;
    int y;
}point[10];

bool compare(const Point &a, const Point &b){
    if(a.x!=b.x) return a.x<b.x;
    else return a.y<b.y;
}
...
sort(point, point+N, compare);

 

방법 2. 연산자 오버로딩 사용

struct Point{
    int x;
    int y;
    
    bool operator<(Point &other){
    	if(x!=other.x) return x<other.x;
    	else return y<other.y;
    }
}point[10];
...
sort(point, point+N);

 

 

 

 

 

---

관련 문제

 

2022.01.11 - [PS/Baekjoon] - [백준/C++] 18870번: 좌표 압축(S2)
-> 비교함수 사용

2022.01.12 - [PS/Baekjoon] - [백준/C++] 1431번: 시리얼번호(S3)
-> 비교함수 사용, 연산자 오버로딩 사용

2022.01.14 - [PS/Baekjoon] - [백준/C++] 9009번: 피보나치(S1)
-> 내림차순 정렬 방법2, 그리디

2022.01.14 - [PS/Baekjoon] - [백준/C++] 2437번: 저울(G3)
-> 오름차순 정렬, 그리디

 

 

---

참고자료 :

https://eocoding.tistory.com/44

C++로 정렬 알고리즘 sort 사용법, 내림차순, 특정 변수 기준 정렬(연산자 오버로딩, compare 함수 활

 

https://velog.io/@juwon9733/%EA%B5%AC%EC%A1%B0%EC%B2%B4struct%EC%99%80-%EC%97%B0%EC%82%B0%EC%9E%90-%EC%98%A4%EB%B2%84%EB%A1%9C%EB%94%A9%EC%9D%84-%ED%86%B5%ED%95%9C-sort-in-C

구조체(struct)와 연산자 오버로딩을 통한 sort in C++

 

 

출처 : 22Summer 신촌캠프 초급반 강사 xhdtlsid2님 강의