qsort가이 값을 변경할 것으로 보인다

Question

나는 다음과 같은 문제와 붙어있어 :

int sort_compare(const void *x, const void *y) { 
    const int *xi = *(const int **) x; 
    const int *yi = *(const int **) y; 

    for (int i = 0; i < block_size; i++) { 
     comp_x[i] = block[(*xi + i) % block_size]; 
     comp_y[i] = block[(*yi + i) % block_size]; 
    } 

    return memcmp(comp_x, comp_y, block_size); 
} 

void sort() { 
    for (int i = 0; i < block_size; i++) { 
     printf("%d,", to_sort[i]); 
    } 
    puts(""); 
    qsort(to_sort, block_size, sizeof (int), sort_compare); 
    for (int i = 0; i < block_size; i++) { 
     printf("%d,", to_sort[i]); 
    } 
    puts(""); 
} 

values: 
    block_size = 5; 
    block = "jkldj"; 
    comp_x, compy_y and to_sort are well allocated 

output: 
    0,1,2,3,4, 
    3,0,1785357420,1,1684826986, 

to_sort이 (원형) 문자열에서, 예를 들어 첫 글자를 포함 (0,1,2,3)으로 표시

qwer 
werq 
erqw 
rqwe 

는로 표현

erqw 
rqwe 
qwer 
werq 

에 정렬 될 필요가 (2,3,0,1). 나는 아주 큰 숫자를 얻는 것 같다. 왜 그런가?

미리 감사드립니다. 당신이

const int *xi = *(const int **) x; 
const int *yi = *(const int **) y; 

을 초기화 할 때

Answer 1

x 및 y 당신의 비교기에있는 통과 포인터를 배열의 요소. 배열 요소는 int입니다. 따라서 int 값을 얻으려면 void 포인터를 int 포인터와 참조 해제로 변환해야합니다. 당신은 당신의 코드에서 간접의 추가 레이어를 가지고, 정말 다음과 같아야합니다

int xi = *(const int *) x; 
int yi = *(const int *) y; 

그럼 그냥 사용 xi 및 yi 대신 직접 *xi 및 *yi를 데이터 비교를 할 때. 당신이 두 배로 경우,

for (int i = 0; i < block_size; i++) { 
    char data_x = block[(xi + i) % block_size]; 
    char data_y = block[(yi + i) % block_size]; 
    if (data_x != data_y) 
     return data_x - data_y; 
} 

return 0; 

그리고 더 최적화로 : 당신은 그냥 루프에서 그들에게 자신을 비교할 수 있습니다 - 최적화로

후 별도의 배열에 데이터를 복사해야하고 memcmp을 없다 block 배열의 데이터 (예 : "qwer" 대신 "qwerqwer"이되도록)를 사용하면 더 이상 랩 어라운드를 처리 할 필요가 없기 때문에 memcmp에 대한 단일 호출로 비교할 수 있습니다. memcmp은 많이 최적화되어 있으므로 데이터가 많은 경우 memcmp을 손으로 작성한 for 루프를 사용하는 것이 훨씬 빠릅니다.

Answer 2

to_sort의 요소의 주소는 다음하는 const int**로되어 해석 xi 및 yi에 대한 값을 제공하기 위해 역 참조. 즉, (그리고 int*이 int보다 큰 경우)를 포인터로 해석합니다.

당신은 방금 void*의 캐스팅해야합니다

const int *xi = (const int *) x; 
const int *yi = (const int *) y; 

Answer 3

qsort()는 N 항목의 선형 목록을 제공함으로써 노래를 부릅니다. 여기서 주어진 항목 (n) 주소는 각 항목의 기준 주소 + 크기를 사용하여 계산할 수 있습니다. 그래서 간단한 것으로부터 시작하고, 간단히 말해 포인터 목록을 의미합니다.

먼저 버퍼의 원형은 복제본을 원본 (간단히 말하자면 1 바이트 미만)에 붙여 넣음으로써 에뮬레이트 될 수 있지만 약 1 바이트를 말하지 않을 것입니다. 나는.

"qwer" ==> "qwerqwer" 

이

