2 조 정렬 말 해 봐.

3317 단어 계산법 의 점적
프로필
    2 조 정렬 (Bitonic Sort) 은 정렬 네트워크 (Sorting Network) 의 하나 로 병렬 계산 이 가능 한 정렬 알고리즘 입 니 다.
    2 조 정렬 을 이해 하려 면 먼저 2 조 서열 을 이해 해 야 한다. 2 조 서열 의 정 의 는 다음 과 같다.
    만약 에 서열 이 다음 과 같은 두 가지 조건 중 하 나 를 만족 시 키 면 쌍 조 서열 이 라 고 부른다.™
    0 ≤ k ≤ n - 1 이 존재 하여 오름차 순 으로, 내림차 순 으로, 또는 하나의 레이 블 의 순환 이동 이 존재 하여 조건 1) 을 만족 시 킵 니 다.
    만약 n 이 짝수 이 고 오름차 순 이 며 내림차 순 이 라면 다음 과 같은 두 서열 은 모두 쌍 조 서열 이다.
    S1=
    S2=
    2 조 정렬 주요 사상:
    1. 먼저 끊 임 없 는 2 점 으로 각 조 에 하나의 요소 만 남 을 때 까지 병합 을 시작한다.
    2. 2 조 정렬 을 병합 할 때 n 보다 크 지 않 은 최대 2 의 멱 차방 2 ^ k 를 경계 로 2 ^ k ~ n 의 요 소 를 각각 0 ~ (n - 2 ^ k) 의 요소 와 비교 한 다음 에 0 ~ 2 ^ k 와 2 ^ k ~ n 두 부분 에 비교 네트워크 를 응용 합 니 다.
    3. 2 조 정렬 이 이해 하기 어 려 운 부분 은 바로 이 병합 과정 에 있 습 니 다. 만약 에 우리 가 길이 가 n 인 서열 a 승 서 를 배열 해 야 한다 고 가정 하면 2 분 동안 전 n / 2 의 서열 을 내림차 순 으로 배열 한 후에 n / 2 의 서열 승 서 를 배열 한 것 이 고 n - 2 ^ k < n / 2 이기 때문에 전 n - 2 ^ k 와 후 n - 2 ^ k 개 요 소 는 모두 중간 요소 보다 크 고 현재 n - 2 ^ k 개 요소 와 후 n - 2 ^ k 개 요 소 를 비교 할 때서열 에서 가장 큰 n - 2 ^ k 개 요 소 를 마지막 n - 2 ^ k 개 위치 에 놓 습 니 다. 즉, 비교 한 후에 2 ^ k ~ n 의 요 소 는 0 ~ 2 ^ k 의 요소 보다 큽 니 다. 그러면 이 두 단락 을 각각 같은 방법 으로 병합 하여 최종 적 으로 완전한 오름차 순 서 를 얻 을 수 있 습 니 다.
    6 개 원소 의 서열 을 예 로 들 면 현재 3 개 원 소 는 내림차 순 으로 배열 되 었 고, 후 3 개 원 소 는 이미 오름차 순 으로 배열 되 었 다 (끝까지 돌아 갈 때 1 개 원소 부터 되 돌 아 왔 기 때문에 6 개 원소 가 합 병 될 때 전후 3 개 원 소 는 이미 정렬 되 었 다). 이것 은 4 (6 보다 크 지 않 은 최대 2 의 幂 次 方) 를 경계 로 각각 1 개 와 5 개, 2 개 와 6 개 원 소 를 비교한다.이 6 개 요소 중 가장 큰 두 개 를 5, 6 번 째 위치 에 놓 은 다음 에 각각 앞의 4 개 와 뒤의 2 개 요 소 를 이 방법 에 따라 병합 한 다음 에 재 귀 하여 순 서 를 완성 합 니 다.
2. 알고리즘 실현
//      
template 
void BitonicMerge(T* pFirst,T* pLast,bool bDirection)
{
	T* pTemp = pFirst;
	if(pFirst < pLast)
	{
		int nLength = pLast - pFirst + 1;                   //      
		int nMid = 1;
		while(nMid < nLength)                               //         2       k
			nMid = nMid << 1;
		nMid = nMid >> 1;
		for(int i=0;i< nLength - nMid;i++)                  //   0~n-k   k~n    ,        bDirection       
		{
			if((*(pTemp+i) > *(pTemp+i+nMid)) == bDirection)
			{
				Swap(*(pTemp+i),*(pTemp+i+nMid));
			}
		}
		BitonicMerge(pFirst,pFirst+nMid-1,bDirection);      //                  
		BitonicMerge(pFirst+nMid,pLast,bDirection);
	}
}


//Bitonic  (    ):      (Sorting Network)   ,               。
//  ,                      ,              。
//               ,                    
template 
bool BitonicSort(T* pFirst,T* pLast,bool bDirection,Compare pFun)
{
	bool bIsReverse = false;
	T* pTemp = NULL;
	if((pFirst == NULL) || (pLast == NULL))
	{
		cout< pLast)
	{
		bIsReverse = true;
		pTemp = pFirst;
		pFirst = pLast;
		pLast = pTemp;
	}
	if(pFirst < pLast)
	{
		int nNum = pLast - pFirst + 1;                         //      
		int nMid = nNum / 2;                                   //         
		BitonicSort(pFirst,pFirst+nMid-1,!bDirection);         //             
		BitonicSort(pFirst+nMid,pLast,bDirection);             //             
		BitonicMerge(pFirst,pLast,bDirection);                 //      
	}
	if(bIsReverse)
	{
		while(pFirst < pLast)
		{
			Swap(*pFirst,*pLast);
			++pFirst;
			--pLast;
		}
	}
	return true;
}

    기타
정렬 알고리즘 및 데이터 구조의 구체 적 인 실현 은 GitHub 참조:https://github.com/daiyl0320/IntroductionToAlgorithms。

좋은 웹페이지 즐겨찾기