빠 른 배열 에서 partition 함수 최적화

//     index ，           Arr[index] ，           Arr[index] 
int partition( int Arr[], int start, int end, int pivotIndex )  //pivotIndex     
{
	int pivot = Arr[pivotIndex];
	swap( Arr[pivotIndex], Arr[end]);     //exchange the pivot and the last element

	int indexStore = start;
	for( int i = start; i < end; i++ )    
	{
		if( Arr[i] < pivot )
		{
			swap( Arr[indexStore], Arr[i] );
			indexStore ++;
		}
	}
	swap( Arr[indexStore], Arr[end] );
	return indexStore;
}

/*****************************
@data:2015/7/1
@author:lss
@function:fast sort by using partition funtion
******************************/


#include <stdio.h>
#include <iostream>
using namespace std;

void swap( int &a, int &b ){   //    
	int tmp  = a;
	a = b;
	b = tmp;

}
//     index ，           Arr[index] ，           Arr[index] 
int partition( int Arr[], int start, int end, int pivotIndex )  //pivotIndex     
{
	int pivot = Arr[pivotIndex];
	swap( Arr[pivotIndex], Arr[end]);     //exchange the pivot and the last element

	int indexStore = start;
	for( int i = start; i < end; i++ )    
	{
		if( Arr[i] < pivot )
		{
			swap( Arr[indexStore], Arr[i] );
			indexStore ++;
		}
	}
	swap( Arr[indexStore], Arr[end] );
	return indexStore;
}

void fastSort( int Arr[], int start, int end ){   //     
	if( start == end )
		return;

	int index = partition( Arr, start, end, start );   //  index ，            。
	if( index > start ) 
		fastSort(Arr, start, index-1 );  //left sort
	if( index < end )
		fastSort(Arr, index+1, end);   //right sort

}

int main(){
	int Arr[] = {3,2,4,7,4,56,1};
	fastSort( Arr, 0, 6);
	for(int i = 0 ; i <= 6; i++)
		cout<<Arr[i]<<endl;  
	return 0;
}

/******************************
*@data:2015/6/16
*@author:lss
*@function:
test sort_fast
**********************************/



#include <iostream>
#include <algorithm>

#include <stdio.h>
using namespace std;


void swap( int &x, int &y){  //swap funtion
	int tmp = x;
	x = y;
	y = tmp;
}

void fastSort( int Arr[], int start, int end ){  //fast funtion

	int pst = start;
	int ped = end-1;
	if( start == end && Arr == NULL)
		return;

	while( pst != ped ){
		if( Arr[pst] >Arr[end] ){
				swap( Arr[pst], Arr[ped]);
				ped --;
			}
		else
			pst ++;
	}
	swap( Arr[ped], Arr[end] );   //swap

	fastSort( Arr,  pst, ped-1 );   //left sort
	fastSort( Arr,  ped+1, end );   //left sort


}


int main(){   //main funtion
	int 
Arr[]={2,7,4,3,6};
	fastSort( Arr, 0, 4);
	for(int i = 0; i<4; i++)
		cout<<i<<endl;

	return 0;
}