SORT
특정 집합의 요소들을 특정 기준으로 나열하는 것
https://ko.wikipedia.org/wiki/정렬_알고리즘
STL에서 구현된 정렬 알고리즘 = 굉장히 “안정적”
→ STL에서 만들어진 정렬의 시간복잡도는 “항상” O(NlogN) 보장
C++에서 사용하는 정렬 = Intro sort (여러 정렬을 섞어 만든 알고리즘)
Intro sort = Heap Sort + Insertion Sort + Quick Sort
STL sort() 사용 방법
#include <iostream>
#include <algorithm> // <-- 정렬 기능이 포함된 라이브러리 (min, max) 등
using namespace std;
bool cmp(int left, int right) {
// return left < right; 이것을 하기 위함
// -> 정렬이 필요하면 false, 정렬이 되어있으면 true
if (left > right) // (우리가 원하는 상태) --> true
return true;
if (left < right)
return false;
// 모든 조건들이 같을때
return false;
}
int main(){
int arr[] = {1,3,5,4,2};
// 정렬 방법
// sort(RandomAccessIterator first, RandomAccessIterator last, compare comp);
// default : sort(시작 메모리, 끝 메모리, <(less))
// iterator : 포인터 / 메모리에 접근할 수 있는 요소
// 즉, sort(배열의 시작 주소, 배열의 끝 주소, 비교 기준)
// #1. 오름차순 정렬 (default)
sort(arr, arr + 5);
for (int i = 0; i < 5; i++) {
cout << arr[i] << ' '; // 5 4 3 2 1
}
cout << endl;
// #2. 내림차순 정렬
sort(arr, arr + 5, cmp);
for (int i = 0; i < 5; i++) {
cout << arr[i] << ' '; // 5 4 3 2 1
}
}
여러 가지 조건의 정렬
#include <iostream>
#include <algorithm>
using namespace std;
// #3. struct 정렬
struct Student {
string name; // 이름
int age; // 나이
int grade; // 점수
};
bool ssafycmp(Student left, Student right) {
// 기준 1. 시험 점수가 높은 사람 (내림차순)
if (left.grade > right.grade)
return true;
if (left.grade < right.grade)
return false;
// 기준 2. 나이가 많은 사람 (내림차순)
if (left.age > right.age)
return true;
if (left.age < right.age)
return false;
// 기준 3. 이름이 사전 순으로 빠른 사람 (오름차순)
if (left.name > right.name)
return false;
if (left.name < right.name)
return true;
// 마지막 (모두 같을 때)
return false;
}
int main() {
Student ssafy[5];
// 시험 점수 높은 사람, 나이가 많은 사람, 이름이 빠른 사람 순으로 정렬 만들 예정
ssafy[0] = { "송씨", 3, 100};
ssafy[1] = { "박씨", 4, 100 };
ssafy[2] = { "김씨", 2, 100 };
ssafy[3] = { "이씨", 4, 100 };
ssafy[4] = { "남씨", 7, 25 };
sort(ssafy, ssafy + 5, ssafycmp);
for (int i = 0; i < 5; i++) {
cout << ssafy[i].name << " " << ssafy[i].age << " " << ssafy[i].grade << '\n';
}
}Priority Queue
queue와는 다르게, priority queue는 더 큰 숫자에 우선 순위를 부여 --> Heap 구조 이용
Heap 구조
완전 이진 트리의 일종 // Max heap과 Min heap이 있음
그래서 숫자들을 어떻게 heap 구조로 바꾸느냐? -> heapify
Heapify
이진 트리를 Heap 구조로 변환하는 과정
Heapify에는 enqueue와 dequeue가 있음
1. Enqueue
2. Dequeue
한 번 동작 시의 시간복잡도
- 삽입(enqueue) : O(logN) - 이진 트리기 때문에, 최대 logN 번 움직임
- 추출(dequeue) : O(logN) - 이진 트리기 때문에, 최대 logN 번 움직임
구현
#include <iostream>
#include <queue> // priority queue는 여기에 속해 있음
using namespace std;
int main(){
int arr[] = {1, 4, 5, 3, 2};
// #1 dafault : Max heap
priority_queue<int>pq;
// 삽입 : push()
// 삭제 : pop()
// 맨 위 (우선순위가 가장 높은 값) 가져오기 : q.top()
// 비어있는 지 : empty()
for (int i=0; i<5; i++){
pq.push(arr[i]); // heapify
}
// 출력
while (!pq.empty()){
cout << pq.top() << " "; // 5 4 3 2 1
pq.pop(); // heapify
}
}
// #2 Min Heap
// 구조
priority_queue<typename, container, _Pr>
// typename : 자료형, container : vector로 사용되고 있음, _Pr : less --> <
// default : priority_queue<int, vector<int>, less<int>>
// sort와 다르게 3번째 parameter는 Compare cmp가 아님 --> 함수 구조체를 사용
// 즉, 함수로 넣어주면 안 되고, 구조체 함수를 만들어서 넣어야 한다.
#include <iostream>
#include <queue>
using namespace std;
struct cmp {
bool operator()(int left, int right) {
if (left > right) // 우리가 원하는 상태 : 내림차순 (Max-heap)
return false; // sort() 와는 다르게, 원하는 상태일 때 false
if (left < right)
return true;
return false;
}
};
int main() {
int arr[] = { 1, 4, 5, 3, 2 };
priority_queue<int, vector<int>, cmp>pq;
for (int i = 0; i < 5; i++) {
pq.push(arr[i]); // heapify
}
while (!pq.empty()) {
cout << pq.top() << " "; // 5 4 3 2 1
pq.pop(); // heapify
}
}cmp 함수를 잘 보면
- sort에서의 cmp
- left > right 일 때 true -> 내림차순
- 올바른 상황 (내가 원하는 상황일 때) → true를 return하게끔 설계
- priority queue에서의 cmp
- left > right 쓰면 false -> Max Heap (내림차순)
- 올바른 상황 (내가 원하는 상황일 때) → false를 return하게끔 설계해야 함
// 3. 사용자 정의 Heap
// a. 정석 방법 : 구조체 cmp를 만들어서 넣는 방법
#include <iostream>
#include <queue>
using namespace std;
struct Student {
string name; // 이름
int age; // 나이
int grade; // 점수
};
struct ssafycmp {
bool operator()(Student A, Student B) {
if (A.grade > B.grade)
return true;
if (A.grade < B.grade) // 1. 우측이 클 때 false이므로, 오름차순(min-heap) 정렬
return false;
if (A.age > B.age)
return true;
if (A.age < B.age) // 2. 우측이 클 때 false이므로, 오름차순(min-heap) 정렬
return false;
if (A.name > B.name) // 3. 좌측이 클 때 false이므로, 내림차순(max-heap) 정렬
return false;
if (A.name < B.name)
return true;
return false; // 마지막은 false로!
}
};
int main() {
Student ssafy[5];
ssafy[0] = { "송씨", 3, 100 };
ssafy[1] = { "박씨", 4, 100 };
ssafy[2] = { "김씨", 2, 100 };
ssafy[3] = { "이씨", 4, 100 };
ssafy[4] = { "남씨", 7, 25 };
priority_queue<Student, vector<Student>, ssafycmp>pq;
pq.push({ "송씨", 3, 100 });
pq.push({ "박씨", 4, 100 });
pq.push({ "김씨", 2, 100 });
pq.push({ "이씨", 4, 100 });
pq.push({ "남씨", 7, 25 });
while (!pq.empty()) {
cout << pq.top().grade << " " << pq.top().age << " " << pq.top().name << '\n' ;
pq.pop();
}
// 25 7 남씨
// 100 2 김씨
// 100 3 송씨
// 100 4 이씨
// 100 4 박씨
}위의 방법이 복잡하니, 구조체 생성 시에 위와 같이 함수를 선언하는 방법이 있음
// 3. 사용자 정의 Heap
// b. 구조체 자체에 "< operatior"의 기준을 잡아주는 방법
#include <iostream>
#include <queue>
using namespace std;
struct Student {
string name; // 이름
int age; // 나이
int grade; // 점수
};
bool operator < (Student A, Student B) {
if (A.grade > B.grade)
return true;
if (A.grade < B.grade)
return false;
if (A.age > B.age)
return true;
if (A.age < B.age)
return false;
if (A.name > B.name)
return false;
if (A.name < B.name)
return true;
return false; // 마지막은 false로!
}
int main() {
Student ssafy[5];
ssafy[0] = { "송씨", 3, 100 };
ssafy[1] = { "박씨", 4, 100 };
ssafy[2] = { "김씨", 2, 100 };
ssafy[3] = { "이씨", 4, 100 };
ssafy[4] = { "남씨", 7, 25 };
priority_queue<Student, vector<Student>>pq;
pq.push({ "송씨", 3, 100 });
pq.push({ "박씨", 4, 100 });
pq.push({ "김씨", 2, 100 });
pq.push({ "이씨", 4, 100 });
pq.push({ "남씨", 7, 25 });
while (!pq.empty()) {
cout << pq.top().name << "2" << pq.top().age << " " << pq.top().grade << endl;
pq.pop();
}
}
// 3. 사용자 정의 Heap
// c. 연산자 자체를 overriding 하는 것 : 비권장
// < 자체를 overriding하는 것이기 때문 - 나중에 다른 기준으로 활용하기 어려움
~~~~#include <iostream>
#include <queue>
using namespace std;
struct Student {
string name; // 이름
int age; // 나이
int grade; // 점수
// const : 상수
// --> 내 자신의 (y, x)가 정렬을 하거나 pq에 들어갔을 때, 중간에 바뀌면 안 됨
bool operator < (Student next) const { // < 표기 :
if (grade > next.grade) // const 표기 :
return true;
if (grade < next.grade)
return false;
if (age > next.age)
return true;
if (age < next.age)
return false;
if (name > next.name)
return false;
if (name < next.name)
return true;
return false; // 마지막은 false로!
}
};
int main() {
Student ssafy[5];
ssafy[0] = { "송씨", 3, 100 };
ssafy[1] = { "박씨", 4, 100 };
ssafy[2] = { "김씨", 2, 100 };
ssafy[3] = { "이씨", 4, 100 };
ssafy[4] = { "남씨", 7, 25 };
priority_queue<Student, vector<Student>>pq;
pq.push({ "송씨", 3, 100 });
pq.push({ "박씨", 4, 100 });
pq.push({ "김씨", 2, 100 });
pq.push({ "이씨", 4, 100 });
pq.push({ "남씨", 7, 25 });
while (!pq.empty()) {
cout << pq.top().name << " " << pq.top().age << " " << pq.top().grade << endl;
pq.pop();
}
}
Sort()와 Priority Queue를 언제 쓰는 것이 유리할까
- Sort() : 딱 한 번의 정렬로 해결이 가능할 때
- Priority Queue : 계속해서 새로운 값이 삽입/추출 될 때 (변화가 있을 시)
ex) Q개의 query가 있다고 가정
- 0일 때, 현재 가장 큰 값을 출력
- 1일 때, 삽입
- 2일 때, 현재 가장 큰 값을 삭제
- Sort : 삽입할 때마다 정렬해야 함
- (Query 수) * (정렬 시간복잡도) → Q*O(NlogN)
- Priority Queue : 삽입/추출마다 heapify 진행
- (Query 수) * (logN) → Q*O(logN)
'IT_Study > C++' 카테고리의 다른 글
| [그래프 #5] 유니온 파인드(Union Find) 알고리즘을 활용한 문제 풀이 방법 (2) | 2023.02.16 |
|---|---|
| [그래프 #4] 다익스트라(Dijkstra) 알고리즘을 활용한 문제 풀이 방법 (0) | 2023.02.15 |
| [C++] 기초 (3) : 문자열(String), 벡터(Vector) (0) | 2023.02.06 |
| [C++] 기초 (2) : 재귀 함수 & 전역변수와 지역변수 & Problem Solving (0) | 2023.01.27 |
| [C++] 기초 (1) : Visual Studio, 자료형, 입력, 조건문, 반복문, 배열, 함수 (0) | 2023.01.13 |