[데이터 구조] - 내부 정렬 (교환 정렬)

#include<stdio.h>
#define ElemType int

/*    */
void swap(int& a, int& b);							//1-1.  
void BubbleSort(ElemType A[], int n);				//1-2.    
int Partition(ElemType A[], int low, int high);		//2-1.  
void QuickSort(ElemType A[], int low, int high);	//2-2.    

//1-1.  
void swap(int& a, int& b) {	//          ，    
	int temp = a;
	a = b;
	b = temp;
}

//1-2.    
void BubbleSort(ElemType A[], int n) {
	for (int i = 0; i < n - 1; i++) {	//       ，  n-1   
		bool flag = false;		//               
		for (int j = n - 1; j > i; j--)		//      
			if (A[j - 1] > A[j]) {		//    
				swap(A[j - 1], A[j]);	//  
				flag = true;	//     ，      
			}
		if (flag == false)
			return;		//          ，       ，      
	}
}

//2-1.  
int Partition(ElemType A[], int low, int high) {	//    
	ElemType pivot = A[low];	//            
	while (low < high) {		// low high         
		while (low < high && A[high] >= pivot)
			high--;
		A[low] = A[high];		//            
		while (low < high && A[low] <= pivot)
			low++;
		A[high] = A[low];		//            
	}
	A[low] = pivot;				//           
	return low;					//           
}	

//2-2.    
void QuickSort(ElemType A[], int low, int high) {
	if (low < high) {		//       
		int pivotpos = Partition(A, low, high);		//  
		QuickSort(A, low, pivotpos - 1);			//             
		QuickSort(A, pivotpos + 1, high);
	}
}

int main() {
	//1.    
	ElemType A[] = { 10,9,8,7,6,5,4,3,2,1 };
	BubbleSort(A, 10);
	for (int i = 0; i < 10; i++)
		printf("%d\t", A[i]);
	printf("
");

	//2.    
	ElemType B[] = { 10,9,8,7,6,5,4,3,2,1 };
	QuickSort(B, 0, 9);
	for (int i = 0; i < 10; i++)
		printf("%d\t", B[i]);
		
	return 0;
}