Jinsi ya Kutumia qsort katika C: Ufafanuzi wa Upangaji wa Safu na Miundo kwa Ufanisi

1. Muhtasari wa Kazi ya qsort

Kazi ya qsort, iliyotolewa katika maktaba ya kawaida ya C, ni zana yenye nguvu kwa ajili ya kupanga vipengele ndani ya array. Kwa kutumia algoriti ya quicksort, qsort inaweza kupanga upya data kwa ufanisi kwa kasi ya juu. Sehemu hii inaeleza misingi ya qsort na inajadili kwa nini kazi hii ni muhimu kwa programu ya C.

Qsort ni nini?

qsort ni kazi yenye uwezo mwingi ambayo inapanga array au orodha kulingana na kazi ya kulinganisha iliyofafanuliwa na mtumiaji. Kama kazi ya kawaida katika C, inatumika sana katika mazingira mbalimbali ya maendeleo. Kwa mfano, unaweza kupanga array za nambari za kiwango, array za herufi, na hata array za miundo kwa ufanisi.

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

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int values[] = {40, 10, 100, 90, 20, 25};
    size_t values_len = sizeof(values)/sizeof(values[0]);

    qsort(values, values_len, sizeof(int), compare);

    for(int i = 0; i < values_len; i++) {
        printf("%d ", values[i]);
    }
    return 0;
}

Msimbo hapo juu unaonyesha mfano wa msingi wa kupanga array ya nambari za kiwango kwa kutumia qsort. Hapa, kazi ya kulinganisha inaamua mpangilio wa vipengele ndani ya array.

2. Vigezo vya qsort na Matumizi

Mfumo wa qsort ni kama ifuatavyo:

void qsort(void *base, size_t num, size_t size, int (*compar)(const void *, const void *));

Maelezo ya Vigezo

1. base : Pointer kwa kipengele cha kwanza cha array kitakachopangwa.
2. num : Idadi ya vipengele katika array.
3. size : Ukubwa wa kila kipengele kwa baiti.
4. compar : Pointer kwa kazi ya kulinganisha.

Kazi hii inapanga vipengele kulingana na kazi ya kulinganisha. compar inachukua vipengele viwili kama hoja na inarudisha ni ipi kubwa. Uwezo huu wa kubadilika unakuruhusu kupanga aina mbalimbali za data.

Jinsi ya Kuunda Kazi ya Kulinganisha

Kazi ya kulinganisha ndiyo ufunguo wa jinsi qsort inavyofanya kazi. Unaweza kufafanua kazi inayolinganisha vipengele viwili, kama inavyoonyeshwa chini:

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

Kazi hii inalinganisha maadili ya a na b. Inarudisha thamani hasi ikiwa a ni ndogo kuliko b, 0 ikiwa sawa, au thamani chanya ikiwa kubwa. Hii inamruhusu qsort kupanga array kwa mpangilio wa kuongezeka.

3. Jinsi qsort Inavyofanya Kazi Ndani: Algoriti ya Quicksort

qsort inatumia algoriti ya quicksort ndani. Quicksort ni algoriti ya kugawanya na kushinda ambayo inafanya kazi kama ifuatavyo:

1. Chagua Pivot : Chagua kipengele cha pivot, mara nyingi kutoka katikati au mwisho wa array.
2. Partition : Hamisha vipengele vidogo kuliko pivot kwa upande wa kushoto, na vipengele vikubwa kwa upande wa kulia.
3. Panga Upinde : Rudiarisha mchakato kwa kila sub-array.

Mchakato huu wa kugawanya na kuunganisha unaruhusu array kupangwa kwa ufanisi. Ugumu wa wastani wa wakati wa quicksort ni O(n log n), na hivyo inafanya iwe haraka zaidi kuliko algoriti nyingi nyingine za kupanga. Hata hivyo, katika hali mbaya zaidi (kama array zilizopangwa tayari), ugumu unaweza kudhoofisha hadi O(n^2), kwa hivyo kujali ni muhimu.

4. Kuunda Kazi za Kulinganisha

Nguvu ya qsort iko katika uwezo wake wa kutumia kazi za kulinganisha maalum kwa aina tofauti za data. Chini kuna mifano kwa aina tofauti za data.

Kazi ya Kulinganisha kwa Nambari za Kiwango

int compare_int(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

Kazi ya Kulinganisha kwa Herufi

int compare_str(const void *a, const void *b) {
    return strcmp(*(const char**)a, *(const char**)b);
}

Kazi ya Kulinganisha kwa Miundo

struct Person {
    int id;
    const char* name;
};

int compare_person(const void *a, const void *b) {
    return ((struct Person*)a)->id - ((struct Person*)b)->id;
}

Kwa kazi za kulinganisha maalum kama hizi, qsort inaweza kupanga array kwa kubadilika kulingana na maudhui yake.

5. Kupanga Array za Miundo kwa qsort

qsort ni muhimu hasa kwa kusort nyingi zinazoshughulikia miundo. Kwa mfano, fikiria kusort nyingi ya miundo ya Person kwa uwanja wao wa id:

struct Person people[] = {
    {1, "Alice"},
    {3, "Charlie"},
    {2, "Bob"}
};

qsort(people, 3, sizeof(struct Person), compare_person);

Kwa kutumia kazi ya compare_person, unaweza kusort kwa id na kupanga mpangilio kama Alice, Bob, na Charlie.

6. Ubora wa Utendaji na Kulinganisha na Algoriti Zingine

Utendaji wa Quicksort

Quicksort ni yenye ufanisi mkubwa wakati wa kushughulikia data ya nasibu, ikiwa na ugumu wa wastani wa wakati wa O(n log n). Hata hivyo, kwa data iliyosort tayari, utendaji wake mbaya zaidi unaweza kushuka hadi O(n^2). Kwa hivyo, wakati quicksort inapendekezwa kwa seti za data za nasibu, algoriti zingine zinaweza kuwa bora chini ya hali maalum.

Kulinganisha na Heapsort

Heapsort inatoa utendaji thabiti wa O(n log n) hata katika hali mbaya zaidi, na hivyo kuifanya iwe thabiti zaidi kuliko quicksort. Bado, quicksort kwa kawaida ni haraka zaidi wastani na data ya nasibu, hivyo inabaki kuwa chaguo linalopendelewa katika hali nyingi.

Kulinganisha na Mergesort

Mergesort pia ni algoriti ya kusort thabiti yenye ugumu wa O(n log n). Inafaa wakati kusort thabiti (kudumisha mpangilio wa asili kwa vipengele sawa) inahitajika. Wakati quicksort si thabiti, kwa matumizi mengi ya kawaida hii si tatizo kubwa.

7. Hitimisho

qsort ni kazi yenye nguvu ya kusort inayopatikana katika C, inayojulikana kwa unyumbufu na kasi yake. Kwa kutumia kazi za kulinganisha za kibinafsi, unaweza kusort nyingi za aina mbalimbali za data na miundo, ambayo inafanya qsort iwe ya vitendo sana katika matumizi ya ulimwengu halisi.

Kuelewa algoriti ya quicksort inakuwezesha kupata faida kubwa zaidi kutoka kwa qsort. Kulingana na seti yako ya data na mahitaji, fikiria kulinganisha na algoriti zingine kama heapsort au mergesort ili kuboresha utendaji.

Jaribu kutumia qsort kwa usahihi katika miradi yako ya maendeleo ya baadaye ili kuandika programu za C zenye ufanisi zaidi.