高速ソート(3パス分割)による大量の重複要素の解決

#include
#include
#include
#define M 20

using namespace std;
static int count_insert = 0;
static int count_partion = 0;

typedef struct index
{
 	  int left;
 	  int right;
}index;

void swap(int& small, int& big)
{
	int temp = small;
	small = big;
	big = temp;
}
/*
|       ：
|
|cur = 1 ->  right       ，pre       。
|
|        arr[cur]  tmp，    arr[pre] arr[cur]，
|       arr[cur] < arr[pre], arr[pre + 1] = arr[pre]  
|            ，   arr[cur]             
|    arr[cur]   arr[pre]   ，          tmp = arr[cur]   
|   tmp   arr[pre]   
*/
void insert_sort( int arr[], int left, int right)
{
	int tmp, cur , pre;
	for (cur = 1; cur < right; cur++)
	{
		pre = cur - 1;
		tmp = arr[cur];

		while ( tmp < arr[pre] && pre >= 0)
		{
			arr[pre + 1] = arr[pre];
			pre--;
		}
		arr[pre] = tmp;
	}
	count_insert += 1;
}
/*
|       ：
|          ，        ，    。
|
|      ，      (i, j)   ，  i,j    ；
|                 base；
|  arr[i]      ，  arr[i]          ；
|  arr[j]      ，  arr[j]        。
|
|                ，       。
*/
index partion(int arr[], int left, int right)
{
	int i , j;
	int pleft, pright;
	int tag, base;
	index p;
	
	if ( left > right ) exit(-1) ;
	
	i = left - 1, j = right;
 	pleft = left - 1, pright = right;
 	base = arr[right];
	//@_1 
	for (;;)
	{
	    while ( i < j && arr[ ++i ] < base );
	    	  
	    while ( i < j && arr[ --j ] > base ) if ( j <= left ) break;
  	  	  
  	  	if ( j == i ) break;
  	  	  
  	  	swap( arr[j] , arr[i]); // @_2

		if ( arr[i] == base )
  	  	 {
   	 		pleft += 1;
			swap(arr[i], arr[pleft]);   	 	  
         }
              
         if ( arr[j] == base )
         {
 	  		pright -= 1;
 	  	    swap( arr[j], arr[pright]);//@_3
		 }
	}//for
	 
	swap( arr[right], arr[i]); //@_4
	
	j = i - 1; i = i + 1;
	
	for (tag = left; tag <= pleft; tag++, j--) swap(arr[tag], arr[j]);
	
	for (tag = right - 1 ; tag >= pright; tag--, i++) swap(arr[tag], arr[i]);//@_5
	
	p.left = j, p.right = i ;

	count_partion += 1;
	
	return p;  
}

/*
|              20，      ，
|      。
|   N      ，           arr[0 -> 10]      
|              。
*/
void quick_sort(int arr[], int left, int right)
{
	if ( left < right )
	{
		if ( (right - left) <= M )
			insert_sort(arr, left, right);
		else
		{
			index sec = partion(arr, left, right);
			quick_sort(arr, left, sec.left);
			quick_sort(arr, sec.right, right);
		}
	}
}

int main()
{
	
	const int size = 500;
	static int s[size];
	srand(unsigned int ( time(NULL)));
	for (int i = 0; i < size; i++)
		s[i] = rand()%100;

	quick_sort(s, 0, size-1);

	for (i = 0; i < size; i++)
		cout << s[i] << " ";
	cout << endl;
	cout << "call insert_sort  " << count_insert << " times" <