을 수행 할 수 있습니다 : 이제 당신이

char *buff = malloc(2 * blocksize); 
memcpy(buff, to_sort, blocksize); 
memcpy(buff+blocksize, to_sort, blocksize); 

오프셋 0 .. (블록 크기-1), 각각의없이 서로 비교 될 수 문자의 블록 크기, 인 특수 포인터 수학.

다음에, 실제로 정렬이 경우,

char** ptrs = malloc(sizeof(char*) * blocksize); 
for (i=0;i<blocksize;i++) 
    ptrs[i] = buff+i; 

다음에, 두 개의 "아이템"비교 함수 포인터의리스트를 작성. 주소로 전달 된 항목은 문자열에 대한 포인터입니다. 다시, 주소는 왼쪽 및 오른쪽으로 과거로 우리가 두 개의 char *를 찾을 수있는 메모리 위치입니다.

int block_compare(const void *left, const void *right) 
{ 
    // memcmp would work for most platforms, but not all, so... 
    return strncmp(*(char **)left, *(char **)right, blocksize); 
} 

마지막

은 (이 qsort를 보낼) 등 :

qsort(ptrs, blocksize, sizeof(char*), block_compare); 

최종 출력 포인터의 블록 크기 길이리스트는 제조로 될 주소 자체 하지 CHAR * 아르 순환 버퍼, 각각은 블록 크기의 청크를 참조합니다. 위에서 설명한 모든의 전문은 다음과 같습니다

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

size_t blocksize = 0; 

int block_compare(const void *left, const void *right) 
{ 
    // memcmp would work for most platforms, but not all, so... 
    return strncmp(*(char **)left, *(char **)right, blocksize); 
} 


int main(int argc, char* argv[]) 
{ 
    char to_sort[] = "qwer"; 
    size_t i = 0; 

    // set blockize 
    blocksize = strlen(to_sort); 

    char *buff = malloc(2 * blocksize); 
    memcpy(buff, to_sort, blocksize); 
    memcpy(buff+blocksize, to_sort, blocksize); 

    char ** ptrs = malloc(blocksize * sizeof(char*)); 
    for (i=0;i<blocksize;++i) 
     ptrs[i] = buff+i; 

    // now send the pointer list to qsort() 
    qsort(ptrs, blocksize, sizeof(*ptrs), block_compare); 

    // ptrs is sorted. do with it what you will. 
    for (i=0;i<blocksize;i++) 
    { 
     fwrite(ptrs[i], sizeof(char), blocksize, stdout); 
     fwrite("\n", sizeof(char), 1, stdout); 
    } 
    fflush(stdout); 

    free(ptrs); 
    free(buff); 

    return EXIT_SUCCESS; 
} 

는 "qwer"를 사용하여 생성합니다 "asubstantiallylongerstringtest"

allylongerstringtestasubstanti 
antiallylongerstringtestasubst 
asubstantiallylongerstringtest 
bstantiallylongerstringtestasu 
erstringtestasubstantiallylong 
estasubstantiallylongerstringt 
gerstringtestasubstantiallylon 
gtestasubstantiallylongerstrin 
iallylongerstringtestasubstant 
ingtestasubstantiallylongerstr 
llylongerstringtestasubstantia 
longerstringtestasubstantially 
lylongerstringtestasubstantial 
ngerstringtestasubstantiallylo 
ngtestasubstantiallylongerstri 
ntiallylongerstringtestasubsta 
ongerstringtestasubstantiallyl 
ringtestasubstantiallylongerst 
rstringtestasubstantiallylonge 
stantiallylongerstringtestasub 
stasubstantiallylongerstringte 
stringtestasubstantiallylonger 
substantiallylongerstringtesta 
tantiallylongerstringtestasubs 
tasubstantiallylongerstringtes 
testasubstantiallylongerstring 
tiallylongerstringtestasubstan 
tringtestasubstantiallylongers 
ubstantiallylongerstringtestas 
ylongerstringtestasubstantiall 

남자가 내가 그했다 희망 사용

erqw 
qwer 
rqwe 
werq 

또 다른 샘플 무엇을 찾고 있었다. (아휴).