빠른 정렬 최적화

최적화점:선택 중축 요소 최적화
상기 코드 target이 선택한 위치는 그룹 요소의 수위를 인정하지만, 이 수치의 크기가 전체 그룹의 중간 위치에 있지 않으면 빠른 배열의 성능을 크게 떨어뜨릴 수 있습니다.target=array[low]라는 문장은 잠재적인 성능 병목이 되었다.따라서 빠른 정렬 속도는 이 target 관건 요소가 그룹에 있는 위치에 달려 있습니다.【개선 방법】 삼수취중법: 세 개의 원소를 제거하고 먼저 정렬을 하고 중간수를 중축원소로 하고 아래의 코드는 수조의 왼쪽, 중간, 오른쪽 세 개의 수를 선택한다.

#include 
using namespace std;
void Swap(int &x,int &y)
{
	int temp = x;
	x = y;
	y = temp;

}

int partition(int * arr,int low,int high)
{
	int mid = (low+high)/2;  //      
	if(arr[high] < arr[low])
	{
		Swap(arr[low],arr[high]);
	}
	if(arr[high]<arr[mid])
	{
		Swap(arr[mid],arr[high]);
		
	}
	// 2 if           
	//  if                  
	if(arr[mid]>arr[low])
	{
		Swap(arr[low],arr[mid]);
	}
	
	//            
	int pv = arr[low];
	while(low<high)
	{
		while(low<high&&arr[high] >=pv)
		{
			high--;
		}
		Swap(arr[low],arr[high]);
		while(low<high&&arr[low] <=pv)
		{
			low++;
		}
		Swap(arr[low],arr[high]);

	}

	return low;






}



void Quick_Sort(int * arr,int low,int high)
{
	if(low<high)
	{
		int pv = partition(arr,low,high);
		Quick_Sort(arr,low,pv-1);
		Quick_Sort(arr,pv+1,high);
	}



}


int  main()
{

	int arr[10];
	
	Quick_Sort(arr,0,9);
	
	for(int i = 0;i<10;i++)
	{
		arr[i] = rand();
	}
	for(int i = 0;i<10;i++)
	{
		cout<<arr[i]<<endl;
	}


	system("pause");
	return 0;
}