[정렬] 더미 노드와 병합 정렬

연결 리스트를 정렬하는 데에는 병합 정렬이 최적이다. 시간 복잡도가 평균적으로 N(log(2)N)을 보장하며 순서가 뒤바뀌지 않는 안전 정렬이다.

 

구현한 연결 리스트는 더미 헤드 노드와 더미 테일 노드를 가지는데 이 존재가 정렬할 때 조금 문제가 되었다. 나이와 전화번호를 가지고 있는데, 정렬의 포인터는 헤드 노드 포인터의 next_ptr부터 시작할 수 있으므로 문제가 되지 않지만 더미 테일 노드는 제외하는 로직을 넣어야 하기 때문이다.

 

병합하는 과정에서, 마지막 과정임을 확인하는 건 작업하는 노드의 갯수를 세는 방법밖에 없으므로 카운팅 로직 하나당 O(N)의 시간 복잡도가 발생하는데, 총 세 번이 발생한다. 데이터의 양이 적을 땐 유의미하지 않지만 데이터가 200만개가 되니까 처리 시간이 급속도로 늦어졌다.

USERDATA* Merge(USERDATA* first, USERDATA* second) {
	USERDATA dummy = {};
	USERDATA* result = &dummy;
	int count = 0;

	//getCount(count, first);
	//getCount(count, second);

	while (first && second) {
		if (first->age <= second->age) {
			result->next_ptr = first;
			first = first->next_ptr;
		}
		else {
			result->next_ptr = second;
			second = second->next_ptr;
		}
		result = result->next_ptr;
	}

	// 남은 리스트 이어붙이기
	result->next_ptr = first ? first : second;
	//if (count == g_node_count) {
	//	USERDATA* cycle = result->next_ptr;
	//	while (cycle->next_ptr) {
	//		cycle = cycle->next_ptr;
	//	}
	//	cycle->next_ptr = &g_tail_node;
	//}

	return dummy.next_ptr;
}

 

나이 기준으로 정렬을 진행했다. 더미 테일 노드를 고려하지 않았을 때는 1.3초면 끝났지만 더미 테일 노드를 고려하는 로직을 추가하고 나서는 2.1초가 걸렸다. 정렬 과정에서 불필요한 로직은 정말 좋지 않다. 그래서 이 로직은 폐기하기로 하고 더미 테일 노드가 언제나 뒤로 가있을 수 있도록 초기화하는 것이 나아 보인다. 나이는 999를 넣어주고 이름과 전화번호 둘다 문자열인데 이름은 "{Tail}", 전화번호는 "{}"로 초기화한다. 왜냐하면 {}은 아스키코드상으로 대소문자 알파벳 이후에 등장하기 때문이다.