C++ vector 퀵정렬 알고리즘 관련 질문 있습니다.

Question

알고리즘을 공부하면서 최소신장트리 관련하여 크러스컬 알고리즘을 C++로 구현하고자합니다.기본 구조는 다음과 같습니다.typedef pair iPair; struct Graph{ int V, E, left; vector< pair > edges; Graph(int V, int E) { this->V = V; this->E = E; this->left = 0; } int Partition(vector < pair > &vertex, int left, int right); void Qsort(vector< pair > vertex, int left, int right);} int Graph::Partition(vector < pair > &vertex, int left, int right) { int pivot_idx = (left + right) / 2; int pivot = vertex.at(pivot_idx).first; while (left < right) { while ((vertex.at(left).first < pivot) && (left < right)) { left++; } while ((vertex.at(right).first > pivot) && (left < right)) { right--; } if (left < right) { iter_swap(vertex.begin()+left, vertex.begin()+right);// vertex.at(left).swap(vertex.at(right)); } } return left;}; void Graph::Qsort(vector< pair > vertex, int left, int right) { if (left < right) { int newIndex = Partition(vertex, left, right); Qsort(vertex, left, newIndex-1); Qsort(vertex, newIndex+1, right); }} 정작 중요한 크러스컬 알고리즘 부분은 가중치가 정렬된 입력값을 넣었을 때 정상적으로 작동하는 것으로 보아 문제가 없는데, 가중치를 퀵소트를 하는 과정에서 partition 함수에선 스왑까지 잘 되는데 다시 Qsort함수 중간으로 리턴될때 벡터의 정렬이 다시 처음과 같이 돌아갑니다. 퀵소트는 이해를 했다고 생각했는데 제가 벡터를 잘못 쓴건지 안되니 당황스럽네요. 개선방안에 대해서 알려주시면 감사하겠습니다.

쿠케캬캬 · Accepted Answer

Qsort vertex파라미터앞에 & 빠뜨린거아닌가요

훈산팸 · Answer

&#64;쿠케캬캬 제가 그걸 놓쳤네요,, 같은 코드만 계속 보면서 머리를 싸매고 있더니 그 간단한게 안보였나봅니다. 도움 주셔서 감사합니다.

C++ vector 퀵정렬 알고리즘 관련 질문 있습니다.

2개의 답변

#quicksort 목록