Implementasi universal bubble sort di C

Saya mencoba membuat fungsi pengurutan gelembung universal. Ini memungkinkan pengguna untuk menulis fungsi perbandingan dan pertukarannya sendiri. Saya menerapkan fungsi pertukaran dan perbandingan untuk tipe int, tetapi ketika saya menjalankan kode untuk array berikutnya: {3, 5, 8, 9, 1, 2, 4, 7, 6, 0} , saya mendapatkan: 0 0 84214528 2312 1 2 4 7 6 0. Mengapa hal ini terjadi?

#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
}

Saya pikir masalahnya ada di 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;
}

Terimakasih atas bantuannya!


c pointers void-pointers function-pointers bubble-sort
person Mihail Feraru    schedule 02.09.2014    source sumber
comment
Anda harus meneruskan ukuran elemen sebagai parameter ke fungsi, dan mengganti address + i dengan address + i * elementSize, jika tidak, alamat yang Anda dapatkan akan mengarah ke tengah elemen array.   -  person mephi42    schedule 02.09.2014
comment
Daripada mendefinisikan makro true dan false, lebih baik sertakan <stdbool.h> dan gunakan bool.   -  person ikh    schedule 02.09.2014
comment
@ mephi42 , elementSize akan menjadi int? jika saya mendeklarasikan:void bubbleSort(void *address, int len, int elementSize, int (*comp)(void *a, void *b), void (*swap)(void *a, void *b)) dan saya menelepon seperti di sini: bubbleSort(alamat, len, sizeof(int), &compInt, &swapInt); , jawabannya salah.   -  person Mihail Feraru    schedule 02.09.2014
comment
Saya akan memodelkan fungsi Anda setelah fungsi qsort standar, dan menggunakan size_t.   -  person mephi42    schedule 02.09.2014
comment
@ mephi42 , terima kasih banyak!   -  person Mihail Feraru    schedule 02.09.2014

Jawaban (1)


arrow_upward
4
arrow_downward

Terima kasih @mephi42. Ini versi pembaruannya.

Masalahnya ada pada fungsi bubbleSort Anda. Anda harus menambahkan address dengan offset dikalikan dengan ukuran elemen.

Kode yang tepat seharusnya:

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;
    }
}

Dan kemudian panggil fungsinya seperti:

bubbleSort(address, len, sizeof(int), compInt, &swapInt);
person Landys    schedule 02.09.2014
comment
Saya pikir tujuannya adalah untuk memisahkan fungsi dari tipe data aktual, jadi casting ke int bukanlah suatu pilihan - array mungkin juga terdiri dari floats. - person mephi42; 02.09.2014
comment
Terima kasih sobat! berhasil! tetapi, apakah array memiliki tipe data lain? - person Mihail Feraru; 02.09.2014
comment
Ya, @mephi42 benar. Lalu, sepertinya kita harus meneruskan ukuran elemennya, yang sepertinya tidak keren. Apakah ada cara lain untuk menghindari melewatkan lebih banyak parameter? - person Landys; 02.09.2014
comment
Ya, melewatkan ukuran elemen tidak terlalu buruk atau tidak biasa. Fungsi C standar seperti calloc() atau fread() atau qsort() - yang sebenarnya merupakan versi standar fungsi OP - semuanya melakukannya. - person mephi42; 02.09.2014