Bubble Sort Algoritme i C, Java og Python

Informatec Digital » Algoritmer » Boblesorteringsalgoritme i C, Java og Python

Boblesorteringsalgoritme er en av de enkleste og mest grunnleggende algoritmene som brukes til å sortere elementer i en liste. Dens enkelhet gjør den til et utmerket valg for å forstå de grunnleggende konseptene for sorteringsalgoritmer. Denne algoritmen brukes ofte i applikasjoner og programmer der antallet elementer som skal sorteres er lite.

I denne artikkelen skal vi fokusere på å implementere boblesorteringsalgoritmen i to populære programmeringsspråk: C og Java. Vi skal utforske trinnene som er nødvendige for å implementere denne algoritmen i hvert av disse språkene, analysere kildekoden og gi detaljerte forklaringer.

Bubble Sort Algoritme i C og Java

Boblesorteringsalgoritmen, som navnet antyder, fungerer ved å sammenligne par av tilstøtende elementer i en liste og utføre bytte hvis de er i feil rekkefølge. Denne prosessen gjentas til listen er fullstendig sortert.

Hvordan fungerer boblesorteringsalgoritmen i C og Java?

Algoritmen for boblesortering følger en enkel, men effektiv tilnærming til sortering av elementer. Den generelle operasjonen til algoritmen er vist nedenfor:

1. Vi starter med en uordnet liste over varer.
2. Vi itererer gjennom listen, og sammenligner hvert par av tilstøtende elementer.
3. Hvis elementene er i feil rekkefølge, bytter vi dem.
4. Vi fortsetter å iterere over listen til den er helt sortert.
5. Iterasjonsprosessen gjentas så mange ganger som nødvendig inntil det ikke foretas flere bytter i en fullstendig pass.

Implementering av boblesorteringsalgoritme i C

Nedenfor presenterer vi implementeringen av boblesorteringsalgoritmen i C-språket :

#include <stdio.h>

