24.12.26 (목)

 

*초기 매개변수 실수한 코드

void QuickSort::SortAlgorithm(vector<int> NumList, int Left, int Right)
{
	if (Left < Right) //재귀호출 종료 조건
	{
		// Pivot의 확정 위치 Idx를 기준으로 왼쪽과 오른쪽으로 나누어 재귀호출
		int PivotIndex = Partition(NumList, Left, Right);
		SortAlgorithm(NumList, Left, PivotIndex - 1);
		SortAlgorithm(NumList, PivotIndex + 1, Right);
	}
}

int QuickSort::Partition(vector<int> NumList, int Left, int Right)
{
	// 임의로 마지막 값을 Pivot으로 설정
	int Pivot = NumList[Right];

	int i = Left - 1;

	for (int j = Left; j <= Right; ++j)
	{
		// 오름차순 정렬
		if (Order == 1)
		{
			if (NumList[j] < Pivot)
			{
				++i;
				swap(NumList[i], NumList[j]);
			}
		}
		// 내림차순 정렬
		else
		{
			if (NumList[j] > Pivot)
			{
				++i;
				swap(NumList[i], NumList[j]);
			}
		}
	}
	// (i + 1)은 Pivot의 최종 위치 
	swap(NumList[i + 1], NumList[Right]);

	// Pivot의 위치 인덱스 반환
	return i + 1;
}

 

 

사용자가 입력한 숫자들을 오름차순 혹은 내림차순으로 정렬하는 클래스를 만들기 위해 알고리즘을 이전에 공부했던 퀵소트로 구현하였다.

하지만 출력결과가 계속 입력결과와 같아서 알고리즘 설계가 잘못되었다고 판단했고 디버깅을 시작했다.

 

Partition 함수에서 정렬 실행 조건에 들어왔음에도 불구하고 값이 swap이 되지 않았다.

SortAlgorithm 함수와 Partition 함수에 매개 변수로 전달된 vector NumList가 클래스 내부에 저장되어있는 NumList의 값을 수정하지 않고 재귀호출 돌때마다 초기 NumList의 값만 가져오는 듯 보였다.

 

원시 배열이 함수에 매개변수로 전달될 때, 레퍼런스로 전달이 되어 '&'를 붙히지 않아도 함수에서 값을 변경하면 원본도 변경 되었어서 vector도 똑같을 거라고 생각했었다.

 

다시 공부해보니 원시 배열은 매개변수로 전달될 때, 레퍼런스와는 조금 달랐다.

배열의 이름 자체가 배열의 첫 번째 요소를 가리키는 포인터로 해석이 된다. 즉, 배열의 이름 자체가 주소를 나타내므로 배열을 함수로 전달하면 배열의 복사본이 아니라 배열의 시작 주소가 전달된다.

 

C++에서 vector와 같이 STL 컨테이너는 기본적으로 값으로 전달 된다. 이는 복사가 발생한다는 의미이며, 원본 데이터가 아닌 복사된 데이터가 함수 내에서 사용되기에 원본 데이터에 영향을 주려면 레퍼런스로 전달해야만 한다.

 

 

*수정된 코드

void QuickSort::SortAlgorithm(vector<int>& NumList, int Left, int Right)
{
	if (Left < Right) //재귀호출 종료 조건
	{
		// Pivot의 확정 위치 Idx를 기준으로 왼쪽과 오른쪽으로 나누어 재귀호출
		int PivotIndex = Partition(NumList, Left, Right);
		SortAlgorithm(NumList, Left, PivotIndex - 1);
		SortAlgorithm(NumList, PivotIndex + 1, Right);
	}
}

int QuickSort::Partition(vector<int>& NumList, int Left, int Right)
{
	// 임의로 마지막 값을 Pivot으로 설정
	int Pivot = NumList[Right];

	int i = Left - 1;

	for (int j = Left; j <= Right; ++j)
	{
		// 오름차순 정렬
		if (Order == 1)
		{
			if (NumList[j] < Pivot)
			{
				++i;
				swap(NumList[i], NumList[j]);
			}
		}
		// 내림차순 정렬
		else
		{
			if (NumList[j] > Pivot)
			{
				++i;
				swap(NumList[i], NumList[j]);
			}
		}
	}
	// (i + 1)은 Pivot의 최종 위치 
	swap(NumList[i + 1], NumList[Right]);

	// Pivot의 위치 인덱스 반환
	return i + 1;
}