연결 리스트
-
[정렬] 더미 노드와 병합 정렬개발/C·C++ 2024. 7. 18. 14:02
연결 리스트를 정렬하는 데에는 병합 정렬이 최적이다. 시간 복잡도가 평균적으로 N(log(2)N)을 보장하며 순서가 뒤바뀌지 않는 안전 정렬이다. 구현한 연결 리스트는 더미 헤드 노드와 더미 테일 노드를 가지는데 이 존재가 정렬할 때 조금 문제가 되었다. 나이와 전화번호를 가지고 있는데, 정렬의 포인터는 헤드 노드 포인터의 next_ptr부터 시작할 수 있으므로 문제가 되지 않지만 더미 테일 노드는 제외하는 로직을 넣어야 하기 때문이다. 병합하는 과정에서, 마지막 과정임을 확인하는 건 작업하는 노드의 갯수를 세는 방법밖에 없으므로 카운팅 로직 하나당 O(N)의 시간 복잡도가 발생하는데, 총 세 번이 발생한다. 데이터의 양이 적을 땐 유의미하지 않지만 데이터가 200만개가 되니까 처리 시간이 급속도로 늦어..