Ātrās šķirošanas metode C un Java valodā: pilnīga rokasgrāmata

Informatec Digital » Algoritmi » Ātrās šķirošanas metode C un Java valodā: pilnīga rokasgrāmata

Programmēšanas pasaulē kārtošanas algoritmiem ir būtiska loma. Viens no visefektīvākajiem un visplašāk izmantotajiem algoritmiem ir Quicksort. Šis algoritms, kas pazīstams ar savu ātrumu un efektivitāti elementu kārtošanā, var tikt ieviests vairākās programmēšanas valodās, tostarp C un Java. Šajā visaptverošajā rokasgrāmatā mēs detalizēti izpētīsim Quicksort C un Java valodās, analizējot tā darbību, ieviešanu un galvenās funkcijas. Pievienojieties mums šajā aizraujošajā ceļojumā cauri Quicksort algoritmam un atklājiet, kā jūs varat to pielietot savos programmēšanas projektos.

Kas ir ātrās šķirošanas metode?

Ātrā kārtošana (Quicksort), kas pazīstama arī kā ātrā kārtošana (quicksort), ir efektīvs kārtošanas algoritms , kas izmanto “skaldi un valdi” metodi. To 1959. gadā izstrādāja britu datorzinātnieks sers Tonijs Hoārs, un kopš tā laika tas ir kļuvis par vienu no visplašāk izmantotajiem un pētītajiem kārtošanas algoritmiem programmēšanā.

Ātrās kārtošanas algoritms ir balstīts uz principu, ka no saraksta tiek atlasīts kārtojamais šarnīra elements un atlikušie elementi tiek sadalīti divās grupās: tie, kas ir mazāki vai vienādi ar šarnīru, un tie, kas ir lielāki par šarnīru. Pēc tam tas pats process tiek rekursīvi piemērots katrai no divām ģenerētajām grupām, līdz visi elementi ir sakārtoti.

Ātrās šķirošanas metode C

C programmēšanas valoda tiek plaši izmantota algoritmu ieviešanai, pateicoties tās efektivitātei un zema līmeņa kontrolei pār aparatūru. Zemāk mēs sniegsim pakāpenisku Quicksort metodes ieviešanu C valodā:

1. darbība: rakursa izvēle

Pirmkārt, no saraksta ir jāatlasa pagrieziena vienums. Ir dažādas pieejas šarnīra izvēlei, taču izplatīta ir pirmā elementa atlase sarakstā.

2. darbība: sadalīšana

Kad rakurs ir atlasīts, saraksts ir jāsadala divās grupās: elementi, kas ir mazāki vai vienādi ar rakursu, un elementi, kas ir lielāki par rakurpunktu. Lai to paveiktu, tiek izmantots kreisais rādītājs un labais rādītājs, lai virzītos uz saraksta centru, līdz tiek atrasti elementi, kas jāmaina.

3. solis: rekursija

Pēc sadalīšanas tas pats process tiek rekursīvi piemērots katrai no divām ģenerētajām grupām. Tas nozīmē, ka katrā grupā tiek atlasīts jauns pagrieziena punkts un tiek veikta sadalīšana vēlreiz, līdz visi elementi ir sakārtoti.

4. darbība: kombinācija

Visbeidzot, grupas tiek apvienotas vienā pasūtītā izkārtojumā. Šajā brīdī visi elementi, kas ir mazāki vai vienādi ar šarnīra punktu, būs pa kreisi no tā, bet visi elementi, kas ir lielāki par to, būs pa labi no tā.

Tālāk ir parādīts Quicksort metodes ieviešanas piemērs 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;
}

Šis kods ievieš Quicksort metodi C valodā, izmantojot rekursijas paņēmienu. Palaižot programmu, ievades masīvs tiks sakārtots un rezultāts tiks izdrukāts.

Ātrās šķirošanas metode Java

Java ir vēl viena plaši izmantota programmēšanas valoda, kas ir piemērota arī Quicksort metodes efektīvai ieviešanai. Tālāk mēs parādīsim soli pa solim Quicksort metodes ieviešanu Java:

1. darbība: rakursa izvēle

Tāpat kā C ieviešanā, arī Java mums no saraksta jāizvēlas pagrieziena elements. Mēs varam izvēlēties pirmo elementu, pēdējo elementu vai pat nejaušu elementu kā pivot.

2. darbība: sadalīšana