void bubbleSort(int array[], int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

int main() {
    int array[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(array) / sizeof(array[0]);
    bubbleSort(array, size);
    printf("Array ordenado: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    return 0;
}

I denne boblealgoritmekoden har vi definert en funksjon kalt bubbleSort som tar en matrise og dens størrelse som parametere. Funksjonen utfører boblesorteringsalgoritmen ved hjelp av to løkker for. Den første løkken for itererer over elementene i matrisen, og den andre sløyfen for foreta de nødvendige sammenligningene og utvekslingene.

Til slutt, i funksjonen main, har vi laget en eksempelmatrise og beregnet størrelsen. Deretter kaller vi funksjonen bubbleSort sende matrisen og dens størrelse som argumenter. Til slutt skriver vi ut den sorterte matrisen til skjermen.

Implementering av boblesorteringsalgoritme i Java

Nedenfor presenterer vi implementeringen av boblesorteringsalgoritmen på Java-språket:

import java.util.Arrays;

public class BubbleSort {
    public static void bubbleSort(int[] array) {
        int size = array.length;
        for (int i = 0; i < size - 1; i++) {
            for (int j = 0; j < size - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(array);
        System.out.println("Array ordenado: " + Arrays.toString(array));
    }
}

I denne koden har vi definert en klasse kalt BubbleSort. Inne i denne klassen har vi erklært en statisk metode kalt bubbleSort som tar en matrise som en parameter. Metoden bubbleSort utfører boblesorteringsalgoritmen ved hjelp av to løkker for, akkurat som i C-implementeringen.

I metoden main, har vi laget en eksempelmatrise og kalt metoden bubbleSort passerer matrisen som et argument. Til slutt bruker vi Arrays.toString(array) for å skrive ut den sorterte matrisen til konsollen.

Implementering av boblesorteringsalgoritmen i Python

Ekvivalenten til Python-boblesorteringsalgoritmen:

def bubble_sort(array):
    size = len(array)
    for i in range(size - 1):
        for j in range(size - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]

array = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(array)
print("Array ordenado:", array)

 

Fordeler med boblesorteringsalgoritme

Algoritmen for boblesortering har noen fordeler, for eksempel:

1. lette: Algoritmen for boblesortering er enkel å forstå og implementere. Det krever ikke komplisert kunnskap og passer for nybegynnere innen programmering.
2. Lav kodekompleksitet: Koden som kreves for å implementere boblesorteringsalgoritmen er relativt kort og konsis. Dette gjør det til et raskt alternativ for å sortere et lite antall varer.

Ulemper med boblesorteringsalgoritme

Til tross for sin enkelhet har boblesorteringsalgoritmen også noen ulemper:

1. Ineffektivitet i store datasett: Algoritmen for boblesortering er ikke effektiv når det gjelder utførelsestid når man arbeider med store datasett. Tidskompleksiteten er O(n^2), noe som betyr at utførelsestiden øker raskt når størrelsen på datasettet øker.
2. Antall sammenligninger: Algoritmen for boblesortering utfører et stort antall sammenligninger, selv når matrisen allerede er sortert. Dette kan føre til unødvendig tap av ytelse og ressurser.

Alternativer til boblesorteringsalgoritmen

Etter hvert som datasett blir større og mer komplekse, er det viktig å vurdere mer effektive alternativer til boblesorteringsalgoritmen. Noen av de populære alternativene inkluderer:

1. Algoritme for innsettingssortering: Denne algoritmen deler listen inn i en ordnet del og en uordnet del, og setter inn hvert element i den uordnede delen i riktig posisjon innenfor den bestilte delen. Den har en tidskompleksitet på O(n^2) i verste fall, men er mer effektiv enn boblesorteringsalgoritmen i de fleste tilfeller.
2. Valgsorteringsalgoritme: Denne algoritmen deler listen inn i en ordnet del og en uordnet del, og velger gjentatte ganger det minste elementet fra den uordnede delen og plasserer det på slutten av den bestilte delen. Den har en tidskompleksitet på O(n^2) i verste fall, men er også mer effektiv enn boblesorteringsalgoritmen i de fleste tilfeller.

Vanlige spørsmål om boblealgoritmer

1. Hva er tidskompleksiteten til boblesorteringsalgoritmen?

Boblesorteringsalgoritmen har en tidskompleksitet på O(n^2), der "n" er antall elementer som skal sorteres. Dette betyr at kjøretiden til algoritmen øker kvadratisk ettersom størrelsen på listen øker.

2. Når er det hensiktsmessig å bruke boblesorteringsalgoritmen?

Algoritmen for boblesortering er egnet når listen over elementer som skal sorteres er liten. På grunn av tidskompleksiteten, anbefales det ikke for bruk på store datasett da mer effektive algoritmer er tilgjengelige.

3. Er boblesorteringsalgoritmen stabil?

Ja, boblesorteringsalgoritmen er en stabil sorteringsalgoritme. Dette betyr at den opprettholder den relative rekkefølgen av elementer med like nøkler under sorteringsprosessen.

4. Hva er det beste alternativet til boblesorteringsalgoritmen?

Valget av det beste alternativet til boblesorteringsalgoritmen avhenger av konteksten og de spesifikke kravene til problemet. Imidlertid er noen mer effektive algoritmer, som quicksort og mergesort , mye brukt på grunn av deres lavere tidskompleksitet.

5. Kan boblesorteringsalgoritmen forbedres?

Ja, det finnes varianter og optimaliseringer av boblesorteringsalgoritmen, for eksempel "toveis boblesortering" og "forbedret boblesortering". Disse optimaliseringene reduserer antall sammenligninger og antall iterasjoner som kreves for å sortere en liste.

6. Hvor finner jeg mer informasjon om sorteringsalgoritmer?

Du kan finne mer informasjon om sorteringsalgoritmer i pålitelige kilder som Wikipedia. Her er noen nyttige linker:

• Sorteringsalgoritmer i Wikipedia
• Boblesortering på Wikipedia

Konklusjon

I denne artikkelen har vi utforsket boblesorteringsalgoritmen i programmeringsspråkene C og Java. Vi har lært hvordan denne algoritmen fungerer steg for steg, og vi har sett den praktiske implementeringen på begge språk. Vi har også diskutert fordeler og ulemper med boblesorteringsalgoritmen, og utforsket mer effektive alternativer.

Selv om boblesorteringsalgoritmen er enkel og lett å implementere, er det viktig å vurdere effektiviteten på større datasett. I slike tilfeller er det tilrådelig å vurdere mer effektive sorteringsalgoritmer, som for eksempel innsettingssortering eller utvalgssortering.

Vi håper denne artikkelen har gitt deg en solid forståelse av boblesorteringsalgoritmen.