[내부 정렬] 2: 반절 삽입 정렬 (binary insertion sorting) 실현 (소스 코드)

이전 글 에 정렬 알고리즘 을 직접 삽입 하 는 것 은 간단 하고 실현 하기 쉽다. 정렬 을 기다 리 는 길이 n 이 매우 길 면 좋 은 정렬 방법 이다. 특히 원시 서열 이 질서 에 가 까 울 때 효율 이 더욱 좋다.정렬 할 길이 n 이 크 면 직접 정렬 하 는 것 이 좋 지 않 습 니 다.이때 우 리 는 이 를 개선 하 는 것 을 고려 할 수 있다. 우 리 는 비교 와 이동 횟수 를 줄 이 는 데 착안 할 수 있 기 때문에 반절 로 순 서 를 삽입 할 수 있다. 그 사상 은 반절 로 찾 는 것 과 유사 하 다.정렬 알고리즘 과정 에서 요 소 를 앞 에 정렬 된 시퀀스 에 순서대로 삽입 하 는 것 입 니 다.앞부분 은 이미 정렬 된 수열 이기 때문에 우 리 는 순서대로 삽입 점 을 찾 지 않 고 반절 로 찾 는 방법 으로 삽입 점 을 찾 는 속 도 를 가속 화 할 수 있다.
반절 삽입 정렬 알고리즘 사상
n 개의 정렬 을 기다 리 는 요 소 를 하나의 질서 표 와 하나의 무질서 표 로 보고 시작 할 때 질서 표 에는 하나의 요소 만 포함 되 어 있 으 며 무질서 표 에는 n - 1 개의 요소 가 포함 되 어 있 으 며 정렬 과정 에서 매번 무질서 표 에서
첫 번 째 요 소 를 꺼 내 질서 표 의 적당 한 위치 에 삽입 하여 새로운 질서 표 로 만 들 고 n - 1 회 반복 하면 정렬 과정 을 완성 할 수 있 습 니 다.
a [i] 를 a [0], a [1],..., a [i - 1] 질서 표 에 삽입 하 는 구체 적 인 실시 과정 은 다음 과 같다.
새로운 요 소 를 정렬 된 배열 에 삽입 하 는 과정 에서 삽입 점 을 찾 을 때 삽입 할 구역 의 첫 번 째 요 소 를 a [low] 로 설정 하고 마지막 요 소 를 a [high] 로 설정 하면 한 번 비교 할 때 삽입 할 요 소 를 a [m] 와 비교 합 니 다. 그 중에서 m = (low + high) / 2 를 비교 합 니 다. 시험 에 참가 할 요소 보다 크 면 a [low] 에서 a [m - 1] 를 새로운 삽입 구역 (즉, high = m - 1) 으로 선택 합 니 다. 그렇지 않 으 면 a [m + 1] 에서 a 를 선택 합 니 다.[high] 는 새로운 삽입 영역 (즉 low = m + 1) 입 니 다. low < = high 가 성립 되 지 않 을 때 까지 이 위치 에 있 는 모든 요 소 를 한 자리 뒤로 옮 기 고 새로운 요 소 를 a [high + 1] 에 삽입 합 니 다.
안정성 및 복잡 도
반절 삽입 정렬 알고리즘 은 안정 적 인 정렬 알고리즘 으로 직접 삽입 알고리즘 보다 키워드 간 비교 횟수 를 현저히 줄 였 기 때문에 직접 삽입 정렬 알고리즘 보다 속도 가 빠 르 지만 이동 횟수 를 기록 하 는 것 은 변 하지 않 았 기 때문에 반절 삽입 정렬 알고리즘 의 시간 복잡 도 는 여전히 O (n ^ 2) 로 정렬 알고리즘 을 직접 삽입 하 는 것 과 같 습 니 다. 추가 공간 O (1).
알고리즘 구현 코드:

void binary_insertion_sort(int *a,int n)
{
	int i;
	//  1             
	for(i=1;i<n;i++)
	{
		int low=0;
		int high=i-1;
		int temp=a[i]; //temp        
		//                     
		while (low<=high)
		{
			int mid=(low+high)/2;
			if (temp<a[mid])
				high=mid-1;
			else
				low=mid+1;
		}
		//     low=high+1，  low    temp       
		
		// low i           
		int j;
		for (j=i;j>low;j--)
		{
			a[j]=a[j-1];
		}
		// temp   low     
		a[low]=temp;
	}
}

참고:
http://www.cnblogs.com/java-class/archive/2013/06/01/3112461.html
http://blog.csdn.net/ns_code/article/details/20043459