[정렬 구조 2] 교환 정렬

1. 거품 정렬  O(N^2)
 
거품 정렬 과정 은 간단 합 니 다. 먼저 첫 번 째 키워드 와 두 번 째 키 워드 를 비교 하고 역순 이면 두 개의 기록 을 교환 합 니 다.그 다음 에 두 번 째 키워드 와 세 번 째 키 워드 를 비교 한 다음 에 이 를 통 해 n - 1 번 째 키워드 와 n 번 째 키 워드 를 비교 하면 가장 큰 키 워드 는 n 번 째 위치 로 교환 된다 는 것 을 알 수 있다.이 과정 을 첫 번 째 기포 정렬 이 라 고 한다.그리고 앞의 n - 1 에 대해 두 번 째 기포 순 서 를 매 겨 두 번 째 큰 키 워드 를 n - 1 위치 로 교환 합 니 다.n - 1 차 기포 정렬 이 완료 되면 질서 있 는 서열 도 생 긴 다.

#include<iostream.h>
/**************************
 *      Bubble Sort   * 
 **************************/  
class BubbleSort{
public:
	static void inc_sort(int keys[],int size);
};

void BubbleSort :: inc_sort(int keys[], int size){
	for(int i=size-1;i>=0;i--)
		for(int j=0;j<i;j++){
			if(keys[j]>keys[j+1]){
				int temp=keys[j];
				keys[j]=keys[j+1];
				keys[j+1]=temp;
			}
		}
	for(int k=0;k<size;k++)
		cout<<keys[k]<<" ";
	cout<<endl;
}
//Test BubbleSort
void main(){
	int raw[]={49,38,65,97,76,13,27,49};  
	int size=sizeof(raw)/sizeof(int);  
	BubbleSort::inc_sort(raw,size);  
}

분명히 기포 정렬 의 시간 복잡 도 는 O (N ^ 2) 이 고 그 공간 복잡 도 는 O (1) 이 며 안정 적 이다.
 
2. 빠 른 정렬 O (N * logN)
 
빠 른 정렬 은 거품 정렬 에 대한 개선 이다.그의 기본 사상 은 한 번 의 순 서 를 통 해 대기 기록 을 독립 된 두 부분 으로 나 누 는 것 이다. 그 중에서 한 부분의 키 워드 는 모두 다른 부분의 키워드 보다 작은 다음 에 이 두 부분 에 대해 계속 빨리 배열 할 수 있 고 전체 서열 이 질서 가 있다.
 
구체 적 인 방법 은 정렬 열 keys [n] 에 대해 두 개의 지침 (low = 0, high = n - 1) 을 확인 하 는 것 이다.그리고 첫 번 째 키 워드 를 keys [0] 로 pivotkey (중심 축) 로 합 니 다.우선 하 이 가 가리 키 는 위치 부터 앞으로 검색 하여 첫 번 째 키 워드 를 pivotkey 보다 작은 기록 을 찾 고 이 기록 의 키 워드 를 pivotkey 와 교환 합 니 다.그리고 low 가 가리 키 는 위 치 를 뒤로 검색 하여 첫 번 째 키 워드 를 pivotkey 보다 큰 기록 을 찾 아 교환 합 니 다.low = high 위치 까지 두 단 계 를 번갈아 반복 합 니 다.이런 과정 을 우 리 는 한 번 의 빠 른 배열 이 라 고 부른다.
 
분 단 된 서열 의 두 부분 에 대해 계속 빠 른 배열 을 하고 모든 서열 의 질서 있 는 위 치 를 알 며 전체 과정 은 빠 른 배열 이다.

#include<iostream.h>

class QuickSort{
private:
	//    (  )
	static int partition(int parts[],int low, int high);
	//  
	static void quick_sort(int parts[],int low, int high);
public:
	//    
	static void inc_sort(int keys[],int size);
};

int QuickSort :: partition(int parts[], int low, int high){	
	int pivotkey=parts[low];	//          
	while(low<high){
		while(low<high && parts[high]>=pivotkey) --high; //                
		parts[low]=parts[high];
		while(low<high && parts[low]<=pivotkey) ++low; //                
		parts[high]=parts[low];
	}
	parts[low]=pivotkey;
	return low; //       
}

void QuickSort :: quick_sort(int parts[],int low,int high){
	if(low<high){
		int pivotloc=QuickSort::partition(parts,low,high);
		QuickSort::quick_sort(parts,low,pivotloc-1);
		QuickSort::quick_sort(parts,pivotloc+1,high);
	}
}

void QuickSort :: inc_sort(int keys[],int size){
	QuickSort::quick_sort(keys,0,size-1);
	
	for(int k=0;k<size;k++)
		cout<<keys[k]<<" ";
	cout<<endl;
}

void main(){
	int raw[]={49,38,65,97,76,13,27,49};    
	int size=sizeof(raw)/sizeof(int);    
	QuickSort::inc_sort(raw,size);    
}

 

//         
#include<iostream.h>
#include<malloc.h>