Kad rakurs ir atlasīts, saraksts ir jāsadala divās grupās, tāpat kā C implementācijā. Mēs izmantosim divus rādītājus, no kuriem viens sākas saraksta sākumā un otrs beigās, un pārvietosim tos uz centru, līdz tie atradīs elementus, kas ir jāapmaina.

3. solis: rekursija

Pēc sadalīšanas tas pats process tiek rekursīvi piemērots katrai no divām ģenerētajām grupām. To panāk, katrai grupai vēlreiz izsaucot Quicksort metodi, līdz visi elementi ir sakārtoti.

4. darbība: kombinācija

Visbeidzot, grupas tiek apvienotas vienā sakārtotā masīvā, tāpat kā C ieviešanā.

Tālāk ir sniegts Java Quicksort metodes ieviešanas piemērs:

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] + " ");
        }
    }
}

Līdzīgi kā C ieviešanā, šis kods ievieš Quicksort metodi Java, izmantojot rekursiju. Palaižot programmu, ievades masīvs tiks sakārtots un rezultāts tiks izdrukāts.

Bieži uzdotie jautājumi

1. Kāda ir Quicksort metodes sarežģītība? Quicksort metodes vidējā sarežģītība ir O(n log n) vidējā gadījumā un O(n^2) sliktākajā gadījumā, kur "n" ir kārtojamā masīva lielums. Tomēr, pateicoties tās efektivitātei un labai veiktspējai vairumā gadījumu, Quicksort joprojām tiek plaši izmantota.

2. Kā Quicksort metodē izvēlēties labāko rakurspunktu? Rakurspunkta izvēle var ietekmēt algoritma veiktspēju. Izplatīta stratēģija ir izvēlēties masīva vidējo elementu kā rakurspunktu, lai vienmērīgāk sadalītu elementus. Vēl viena iespēja ir atlasīt trīs elementus un izmantot to mediānu kā rakurspunktu.

3. Kad man vajadzētu izmantot Quicksort, nevis citus kārtošanas algoritmus? Quicksort ir lieliska izvēle, ja vēlaties efektīvu kārtošanas algoritmu un jums ir pietiekami daudz atmiņas. Tomēr, ja atmiņa ir ierobežota vai ja jums ir nepieciešams stabils algoritms (tāds, kas saglabā identisku elementu relatīvo secību), varat apsvērt citus algoritmus, piemēram, mergesort.

4. Kas notiek, ja kārtojamajā masīvā ir atkārtoti elementi? Ātrās kārtošanas metode var bez problēmām apstrādāt masīvus ar atkārtotiem elementiem. Tomēr sliktākajā gadījumā, kad visi elementi ir vienādi, sadalīšana var nebūt taisnīga, un tas var ietekmēt algoritma veiktspēju.

5. Vai Quicksort metodi ir iespējams ieviest iteratīvi, nevis rekursīvi? Jā, Quicksort metodi ir iespējams ieviest iteratīvi, izmantojot datu struktūru, ko sauc par steku. Biežāk tiek izmantota rekursīvā versija, taču iteratīvā versija var būt vēlamāka noteiktos gadījumos, kad vēlaties izvairīties no rekursijas radītajām papildu izmaksām.

6. Vai Quicksort metode ir stabila? Nē, Quicksort metode nav stabila, kas nozīmē, ka tā ne vienmēr saglabā identisku elementu relatīvo secību. Ja ir nepieciešams stabils algoritms, jāapsver citas iespējas, piemēram, mergesort.

Secinājums

Noslēgumā jāsaka, ka Quicksort ir efektīvs un plaši izmantots kārtošanas algoritms programmēšanā. Šajā rokasgrāmatā mēs esam detalizēti izpētījuši, kā tas darbojas un kā to ieviest C un Java programmēšanas valodās. Quicksort izmanto “skaldi un valdi” tehniku, atlasot pagrieziena punktu un sadalot atlikušos elementus divās grupās. Izmantojot rekursiju, grupas tiek kārtotas, līdz tiek iegūts galīgais sakārtotais masīvs.

Ir svarīgi ņemt vērā Quicksort funkcijas un apsvērumus, piemēram, rakursa atlasi un atkārtotu elementu apstrādi. Turklāt ir jāizvērtē citas šķirošanas algoritmu iespējas, pamatojoties uz konkrētajām projekta vajadzībām.

Mēs ceram, ka šī visaptverošā rokasgrāmata par Quicksort metodi C un Java ir devusi jums stabilu izpratni un iedvesmojusi jūs izmantot šo efektīvo algoritmu savos programmēšanas projektos!