Bubble sort การใช้งานสากลใน C

ฉันกำลังพยายามสร้างฟังก์ชันการเรียงลำดับฟองสากล อนุญาตให้ผู้ใช้เขียนฟังก์ชันการเปรียบเทียบและสลับของตัวเอง ฉันใช้ฟังก์ชัน swap และเปรียบเทียบสำหรับประเภท 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;
}

ขอบคุณที่ช่วยเหลือ!


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 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)


ขอบคุณ @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 ไม่ใช่ตัวเลือก - อาร์เรย์อาจประกอบด้วย floats เช่นกัน - 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