void quick_sort(int *pArr, int size){
	int * beginIdxs=(int *)malloc(size * sizeof(int)); //            
	int * endIdxs=(int *)malloc(size * sizeof(int));//            
	beginIdxs[0]=0;
	endIdxs[0]=size-1;
	int curIdx=0;
	while(curIdx>-1){
		int low=beginIdxs[curIdx];
		int high=endIdxs[curIdx];
		int pivotkey=pArr[low]; //            
		while(low<high){
			while(low<high && pivotkey<=pArr[high]) --high;
			pArr[low]=pArr[high];
			while(low<high && pivotkey>=pArr[low]) ++low;
			pArr[high]=pArr[low];
		}
		pArr[low]=pivotkey;
		int pivotidx=low;
		int begin=beginIdxs[curIdx];
		int end=endIdxs[curIdx];
		curIdx--;
		if(begin<pivotidx-1){
			beginIdxs[++curIdx]=begin;
			endIdxs[curIdx]=pivotidx-1;
		}
		if(end>pivotidx+1){
			beginIdxs[++curIdx]=pivotidx+1;
			endIdxs[curIdx]=end;
		}
	}
	
	//    
	for(int k=0;k<size;k++){
		cout<<pArr[k]<<" ";
	}
}
void main(){
	int raw[]={49,38,65,97,76,13,27,49};      
	int size=sizeof(raw)/sizeof(int);      
	quick_sort(raw,size);      
}

 
빠 른 정렬 의 평균 시간 복잡 도 는 O (N * logN) 이다.그러나 빠 른 정렬 은 대기 키워드 서열 이 질서 가 있 거나 기본적으로 질서 가 있 는 상황 에서 빠 른 정렬 은 거품 정렬 로 탈바꿈 하고 시간 복잡 도 는 O (N ^ 2) 로 낮 아진 다.경험 에 의 하면 모든 O (N * logN) 급 의 이러한 정렬 알고리즘 에서 빠 른 정렬 은 현재 가장 좋 은 내부 정렬 방법 으로 여 겨 지고 있다.하지만 빨리 줄 을 서 려 면 재 귀 를 위 한 스 택 공간 이 필요 하 다.만약 에 모든 구분 이 길이 가 비슷 한 두 개의 하위 서열 로 고 르 게 나 눌 수 있다 면 창고 의 최대 깊이 는 [logN] + 1 이다.따라서 공간 복잡 도 는 O (logN) 이다.빨리 줄 서 는 것 도 불안정 해.
 
빠 른 정렬 은 최 악의 가능성 이 있 기 때문에 이 알고리즘 을 개선 하 는 최적화 도 많다.
 
에 세이 화 빠 른 배열: 빠 른 정렬 의 최 악의 상황 은 매번 주 원 에 대한 선택 을 바탕 으로 합 니 다.기본 적 인 빠 른 정렬 은 첫 번 째 요 소 를 주 원 으로 선택 합 니 다.이렇게 하면 배열 이 질서 가 있 는 상황 에서 매번 구분 할 때마다 최 악의 결 과 를 얻 을 수 있다.비교적 흔히 볼 수 있 는 최적화 방법 은 랜 덤 으로 하나의 요 소 를 주 원 으로 선택 하 는 것 이다.이 경우 최 악의 경 우 는 여전히 O (n ^ 2) 이지 만 최 악의 경 우 는 입력 데이터 에 의존 하지 않 고 무 작위 함수 의 수치 가 좋 지 않 기 때 문 입 니 다.실제로 에 세이 화 빠 른 정렬 이 이론 최 악의 상황 을 얻 을 가능성 은 1 / (2 ^ n) 에 불과 하 다.따라서 랜 덤 화 빠 른 정렬 은 절대 다수의 입력 데이터 가 O (nlogn) 에 이 르 는 기대 시간 에 대한 복잡 도 를 나 타 낼 수 있다.한 선 배 는 "에 세이 화 빠 른 정렬 은 한 사람의 평생 인품 수 요 를 만족 시 킬 수 있다" 고 치밀 하 게 정리 했다. 에 세이 화 빠 른 정렬 의 유일한 단점 은 입력 데이터 에 같은 데이터 가 많 으 면 에 세이 화 효과 가 직접적 으로 줄어든다 는 것 이다.극한 상황, 즉 n 개의 같은 수의 정렬 에 대해 랜 덤 으로 빠 른 정렬 의 시간 복잡 도 는 의심 할 여지없이 O (n ^ 2) 로 낮 아진 다.해결 방법 은 교환 되 지 않 은 상태 에서 주 원 을 원래 위치 에 유지 하 는 방법 으로 스 캔 하 는 것 이다.
 
균형 빠 른 배열 (Balanced Quicksort): 매번 가능 한 한 중간 값 을 대표 할 수 있 는 요 소 를 관건 적 인 데이터 로 선택 한 다음 에 일반 빠 른 배열 의 원칙 에 따라 비교, 교체 와 재 귀 를 한다.일반적으로 이 데 이 터 를 선택 하 는 방법 은 시작, 끝, 중간 세 개의 데 이 터 를 취하 여 그 중의 중간 값 을 비교 하여 선택 하 는 것 이다.이 세 가지 값 을 취 하 는 장점 은 실제 문제 (예 를 들 어 정보 학 경기...) 에서 유사 순서 데이터 나 역순 데이터 가 나타 날 확률 이 비교적 크다 는 것 이다. 이때 중간 데 이 터 는 반드시 중간 값 이 되 고 사실상 의 유사 중간 값 이 된다.만약 에 중간 에 큰 양쪽 이 작은 (또는 반대) 데 이 터 를 만 나 서 얻 은 값 이 모두 최고치 에 가깝다 면 적어도 두 부분 을 나 눌 수 있 기 때문에 실제 효율 도 2 배 정도 증가 하고 데 이 터 를 약간 흐 트 러 뜨리 고 퇴화 된 구 조 를 파괴 하 는 데 유리 하 다.
빠 른 배열 최적화 문제 에 대해 서 는 자바 API (JDK) 의 예 를 살 펴 보고 을 참조 할 수 있다.