Универсальная реализация пузырьковой сортировки на C

Я пытаюсь сделать универсальную функцию пузырьковой сортировки. Это позволяет пользователю написать свою собственную функцию сравнения и замены. Я реализовал функцию подкачки и сравнения для типа int, но когда я запускаю код для следующего массива: {3, 5, 8, 9, 1, 2, 4, 7, 6, 0}, я получаю: 0 0 84214528 2312 1 2 4 7 6 0. Почему это происходит?

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

#define true 1
#define false 0

int compInt(void *a, void *b) // FUNCTION FOR COMPARE INT
{
    if (*(int*)(a) > *(int*)(b)) { return false; } // IF FIRST INT > SECOND INT (WRONG ORDER) RETURN FALSE
    return true; // RIGHT ORDER -> RETURN TRUE
}

Думаю проблема где-то в swapInt.

void swapInt(void *a, void *b) // FUNCTION FOR SWAP INT
{
    int aux; // TEMPORARY VARIABLE, IT STORAGES VALUE OF *(int*)(a)

    aux = *(int*)(a);
    *(int*)(a) = *(int*)(b); // a value is now equal to b value
    *(int*)(b) = aux; // b has value of aux
}

void bubbleSort(void *address, int len, int (*comp)(void *a, void *b), void (*swap)(void *a, void *b)) // bubble sort function allow to user to write it's compare and swap function
{
    int newlen;

    while (len != 0) {
        newlen = 0;
        for (int i = 1; i < len; i++) {         
            if (!comp(address + i - 1, address + i)) {
                swap(address + i - 1, address + i);
                newlen = i;  
            }
        }
        len = newlen;
    }
}

int main()
{
    int array[] = {3, 5, 8, 9, 1, 2, 4, 7, 6, 0}; // CREATE AN ARRAY OF INT
    int len = 10; // DECLARE IT LEN

    void *address; // VOID POINTER TO ARRAY
    address = array;

    bubbleSort(address, len, &compInt, &swapInt); // SORT IT 
    for (int i = 0; i < len; ++i) { 
        printf("%d ", array[i]); // PRINT IT
    }

    return 0;
}

Спасибо за помощь!


c pointers void-pointers function-pointers bubble-sort
person Mihail Feraru    schedule 02.09.2014    source источник
comment
Вам нужно передать размер элемента в качестве параметра функции и заменить address + i на address + i * elementSize, иначе полученные вами адреса будут указывать на середину элементов массива.   -  person mephi42    schedule 02.09.2014
comment
Вместо определения макросов true и false лучше включить <stdbool.h> и использовать bool.   -  person ikh    schedule 02.09.2014
comment
@mephi42 mephi42, elementSize будет int? если я объявляю: void bubbleSort(void *address, int len, int elementSize, int (*comp)(void *a, void *b), void (*swap)(void *a, void *b)) и я вызываю как здесь: bubbleSort(address, len, sizeof(int), &compInt, &swapInt); , ответ неверный.   -  person Mihail Feraru    schedule 02.09.2014
comment
Я бы смоделировал вашу функцию на основе стандартной функции qsort, и она использует size_t.   -  person mephi42    schedule 02.09.2014
comment
@mephi42, большое спасибо!   -  person Mihail Feraru    schedule 02.09.2014

Ответы (1)


arrow_upward
4
arrow_downward

Спасибо @mephi42. Вот версия обновления.

Проблема в вашей функции bubbleSort. Вы должны добавить address со смещением, умноженным на размер элемента.

Правильные коды должны быть:

void bubbleSort(void *address, int len, size_t ele_size, int (*comp)(void *a, void *b), void (*swap)(void *a, void *b)) // bubble sort function allow to user to write it's compare and swap function
{
    int newlen;

    while (len != 0) {
        newlen = 0;
        for (int i = 1; i < len; i++) {         
            if (!comp((char*)address + ele_size * (i - 1), (char*)address + ele_size * i)) {
                swap((char*)address + ele_size * (i - 1), (char*)address + ele_size * i);
                newlen = i;  
            }
        }
        len = newlen;
    }
}

И затем вызовите функцию, например:

bubbleSort(address, len, sizeof(int), compInt, &swapInt);
person Landys    schedule 02.09.2014
comment
Я думаю, что его цель состоит в том, чтобы отделить функцию от фактического типа данных, поэтому приведение к int не вариант — массив также может состоять из float. - person mephi42; 02.09.2014
comment
Спасибо чувак! оно работает! но если массив имеет другой тип данных? - person Mihail Feraru; 02.09.2014
comment
Да, @mephi42 прав. Затем, кажется, мы должны передать размер элемента, что выглядит не очень круто. Есть ли другой способ избежать передачи большего количества параметров? - person Landys; 02.09.2014
comment
Что ж, передача размера элемента не так уж плоха или необычна. Стандартные функции C, такие как calloc() или fread() или qsort(), которые на самом деле являются стандартной версией функции OP, все это делают. - person mephi42; 02.09.2014