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。
좋은 웹페이지 즐겨찾기
