퀵 정렬 구현하기

퀵 정렬은 O(n logN)의 시간 복잡도를 지닌 좋은 정렬법입니다. 

 

배열의 가장 앞 인덱스를 기준점으로 양 끝점부터 시작하여 서로 만날때까지 반대편 인덱스로 넘어가며 검색하여 위치를 바꾸어줍니다. 양 끝점에서 시작한 점들이 만나는 지점의 인덱스와 기준점으로 잡은 값을 바꿔주어 기준점 왼편과 오른편에 각각 더 작은 수와 큰 수가 오게 됩니다. 

 

이를 기준점 인덱스를 기준으로 양 옆의 배열들을 다시 재귀적으로 함수를 호출하여 정렬을 하게되면, 결과적으로 배열의 모든 값들이 오름차순으로 정렬되어짐을 알 수 있습니다.

 

아래는 위에서 설명한 퀵 정렬을 C++언어를 이용하여 만든 소스코드입니다. 템플릿 프로그래밍을 이용하여 모든 클래스에 대해 적용할 수 있게끔 일반화 프로그래밍을 하였습니다. 

template<class T>
vector<T> QuickSort(vector<T>& list, int front, int back)
{
	T middle = list[front];
	int i = front;
	int j = back + 1;

	if (front < back)
	{
		do {
			do {
				i++;
			} while (middle > list[i]);
			do {
				j--;
			} while (middle < list[j]);

			if (i < j)
			{
				int temp = list[i];
				list[i] = list[j];
				list[j] = temp;
			}
		} while (i < j);

		int temp = list[j];
		list[j] = middle;
		list[front] = temp;

		QuickSort(list, front, j - 1);
		QuickSort(list, j + 1, back);
	}
	return list;
}

 

다음 포스팅에서도 자료구조에서 중요한 알고리즘을 가져와서 포스팅해보도록 하겠습니다! 포바~!