빠른 분류를 이해해야합니다.

빠른 정렬을 이해하는 데 어려움을 겪고 있습니다. 여기 내 이해빠른 분류를 이해해야합니다.

우리는 피벗보다
모든 요소가 피벗보다는 모든 요소 이상이 바로
사용 재귀로 이동 피벗
의 왼쪽에 갈 피벗을 선택 지금까지입니다 이 프로세스를 계속하십시오.

내 문제는 재귀 인 마지막 단계를 계속하는 방법을 이해할 수 없다는 것입니다. 나는 지금까지 다음과 같은 것을 가지고있다. 나는 아주 기본적인 것을 원한다. 배열은

void quickSort(int *ptr,int lowindex , int highindex) 
{ 
    int left = lowindex ; 
    int right = highindex; 
    int pivot = ptr[rand()%highindex]; 

    while(left < right) 
    { 
     while(ptr[left] < pivot) 
     { 
      left++; 
     } 
     while(ptr[right] > pivot) 
     { 
      right--; 
     } 

     //Now swap the two 
     int temp = ptr[left]; 
     ptr[left] = ptr[right]; 
     ptr[right] = temp; 
    } 

    std::cout << "Current Array is : "; 
    for(int i=0;i<7;i++) 
    { 
     std::cout << ptr[i] << "," ; 
    } 
    std::cout << "\n"; 

     //How to add recursion ? 
}

또한 붙어 얻을 while(left < right) 루프에 대한 가능성이 중복

이 없습니다 - 즉 왼쪽과 오른쪽이 반복 계속해서 이렇게 변경하지 마십시오? 그렇다면 어떻게 처리해야합니까?

출처

2014-03-01 Rajeshwar

'ptr [left]'와'ptr [right]'가 모두 피벗과 동일한 값을 가리킬 때 어떤 점이 좋습니까? –

흠. 나는 그것을 고려하지 않았다. – Rajeshwar

int pivot = ptr[rand()%highindex];

이 줄 활성 범위 lowindex 및 highindex 사이라고 가정

int pivot = ptr[lowindex+rand()%(highindex-lowindex+1)];

될 것이다. 하지만 피벗이 왼쪽 또는 오른쪽 부분에 속하는지 알 수없는 문제가 발생하더라도 pivot=ptr[lowindex]과 같이 고정 된 위치에서 선택하는 것이 더 쉽습니다. 당신의 비교 연산의

하나는 피벗 넘어 left 포인터를 발견하고 right 포인터의 오른쪽 것이다 끝에

while(ptr[left] <= pivot)

처럼, 평등을 포함해야한다. 이 경우 스왑 작업을해서는 안됩니다.

if(left < right){ // swap

당신이해야 할 파티션이 있는지 피벗 값은 두 섹션이 같은 기능 무언가의 끝 부분에 추가 재귀에 대한 마지막

swap(ptr[lowindex /*pivot*/], ptr[right]);

사이 종료 후 :

quickSort(ptr, lowindex, right-1); 
quickSort(ptr, left, highindex);

일반적인 개념은 다소 단순하지만 세부 사항은 제대로 이해하기가 다소 까다 롭습니다. 디버깅을 준비하십시오. 희망이 도움이됩니다.

출처

2014-03-01 23:09:01 pentadecagon

빠른 분류를 이해해야합니다.

답변

관련 문제