블로그 이미지

[정렬][C++] Template를 이용한 퀵 정렬(Quick Sort)

2013. 2. 14. 16:15

Quick Sort(퀵 정렬)

C++, Array Version (배열 버전)


Quick Sort Function(퀵 정렬 함수)

 // 첫번째 인자 : 배열
// 두번째 인자 : 무조건 1 (두번째 인자 Index)
// 세번째 인자 : 배열의 길이 + 1 (마지막 인자 Index)
// 네번째 인자 : Ascending 일 때 오름차순, Descending 일 때 내림차순
template<typename T, size_t n>
void sort_quick(T (&_input)[n], int Left, int Right, bool _option)
{
	int Base_Index = Left-1;	//가장 왼쪽의 값을 기준 값으로 잡음
	int Left_Index = Left;
	int Right_Index = Right;

	if(Right_Index <= Left_Index)
		return;

	while(Left_Index < Right_Index)
	{
		if(_option)
		{
			//오름차순
			//우측 포인터 부터 접근
			while((Left_Index < Right_Index) && (_input[Base_Index] < _input[Right_Index]))
			{
				Right_Index--;	
			}

			while((Left_Index < Right_Index) && (_input[Base_Index] > _input[Left_Index]))
			{
				Left_Index++;
			}
		}else{
			//내림차순
			//우측 포인터 부터 접근
			while((Left_Index < Right_Index) && (_input[Base_Index] > _input[Right_Index]))
			{
				Right_Index--;
			}
			while((Left_Index < Right_Index) && (_input[Base_Index] < _input[Left_Index]))
			{
				Left_Index++;
			}
		}
		Swap(_input[Left_Index], _input[Right_Index]);
	}

	//오름차순
	if(_option)
	{
		if(_input[Base_Index] > _input[Right_Index])
			Swap(_input[Base_Index], _input[Right_Index]);
	}else{
	//내림차순
		if(_input[Base_Index] < _input[Right_Index])
			Swap(_input[Base_Index], _input[Right_Index]);
	}
	
	//좌측 정렬 재귀함수 호출
	sort_quick(_input,Left ,Right_Index-1, _option);
	//우측 정렬 재귀함수 호출
	sort_quick(_input,Right_Index+1,Right, _option);
}



예제)

#include <iostream>

#define ARRAY_LENGTH(X) sizeof(X)/sizeof(X[0])
#define Ascending true
#define Descending false

template <typename T>
void Swap(T& _input1, T& _input2)
{
	T temp = _input1;
	_input1 = _input2;
	_input2 = temp;
}

// 첫번째 인자 : 배열
// 두번째 인자 : 무조건 1 (두번째 인자 Index)
// 세번째 인자 : 배열의 길이 + 1 (마지막 인자 Index)
// 네번째 인자 : Ascending 일 때 오름차순, Descending 일 때 내림차순
template<typename T, size_t n>
void sort_quick(T (&_input)[n], int Left, int Right, bool _option)
{
	int Base_Index = Left-1;	//가장 왼쪽의 값을 기준 값으로 잡음
	int Left_Index = Left;
	int Right_Index = Right;

	if(Right_Index <= Left_Index)
		return;

	while(Left_Index < Right_Index)
	{
		if(_option)
		{
			//오름차순
			//우측 포인터 부터 접근
			while((Left_Index < Right_Index) && (_input[Base_Index] < _input[Right_Index]))
			{
				Right_Index--;	
			}

			while((Left_Index < Right_Index) && (_input[Base_Index] > _input[Left_Index]))
			{
				Left_Index++;
			}
		}else{
			//내림차순
			//우측 포인터 부터 접근
			while((Left_Index < Right_Index) && (_input[Base_Index] > _input[Right_Index]))
			{
				Right_Index--;
			}
			while((Left_Index < Right_Index) && (_input[Base_Index] < _input[Left_Index]))
			{
				Left_Index++;
			}
		}
		Swap(_input[Left_Index], _input[Right_Index]);
	}

	//오름차순
	if(_option)
	{
		if(_input[Base_Index] > _input[Right_Index])
			Swap(_input[Base_Index], _input[Right_Index]);
	}else{
	//내림차순
		if(_input[Base_Index] < _input[Right_Index])
			Swap(_input[Base_Index], _input[Right_Index]);
	}
	
	//좌측 정렬 재귀함수 호출
	sort_quick(_input,Left ,Right_Index-1, _option);
	//우측 정렬 재귀함수 호출
	sort_quick(_input,Right_Index+1,Right, _option);
}

int main(void)
{
	char a[] = {'a','f','d','e','b','k','z','i','g','h','c','b'};

	sort_quick(a, 1, ARRAY_LENGTH(a)-1, Ascending);

	for(int i=0; i<ARRAY_LENGTH(a); i++)
	{
		std::cout << a[i] << " ";
	} 
} 



  1. wmfdod123 2016.05.13 20:58  address  modify / delete  reply

    이게 quicksort가 맞나요 bubble sort아닌가요??