3 way quicksort (C implementation)

Question

implement 나는 C를 사용하는 순수한 일반 알고리즘을 사용하려고합니다. 3 방향 quicksort를 사용하지만 구현이 올바른 결과를 내지 못합니다. 출력은 거의 정렬되지만 일부 키는 있어야하는 위치가 아닙니다. 코드는 다음과 같습니다. 미리 감사드립니다.

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <time.h> 

static void swap(void *x, void *y, size_t size) { 
    void *tmp = malloc(size); 

    memcpy(tmp, x, size); 
    memcpy(x, y, size); 
    memcpy(y, tmp, size); 

    free(tmp); 
} 

static int cmpDouble(const void *i, const void *j) { 
    if (*(double *)i < *(double *)j) 
     return 1; 
    else if (*(double *)i == *(double *)j) 
     return 0; 
    else 
     return -1; 
} 

void qsort3way(void *base, int lo, int hi, size_t size, 
       int (*cmp)(const void *, const void *)) { 
    if (hi <= lo) 
     return; 
    else { 
     char *ptr = (char*)base; 
     char *v = ptr + lo * size; 

     int lt = lo, gt = hi; 
     int i = lo; 
     while (i <= gt) { 
      int c = cmp(v, ptr + i * size); 
      if (c < 0) 
       swap(ptr + (lt++) * size, ptr + (i++) * size, size); 
      else if (c > 0) 
       swap(ptr + i * size, ptr + (gt--) * size, size);  
      else 
       i++; 
     } 

     qsort3way(base, lo, lt - 1, size, cmp); 
     qsort3way(base, gt + 1, hi, size, cmp); 
    }  
} 

int main(void) { 
    int i; 
    double *d = (double*)malloc(sizeof(double) * 100); 

    for (i = 0; i < 100; i++) 
     d[i] = (double)rand(); 

    qsort3way(d, 0, 100 -1, sizeof(double), cmpDouble); 

    for (i = 0; i < 100; i++) 
     printf("%.10lf\n", d[i]); 

    free(d); 
    return 0; 
} 

샘플 출력 :

 
    41.0000000000 
    153.0000000000 
    288.0000000000 
    2082.0000000000 
    292.0000000000 
    1869.0000000000 
    491.0000000000 
    778.0000000000 
    1842.0000000000 
    6334.0000000000 
    2995.0000000000 
    8723.0000000000 
    3035.0000000000 
    3548.0000000000 
    4827.0000000000 
    3902.0000000000 
    4664.0000000000 
    5436.0000000000 
    4966.0000000000 
    5537.0000000000 
    5447.0000000000 
    7376.0000000000 
    5705.0000000000 
    6729.0000000000 
    6868.0000000000 
    7711.0000000000 
    9961.0000000000 
    8942.0000000000 
    9894.0000000000 
    9040.0000000000 
    9741.0000000000 

Answer 1

당신이 @JohnBollinger에게 제공하는 book link을 읽은 후. 알고리즘 작동 방식을 이해합니다. 문제는 피벗 이동이지만 v 값을 변경하지 않는다는 것입니다.

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

typedef void qsort3way_swap(void *a, void *b); 
typedef int qsort3way_cmp(void const *a, void const *b); 

static void qsort3way_aux(char *array_begin, char *array_end, size_t size, 
          qsort3way_cmp *cmp, qsort3way_swap *swap) { 
    if (array_begin < array_end) { 
    char *i = array_begin + size; 
    char *lower = array_begin; 
    char *greater = array_end; 
    while (i < greater) { 
     int ret = cmp(lower, i); 
     if (ret < 0) { 
     swap(i, lower); 
     i += size; 
     lower += size; 
     } else if (ret > 0) { 
     greater -= size; 
     swap(i, greater); 
     } else { 
     i += size; 
     } 
    } 
    qsort3way_aux(array_begin, lower, size, cmp, swap); 
    qsort3way_aux(greater, array_end, size, cmp, swap); 
    } 
} 

static void qsort3way(void *array_begin, void *array_end, size_t size, 
         qsort3way_cmp *cmp, qsort3way_swap *swap) { 
    qsort3way_aux(array_begin, array_end, size, cmp, swap); 
} 

