반응형
Problem Solving을 하다보면 주어진 원소를 정렬 시킬 필요가 있습니다.
물론 STL을 이용해서 구현할 수 있지만 해당 노트에서는 구조체 형태로 정렬하는 내용을 다룹니다.
상황 (조건)
특정 사람이 {나이age, 경험exp}가 있을 때,
나이가 큰 순(내림차순) / (나이가 동일한 경우) 경험이 큰 순(내림차순)
즉, 여러 기준을 적용해서 정렬하겠습니다.
Input
3
20 20
20 30
30 10
Output
age = 30, exp = 10
age = 20, exp = 30
age = 20, exp = 20
구현 코드
#include <stdio.h>
#define MAX_NUM 100
int N;
struct Node {
int age, exp;
void print() {
printf("age = %d, exp = %d\n", age, exp);
}
}input[MAX_NUM];
bool comp(Node A, Node B) {
if (A.age < B.age) return true;
else if (A.age == B.age) return A.exp < B.exp;
return 0;
}
inline void swap(Node& A, Node& B) { Node temp = A; A = B; B = temp; }
void quickSort(int first, int last) {
register int i, j, pivot;
if (first < last) {
pivot = first;
i = first, j = last;
while (i < j) {
while (comp(input[i], input[pivot]) && i < last) {
i++;
}
while (comp(input[j], input[pivot])) {
j--;
}
if (i < j) {
swap(input[i], input[j]);
}
}
swap(input[pivot], input[j]);
quickSort(first, j - 1);
quickSort(j + 1, last);
}
}
int main(void) {
freopen("input.txt", "r", stdin);
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d %d", &input[i].age, &input[i].exp);
}
quickSort(0, N - 1);
// 결과 출력
for (int i = 0; i < N; ++i) {
input[i].print();
}
printf("\n");
}
분석
Quick Sort 혹은 다른 Sort 코드를 이용해도 상관 없습니다.
구조체를 정의하고 비교하는 부분을 comp()로 처리해서 모듈화 하였습니다.
comp() 함수
- 오름/내림 차순 기준에 따라 부등호 방향을 바꿔가며 디버깅하면 되기에 부등호 방향은 크게 고민할 필요 없습니다.
bool comp(Node A, Node B) {
if (A.age < B.age) return true;
else if (A.age == B.age) return A.exp < B.exp;
return 0;
}
※ PS에서는 2~3가지 기준이 있기 때문에 종종 사용될 때가 있습니다.
Quick Sort는 pivot의 위치에 따라 재귀 수행시 overflow가 날 수 있기에
어떤 Input Case에서도 안정적인 Merge Sort를 구현하는 것을 권장합니다.
[실행 결과]
반응형
'알고리즘' 카테고리의 다른 글
문자열 Hash (djb2) (0) | 2021.06.12 |
---|---|
[예제] 힙 정렬 구현 (0) | 2021.06.04 |
퀵(Quick) 정렬 (0) | 2021.06.04 |
삽입 정렬(Insertion Sort) (2) | 2021.06.02 |
[ps] 여러 정수 기준에 따른 우선순위 비교 및 정렬 (0) | 2021.05.30 |
댓글