I-Quicksort Method ku-C ne-Java: Umhlahlandlela ophelele

Informatec Digital » Ama-algorithms » I-Quicksort Method ku-C ne-Java: Umhlahlandlela ophelele

Ezweni lokuhlela, ama-algorithm okuhlunga adlala indima ebalulekile. Phakathi kwama-algorithm asebenza kahle futhi asetshenziswa kabanzi yi-Quicksort. Le algorithm, eyaziwa ngesivinini sayo kanye nokusebenza kahle ekuhleleni izakhi, ingasetshenziswa ngezilimi eziningana zokuhlela, okuhlanganisa i-C ne-Java. Kulo mhlahlandlela ophelele, sizohlola i-Quicksort ku-C kanye ne-Java ngokuningiliziwe, sihlaziye ukusebenza kwayo, ukusetshenziswa kwayo, kanye nezici ezibalulekile. Joyina nathi kulolu hambo oluthakazelisayo nge- algorithm ye-Quicksort bese uthola ukuthi ungayisebenzisa kanjani kumaphrojekthi akho okuhlela.

Ithini i-Quicksort Method?

I-Quicksort, eyaziwa nangokuthi i-quicksort, iyi- algorithm yokuhlunga esebenza kahle esebenzisa indlela yokuhlukanisa nokunqoba. Yasungulwa usosayensi wekhompyutha waseBrithani uSir Tony Hoare ngo-1959 futhi kusukela lapho ibe ngenye yama-algorithm okuhlunga asetshenziswa kakhulu futhi afundwe kakhulu ekuhleleni izinhlelo.

I -algorithm ye-Quicksort isekelwe esimisweni sokukhetha isici se-pivot ohlwini okufanele sihlungwe bese uhlukanisa izinto ezisele zibe amaqembu amabili: lezo ezingaphansi noma ezilingana ne-pivot, kanye nalezo ezinkulu kune-pivot. Bese, inqubo efanayo isetshenziswa ngokuphindaphindiwe eqenjini ngalinye lalawa amabili akhiqizwe, kuze kube yilapho zonke izinto sezihlungiwe.

Indlela ye-Quicksort ku-C

Ulimi lokuhlela lwe-C lusetshenziswa kabanzi ekusebenziseni ama-algorithm ngenxa yokusebenza kahle kwalo kanye nokulawula okuphansi kwehadiwe. Ngezansi, sizokwethula ukusetshenziswa kwesinyathelo ngesinyathelo kwendlela ye-Quicksort ku-C:

Isinyathelo 1: Ukukhetha i-pivot

Okokuqala, into ye-pivot kufanele ikhethwe ohlwini. Kunezindlela ezihlukene zokukhetha i-pivot, kodwa evamile ukukhetha into yokuqala ohlwini.

Isinyathelo sesi-2: Ukuhlukanisa

Uma i-pivot isikhethiwe, uhlu kufanele luhlukaniswe ngamaqembu amabili: ama-elementi angaphansi noma alingana ne-pivot nama-elementi amakhulu kune-pivot. Ukufeza lokhu, i-pointer yesokunxele kanye nesikhombi esingakwesokudla kusetshenziswa ukuya phakathi nendawo yohlu kuze kube yilapho zithola izici ezidinga ukushintshwa.

Isinyathelo sesi-3: Ukuphindaphinda

Ngemuva kokuthi ukuhlukaniswa kwenziwe, inqubo efanayo isetshenziswa ngokuphindaphindiwe kuqembu ngalinye kulawa amabili akhiqiziwe. Okusho ukuthi, i-pivot entsha ikhethwa eqenjini ngalinye futhi ukwahlukanisa kwenziwa futhi kuze kuhlungwe zonke izici.

Isinyathelo sesi-4: Inhlanganisela

Ekugcineni, amaqembu ahlanganiswa abe ilungiselelo elilodwa eli-oda. Kuleli qophelo, zonke izici ezingaphansi noma ezilingana ne-pivot zizoba kwesokunxele sayo, kuyilapho ama-elementi amakhulu kunalokho azoba kwesokudla kuyo.