static void swap_int_aux(int *a, int *b) { 
    int tmp = *a; 
    *a = *b; 
    *b = tmp; 
} 

static void swap_int(void *a, void *b) { swap_int_aux(a, b); } 

static int cmp_int_aux(int const *a, int const *b) { 
    if (*a < *b) { 
    return 1; 
    } else if (*a > *b) { 
    return -1; 
    } else { 
    return 0; 
    } 
} 

static int cmp_int(void const *a, void const *b) { return cmp_int_aux(a, b); } 

static void print_int(char const *intro, int const *array, size_t const size) { 
    printf("%s:", intro); 
    for (size_t i = 0; i < size; i++) { 
    printf(" %d", array[i]); 
    } 
    printf("\n"); 
} 

#define SIZE 42 

int main(void) { 
    int array[SIZE]; 

    srand((unsigned int)time(NULL)); 
    for (size_t i = 0; i < SIZE; i++) { 
    array[i] = rand() % SIZE - SIZE/2; 
    } 

    print_int("before", array, SIZE); 

    qsort3way(array, array + SIZE, sizeof *array, cmp_int, swap_int); 

    print_int("after", array, SIZE); 
} 

주 : int i = lo + 1; 및 char *i = array_begin + size;이 필수 최적화 귀하의 피벗 내가 당신에게 "적절한"솔루션을 제안 인덱스 lt

char *ptr = base; 

int lt = lo, gt = hi; // lt is the pivot 
int i = lo + 1; // we don't compare pivot with itself 
while (i <= gt) { 
    int c = cmp(ptr + lt * size, ptr + i * size); 
    if (c < 0) { 
    swap(ptr + lt++ * size, ptr + i++ * size, size); 
    } 
    else if (c > 0) 
    swap(ptr + i * size, ptr + gt-- * size, size); 
    else 
    i++; 
} 
qsort3way(base, lo, lt - 1, size, cmp); 
qsort3way(base, gt + 1, hi, size, cmp); 

이다. 왜냐하면 함수 비교 결과가 pivot != pivot이면 무한 재귀가 발생하기 때문입니다. 이것이 어떻게 가능할까요?

1. 기능 cmp는 버그입니다.
2. double에는 이상한 힘이 있습니다 ... 두 배가 그 자체와 같지 않을 수 있습니다! (-nan).

Answer 2

이 잘못된이기 때문에 구현에 올바른 결과가 제공되지 않습니다. 꽤 나쁘게 틀린, 실제로, 그것이 3 방향 quicksort이고, 규칙적인 하나가 아니기로되어 있기 때문에.

하나의 기본 문제는 주 파티션 루프 이후에 피벗을 적절한 위치로 옮기는 비트를 생략했다는 것입니다. 표준 퀵 소트의 경우 구현 세부 사항에 따라 루프 이후에 추가 스왑 또는 할당이 필요합니다. 하나 또는 두 개의 여분의 루프를 포함하여 잠재적으로 많은 값을 피벗과 동일한 위치로 이동시키는 3 방향 퀵 소트의 경우.

@Stargateur가 지적한 문제는 더 중요합니다. 값으로가 아닌 포인터로 피벗 요소를 추적하고 파티셔닝 루프 과정에서 원래 값을 그 위치에서 바꿀 때가 있습니다.

또한 3 방향 퀵 소트의 주 파티션 루프가 잘못되었습니다. 피벗과 동일한 요소를 만날 때 그냥 자리에 두지 만 대신 한쪽 끝 또는 다른 쪽 (또는 보조 기억 장치의 일종)으로 이동할 필요가 있습니다. 그렇게하면 메모리 비용이 발생합니다. 끝에서 가운데로 이동할 수 있습니다. 어떤 의미에서 이전 문제는이 경우의 특수한 경우입니다. 즉, 피벗 값을위한 공간을 예약하거나 피벗 값을 추적하지 않습니다. 이 문제를 해결하면 이전 문제도 해결됩니다.

구현을 준비하는 데 사용한 참조가 무엇인지 또는 처음부터 작성했는지 여부는 확실하지 않지만 Geeks for Geeks는 체크 아웃하려는 C++ (거의 C 임) implementation for int arrays을 가지고 있습니다.