C-keele qsort funktsioon: kiire ja paindlik massiivi sorteerimine praktiliste näidetega

1. qsort funktsiooni ülevaade

C-keele standardraamatukogus pakutav qsort funktsioon on võimas tööriist massiivis olevate elementide sorteerimiseks. qsort kasutab kiiret QuickSort algoritmi, mis võimaldab andmeid kiiresti ümber järjestada ja on väga efektiivne. Selles jaotises selgitame qsort põhitoimimist ning miks see funktsioon on oluline.

Mis on qsort?

qsort on üldotstarbeline funktsioon, mis sorteerib massiive ja loendeid kasutaja määratud võrdlusfunktsiooni põhjal. See on C-keele standardfunktsioon ja seda kasutatakse laialdaselt paljudes arendusprojektides. Näiteks saab efektiivselt sorteerida täisarvude, stringide või isegi struktuuride massiive.

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

Ülaltoodud kood on lihtne näide, kuidas sorteerida täisarvumassiivi, kasutades qsort. Siin kasutatakse võrdlusfunktsiooni, et määrata, millises järjestuses elemendid paiknevad.

2. qsort-i argumendid ja kasutamine

qsort prototüüp on järgmine:

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

Argumentide selgitus

1. base: Sorteeritava massiivi alguspointer.
2. num: Massiivi elementide arv.
3. size: Iga elemendi suurus (baitides).
4. compar: Võrdlusfunktsiooni pointer.

See funktsioon sorteerib elemendid võrdlusfunktsiooni alusel. compar võtab argumendiks kaks elementi ning tagastab väärtuse, mis näitab, kumb on suurem. See paindlikkus võimaldab sorteerida erinevaid andmetüüpe.

Võrdlusfunktsiooni loomine

Võrdlusfunktsioon on qsort-i töö keskne osa. Järgnevalt on näidatud, kuidas määratleda funktsioon elementide võrdlemiseks.

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

See funktsioon võrdleb a ja b väärtusi ning tagastab negatiivse väärtuse, kui a on väiksem, nulli kui võrdsed ja positiivse väärtuse, kui a on suurem. Nii saab qsort sorteerida massiivi kasvavas järjekorras.

3. qsort-i sisemine töö: QuickSort algoritm

qsort kasutab sisemiselt QuickSort algoritmi. QuickSort on jagamis- ja valitsemisstrateegiat kasutav algoritm, mis toimib järgmiselt:

1. Pivot’i valik: Valitakse keskne või viimane element massiivist kui pivot.
2. Jagamine: Elemendid, mis on pivotist väiksemad, viiakse vasakule; suuremad paremale.
3. Rekursiivne sorteerimine: Mõlemat osa töödeldakse rekursiivselt sama meetodiga.

Korduva jagamise ja liitmise tulemusel sorteeritakse massiiv väga efektiivselt. QuickSorti keskmine arvutuskeerukus on O(n log n), mis teeb selle väga kiireks võrreldes paljude teiste sorteerimisalgoritmidega. Kuid halvemal juhul (nt juba sorteeritud massiiv) võib keerukus olla O(n^2), millele tasub tähelepanu pöörata.

4. Võrdlusfunktsioonide loomine erinevatele andmetüüpidele

qsort eeliseks on võimalus luua kohandatud võrdlusfunktsioone erinevate andmetüüpide jaoks. Allpool on toodud näiteid erinevat tüüpi võrdlusfunktsioonidest.

Täisarvude võrdlusfunktsioon

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

Stringide võrdlusfunktsioon

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

Struktuuride võrdlusfunktsioon

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

Nii saab qsort abil paindlikult sorteerida massiivi sisu vastavalt soovitud kriteeriumile.

5. Struktuurimassiivi sorteerimine qsort-iga

Ka struktuuride massiivi sorteerimiseks on qsort väga tõhus. Näiteks saab allolevas näites Person struktuuride massiivi sorteerida id välja alusel.

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

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

Kasutades compare_person funktsiooni, saab sorteerida massiivi järjekorda Alice, Bob, Charlie, vastavalt nende id väärtustele.

6. Jõudluse optimeerimine ja võrdlus teiste algoritmidega

QuickSorti jõudlus

QuickSort on väga efektiivne juhuslike andmete korral ja selle keskmine keerukus on O(n log n). Kui aga massiiv on juba sorteeritud, võib tekkida halvim juhtum O(n^2) keerukusega. Seetõttu on juhuslike andmestike korral QuickSort soovitatav, kuid mõnel juhul võiks kaaluda ka teisi algoritme.

Võrdlus HeapSortiga

HeapSort pakub stabiilsemat jõudlust, säilitades alati O(n log n) keerukuse, mis teeb selle sobivaks juhtudel, kus on oluline vältida halbu juhtumeid. Kuid enamasti on QuickSort keskmiselt kiirem.

Võrdlus MergeSortiga

MergeSort on samuti stabiilne O(n log n) keerukusega sorteerimisalgoritm ning sobib hästi, kui on oluline säilitada samade väärtuste esialgne järjekord. QuickSort ei taga stabiilsust, kuid enamikul juhtudel see praktiliselt probleeme ei põhjusta.

7. Kokkuvõte

qsort on võimas C-keeles pakutav sorteerimisfunktsioon, mis on paindlik ja kiire ning seetõttu väga laialdaselt kasutatav. Kohandatud võrdlusfunktsioonide abil saab sorteerida erinevat tüüpi andmeid ja struktuure, mistõttu on see väga praktiline tööriist.

Kui mõista QuickSort algoritmi põhimõtteid, saab qsort funktsiooni kasutada maksimaalse tõhususega. Sõltuvalt andmestikust või tingimustest võib olla mõistlik võrrelda ka HeapSorti või MergeSorti kasutamist, et saavutada parim jõudlus.

Soovitame kasutada qsort funktsiooni tulevaste arendusprojektide raames ning katsetada selle võimalusi, et kirjutada efektiivsemaid programme.