C 배열 파티션

Question

배열에서 퀵 정렬을 사용하려고하는데, 내가 잘못하고있는 것이 확실하지 않습니다. 순서에 내 번호는

-2 0 1 4 7 9 11 12 15

내가 얻고 그러나해야한다 :

0 1 4 7 15 12 11 9 -2

int partition(int* a, int left, int right) 
{ 
    int pivot, leftPoint, rightPoint, temp; 
    pivot = a[left]; 
    leftPoint = left; 
    rightPoint = right + 1; 

    while(rightPoint > leftPoint) 
    { 
     while(a[leftPoint] <= pivot && leftPoint <= right) 
      leftPoint ++; 
     while(a[rightPoint] > pivot) 
      rightPoint --; 
     temp = a[leftPoint]; 
     a[leftPoint] = a[rightPoint]; 
     a[rightPoint] = temp; 
    } 
    temp = a[left]; 
    a[left] = a[rightPoint]; 
    a[rightPoint] = temp; 
    return rightPoint; 
} 

0 : 여기에

내 파티션 코드

누군가 내 알고리즘에 문제가 있음을 설명 할 수 있습니까?

EDIT : 이 내 초기 배열이다

7-12 1-2 0 15 4 11 9

제가

quicksort(a, 0, 8); 

이것은 구현은 퀵로 전화 내 퀵 소트 :

void quickSort(int a[], int low, int high) 
{ 
    int pivotPoint; 
    if(low < high) 
    { 
     // divide and conquer 
     pivotPoint = partition(a, low, high); 
     quickSort(a, low, pivotPoint); 
     quickSort(a, pivotPoint + 1, high); 
    } 
} 

추가 정보

Answer 1

는 문제가 거의 확실에 놓여 :

rightPoint = right + 1; 

당신이 (a, 0, 8)에 대한 분할 루프에 들어가, 당신은 유효한부터 나쁜 소식이다 피벗 값으로 a[9]을 비교하고 인덱스는 a[0] ~ a[8]입니다. 여기

은 당신의 코드는 SSCCE ( Short, Self-Contained, Correct Example)로 변환됩니다 : 실행

#include <stdio.h> 
#include <assert.h> 

static 
int partition(int *a, int left, int right) 
{ 
    int pivot, leftPoint, rightPoint, temp; 
    pivot = a[left]; 
    leftPoint = left; 
    rightPoint = right + 1; 

    while (rightPoint > leftPoint) 
    { 
     while (a[leftPoint] <= pivot && leftPoint <= right) 
      leftPoint++; 
     while (a[rightPoint] > pivot) 
      rightPoint--; 
     assert(a[leftPoint] != -99 && a[leftPoint] != +99); 
     assert(a[rightPoint] != -99 && a[rightPoint] != +99); 
     assert(leftPoint >= left && leftPoint <= right); 
     assert(rightPoint >= left && rightPoint <= right); 
     temp = a[leftPoint]; 
     a[leftPoint] = a[rightPoint]; 
     a[rightPoint] = temp; 
    } 
    temp = a[left]; 
    a[left] = a[rightPoint]; 
    a[rightPoint] = temp; 
    return rightPoint; 
} 

static 
void quickSort(int a[], int low, int high) 
{ 
    int pivotPoint; 
    if (low < high) 
    { 
     // divide and conquer 
     pivotPoint = partition(a, low, high); 
     quickSort(a, low, pivotPoint); 
     quickSort(a, pivotPoint + 1, high); 
    } 
} 

int main(void) 
{ 
    int aplus[] = 
    { 
     +99, +99, +99, 
     7, 12, 1, -2, 0, 15, 4, 11, 9, 
     -99, -99, -99 
    }; 
    int *a = aplus + 3; 

    quickSort(a, 0, 8); 
    return 0; 
} 

의 주장 화재 중 하나를

Assertion failed: (a[rightPoint] != -99 && a[rightPoint] != +99), 
    function partition, file partn.c, line 19. 

Answer 2

당신이 당신의 파티션의 첫 번째 요소 등을 사용하는 것 문지방. 그럼

leftPoint = left; 
rightPoint = right + 1; 

여기에 포함 시키십시오.

temp = a[left]; 
a[left] = a[rightPoint]; 
a[rightPoint] = temp; 

여기 끝내면 파티션 중간으로 바꿉니다. 먼저 배열을 넘지 않는 초 문턱을 제외하고, 필요 :

leftPoint = left+1; 
rightPoint = right; 

편집을 당신 alsho 임계 값은 다음 요소보다 작은 경우 확인 만 사실이 경우 교체해야 :

if(a[left+1] < pivot) { 
    temp = a[left]; 
    a[left] = a[rightPoint]; 
    a[rightPoint] = temp; 
    rightPoint = left; 
} 

배열이 이미 정렬 된 경우 또는 파티션이 실패합니다.

완전히 임계 값을 제외 할 수 교수형 찾는 최적화 여기

pivotPoint = partition(a, low, high); 
    quickSort(a, low, pivotPoint); 
    quickSort(a, pivotPoint + 1, high); 

으로

(최종 편집의) :

quickSort(a, low, pivotPoint-1);