Bubble Сортировка с помощью указателей на функцию

Question

Я пытаюсь реализовать сортировку пузырьков в c, используя указатели для работы, но не работает. Может кто-нибудь мне помочь? Вот код:

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

void bubbleSort(void** base, size_t length, int (*compar)(const void*, const void*)); 

int main(int argc, char* argv[]) { 
    int cmp(const void*, const void*); 
    int vet[] = {1, 2, 5, 7, 6, 1, 3, 2, 9, 15, 14, 20}; 
    bubbleSort((void**) &vet, sizeof(vet)/sizeof(vet[0]), cmp); 
    int i; 
    for (i = 0; i < sizeof(vet)/sizeof(vet[0]); i++) { 
     printf("%d\n", vet[i]); 
    } 
    return 0; 
} 

int cmp(const void* x, const void* y) { 
    return **((int* const*) x) - **((int* const*) y); 
} 

void bubbleSort(void** base, size_t length, int (*compar)(const void*, const void*)) { 
    int i, j; 
    void swap(void*, void*); 
    for (i = 0; i < length; i++) { 
     for (j = 1; j < length; j++) { 
      if ((*compar)(base[i], base[i]) < 0) { 
       swap(base[i], base [j]); 
      } 
     } 
    } 
} 

void swap(void* a, void* b) { 
    void* tmp = a; 
    a = b; 
    b = tmp; 
} 

Выход такой же вектор без сортировки. (Извините за мой английский)

Answer 1

Когда я запустил вышеуказанный код на своей машине, я получил SIGSEGV. Затем я обнаружил, что в вашем коде много ошибок.

Во-первых, ваша функция swap на самом деле ничего не делает! Вы передаете две указатели на элементы массива этой функции. Вы просто заменяете адреса, на которые они указывали ранее. Это совершенно бесполезно. Его можно написать разными способами. Я предпочитаю следующее:

void swap(void* a, void* b) { 
//get the int pointers... 
int* t_a = (int*)a; 
int* t_b = (int*)b; 

//now change the values in them... 
int tmp = *t_a; 
*t_a = *t_b; 
*t_b = tmp; 

}

Поэтому я отливают их первым int является то, что бессмысленно назначать значение в void*.

Код bubbleSort, что вы думаете base[i] в вашем коде? Это не значение элемента ith в массиве. Он является двунаправленным, base[i] фактически ссылается на указатель ith, указывающий на какой-либо другой массив.

Поскольку здесь существует только один массив, поэтому base[0] является единственным действительным адресом, который у нас есть. Если вы попытаетесь ссылаться на другие указатели, тогда это будет SIGSEGV, который я предвидел перед запуском кода.

Что вам нужно сделать, сначала получите указатель, указывающий на первый элемент массива (скажем ptr). Теперь ptr - не что иное, как наш начальный массив. Затем используйте это.

void bubbleSort(void** base, size_t length, int (*compar)(const void*, const void*)) { 
    int i, j; 
    int *ptr = &(*base); 
    for (i = 0; i < length; i++) { 
     for (j = 1; j < length; j++) { 
      if ((*compar)(&ptr[i], &ptr[j]) < 0) { 
       swap(&ptr[i], &ptr[j]); 
      } 
     } 
    } 
} 

Надеется, что это помогает ...

Answer 2

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

int cmp(const void *x, const void *y){ 
    int a = *(const int *)x; 
    int b = *(const int *)y; 
    return a < b ? -1 : (a > b); 
} 

void swap(void *a, void *b, size_t type_size) { 
    void *tmp = malloc(type_size); 
    memcpy(tmp, a, type_size); 
    memcpy(a, b, type_size); 
    memcpy(b, tmp, type_size); 
    free(tmp); 
} 

void bubbleSort(void *base, size_t length, size_t type_size, int (*compar)(const void*, const void*)) { 
    int i, j; 
    for (i = 0; i < length - 1; ++i) { 
     for (j = i+1; j < length; ++j){ 
      char *data_i = (char*)base + type_size * i; 
      char *data_j = (char*)base + type_size * j; 
      if(compar(data_i, data_j) > 0) 
       swap(data_i, data_j, type_size); 
     } 
    } 
} 

int main() { 
    int vet[] = {1, 2, 5, 7, 6, 1, 3, 2, 9, 15, 14, 20}; 
    bubbleSort(vet, sizeof(vet)/sizeof(*vet), sizeof(*vet), cmp); 
    int i; 
    for (i = 0; i < sizeof(vet)/sizeof(*vet); i++) { 
     printf("%d\n", vet[i]); 
    } 
    return 0; 
}