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

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] << " "; }  }