Ngezansi isibonelo sokuqaliswa kwendlela ye-Quicksort ku-C:

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[low];
    int i = low + 1;
    int j = high;

    while (1) {
        while (arr[i] < pivot && i <= j)
            i++;

        while (arr[j] > pivot)
            j--;

        if (i >= j)
            break;

        swap(&arr[i], &arr[j]);
    }

    swap(&arr[low], &arr[j]);

    return j;
}

void quicksort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quicksort(arr, low, pivot - 1);
        quicksort(arr, pivot + 1, high);
    }
}

int main() {
    int arr[] = {5, 2, 9, 1, 7, 6, 8, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    quicksort(arr, 0, n - 1);

    printf("Arreglo ordenado: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

Le khodi isebenzisa indlela ye-Quicksort ku-C isebenzisa indlela yokuphindaphinda. Uma uqalisa uhlelo, uhlelo lokokufaka luzohlungwa futhi umphumela uzophrintwa.

Indlela ye-Quicksort ku-Java

I-Java ingolunye ulimi lokuhlela olusetshenziswa kakhulu futhi olulungele ukusebenzisa indlela ye-Quicksort ngempumelelo. Okulandelayo, sizobonisa ukuqaliswa kwesinyathelo ngesinyathelo sendlela ye-Quicksort ku-Java:

Isinyathelo 1: Ukukhetha i-pivot

Njengasekusetshenzisweni kwe-C, naku-Java nathi sidinga ukukhetha isici se-pivot ohlwini. Singakhetha i-elementi yokuqala, i-elementi yokugcina noma i-elementi engahleliwe njenge-pivot.

Isinyathelo sesi-2: Ukuhlukanisa

Uma i-pivot isikhethiwe, uhlu kufanele luhlukaniswe ngamaqembu amabili, njengasekusetshenzisweni kuka-C Sizosebenzisa ama-indices amabili, eyodwa iqala ekuqaleni kohlu neyodwa ekugcineni, futhi siziyise phakathi nendawo kuze kube yilapho zithola izici ezidinga ukushintshwa.

Isinyathelo sesi-3: Ukuphindaphinda

Ngemuva kokuthi ukuhlukaniswa kwenziwe, inqubo efanayo isetshenziswa ngokuphindaphindiwe kuqembu ngalinye kulawa amabili akhiqiziwe. Lokhu kufezwa ngokubiza indlela ye-Quicksort futhi eqenjini ngalinye kuze kube yilapho zonke izici zihlungwa.

Isinyathelo sesi-4: Inhlanganisela

Ekugcineni, amaqembu ahlanganiswa abe yilungu elilodwa elihlungiwe, njengasekusetshenzisweni kuka-C.

Ngezansi isibonelo sokuqaliswa kwendlela ye-Quicksort ku-Java:

public class Quicksort {
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        int i = low + 1;
        int j = high;

        while (true) {
            while (i <= j && arr[i] < pivot)
                i++;

            while (arr[j] > pivot)
                j--;

            if (i >= j)
                break;

            swap(arr, i, j);
        }

        swap(arr, low, j);

        return j;
    }

    public static void quicksort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);
            quicksort(arr, low, pivot - 1);
            quicksort(arr, pivot + 1, high);
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 7, 6, 8, 3, 4};
        int n = arr.length;

        quicksort(arr, 0, n - 1);

        System.out.print("Arreglo ordenado: ");
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Ngokufanayo nokuqaliswa kwe-C, le khodi isebenzisa indlela ye-Quicksort ku-Java isebenzisa ukuphindaphinda. Uma uqalisa uhlelo, uhlelo lokokufaka luzohlungwa futhi umphumela uzophrintwa.

Imibuzo ebuzwa njalo

1. Iyini inkimbinkimbi yendlela ye-Quicksort? Indlela ye-Quicksort inobunkimbinkimbi obumaphakathi be-O(n log n) esimweni esimaphakathi kanye ne-O(n^2) esimweni esibi kakhulu, lapho u-"n" engusayizi we-array okufanele ihlungwe. Kodwa-ke, ngenxa yokusebenza kwayo kahle kanye nokusebenza kahle ezimweni eziningi, i-Quicksort isasetshenziswa kabanzi.

2. Ngingayikhetha kanjani i-pivot engcono kakhulu endleleni ye-Quicksort? Ukukhetha i-pivot kungathinta ukusebenza kwe-algorithm. Isu elivamile ukukhetha isici esiphakathi se-array njenge-pivot ukuze kusatshalaliswe izakhi ngokulinganayo. Enye inketho ukukhetha izakhi ezintathu bese usebenzisa i-median yazo njenge-pivot.

3. Kufanele ngisebenzise nini i-Quicksort esikhundleni sezinye izindlela zokuhlunga? I-Quicksort iyisinqumo esihle kakhulu uma ufuna i-algorithm yokuhlunga esebenza kahle futhi unememori eyanele etholakalayo. Kodwa-ke, uma imemori ilinganiselwe noma uma udinga i-algorithm ezinzile (egcina ukuhleleka okuhlobene kwezinto ezifanayo), ungacabanga ngezinye izindlela zokuhlunga ezifana ne -mergesort.

4. Kwenzekani uma uhlu oluzohlungwa luqukethe izinto eziphindaphindwayo? Indlela ye-Quicksort ingaphatha uhlu olunezakhi eziphindaphindwayo ngaphandle kwezinkinga. Kodwa-ke, esimweni esibi kakhulu, lapho zonke izakhi zifana, ukwahlukanisa kungase kungabi kuhle, futhi lokhu kungathinta ukusebenza kwe-algorithm.

5. Kungenzeka yini ukusebenzisa indlela ye-Quicksort ngokuphindaphindiwe esikhundleni sokuyiphinda? Yebo, kungenzeka ukusebenzisa indlela ye-Quicksort ngokuphindaphindiwe usebenzisa isakhiwo sedatha esibizwa ngokuthi i-stack. Inguqulo ye-recursive ivame ukusetshenziswa, kodwa inguqulo ye-reterative ingase ibe ngcono ezimweni ezithile lapho ufuna ukugwema khona imali engaphezulu ye-recursion.

6. Ingabe indlela ye-Quicksort izinzile? Cha, indlela ye-Quicksort ayizinzile, okusho ukuthi ayigcini ukuhleleka okuhlobene kwezinto ezifanayo. Uma kudingeka i-algorithm ezinzile, ezinye izinketho ezifana ne-mergesort kufanele zicatshangelwe.

Isiphetho

Ekuphetheni, i-Quicksort iyi- algorithm yokuhlunga esebenza kahle futhi esetshenziswa kabanzi ekuhleleni izinhlelo. Kuyo yonke le mhlahlandlela, sihlole ngokuningiliziwe ukuthi isebenza kanjani nokuthi singayisebenzisa kanjani ezilimini zokuhlela ze-C ne-Java. I-Quicksort isebenzisa indlela yokuhlukanisa nokunqoba, ikhetha i-pivot bese ihlukanisa izinto ezisele zibe amaqembu amabili. Ngokuphindaphindwa, amaqembu ahlelwa kuze kube yilapho kutholakala uhlu lokugcina oluhleliwe.

Kubalulekile ukuqaphela izici nokucatshangelwa kwe-Quicksort, njengokukhethwa kwe-pivot nokuphatha izinto eziphindaphindiwe. Ukwengeza, ezinye izinketho zokuhlunga ze-algorithm kufanele zihlolwe ngokusekelwe ezidingweni ezithile zephrojekthi.

Sithemba ukuthi lo mhlahlandlela ophelele wendlela ye-Quicksort ku-C ne-Java ukunikeze ukuqonda okuqinile futhi wakugqugquzele ukuthi usebenzise le-algorithm ephumelelayo kumaphrojekthi akho wokuhlela!