Bubble Sort Algoritme i C, Java og Python

Informatic Digital » Algoritmer » Bubble Sort Algoritme i C, Java og Python

Boblesorteringsalgoritme er en af ​​de enkleste og mest basale algoritmer, der bruges til at sortere elementer i en liste. Dens enkelhed gør det til et glimrende valg til at forstå de grundlæggende begreber for sorteringsalgoritmer. Denne algoritme bruges almindeligvis i applikationer og programmer, hvor antallet af elementer, der skal sorteres, er lille.

I denne artikel vil vi fokusere på implementeringen af ​​boblesorteringsalgoritmen i to populære programmeringssprog: C og Java. Vi vil undersøge de nødvendige trin for at implementere denne algoritme i hvert af disse sprog, analysere kildekoden og give detaljerede forklaringer.

Bubble Sort Algoritme i C og Java

Boblesorteringsalgoritmen fungerer, som navnet antyder, ved at sammenligne par af tilstødende elementer i en liste og udføre bytte, hvis de er i den forkerte rækkefølge. Denne proces gentages, indtil listen er helt sorteret.

Hvordan fungerer boblesorteringsalgoritmen i C og Java?

Boblesorteringsalgoritmen følger en enkel, men effektiv tilgang til sortering af elementer. Den generelle funktion af algoritmen er vist nedenfor:

1. Vi starter med en uordnet liste over varer.
2. Vi itererer gennem listen og sammenligner hvert par af tilstødende elementer.
3. Hvis elementerne er i den forkerte rækkefølge, bytter vi dem.
4. Vi fortsætter med at iterere over listen, indtil den er helt sorteret.
5. Iterationsprocessen gentages så mange gange som nødvendigt, indtil der ikke foretages flere swaps i en komplet gennemløb.

Implementering af boblesorteringsalgoritme i C

Nedenfor præsenterer vi implementeringen af ​​​​boblesorteringsalgoritmen i C-sproget :

#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 boblealgoritmekode har vi defineret en funktion kaldet bubbleSort som tager et array og dets størrelse som parametre. Funktionen udfører boblesorteringsalgoritmen ved hjælp af to sløjfer for. Den første sløjfe for itererer over elementerne i arrayet og den anden sløjfe for foretage de nødvendige sammenligninger og udvekslinger.

Til sidst i funktionen main, har vi oprettet et eksempel-array og beregnet dets størrelse. Så kalder vi funktionen bubbleSort sende arrayet og dets størrelse som argumenter. Til sidst udskriver vi det sorterede array til skærmen.

Implementering af boblesorteringsalgoritme i Java

Nedenfor præsenterer vi implementeringen af ​​boblesorteringsalgoritmen i Java-sproget:

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 kode har vi defineret en klasse kaldet BubbleSort. Inde i denne klasse har vi erklæret en statisk metode kaldet bubbleSort som tager et array som en parameter. Metoden bubbleSort udfører boblesorteringsalgoritmen ved hjælp af to sløjfer for, ligesom i C-implementeringen.

I metoden main, har vi lavet et eksempel-array og kaldt metoden bubbleSort passerer arrayet som et argument. Til sidst bruger vi Arrays.toString(array) for at udskrive det sorterede array til konsollen.

Implementering af boblesorteringsalgoritmen i Python

Det svarer 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)

 

Fordele ved boblesorteringsalgoritme

Boblesorteringsalgoritmen har nogle fordele, såsom:

1. lethed: Boblesorteringsalgoritmen er nem at forstå og implementere. Det kræver ikke kompliceret viden og er velegnet til begyndere inden for programmering.
2. Lav kodekompleksitet: Den nødvendige kode for at implementere boblesorteringsalgoritmen er relativt kort og kortfattet. Dette gør det til en hurtig mulighed for at sortere et lille antal varer.

Ulemper ved boblesorteringsalgoritme

På trods af sin enkelhed har boblesorteringsalgoritmen også nogle ulemper:

1. Ineffektivitet i store datasæt: Boblesorteringsalgoritme er ikke effektiv med hensyn til eksekveringstid, når der er tale om store datasæt. Dens tidskompleksitet er O(n^2), hvilket betyder, at udførelsestiden øges hurtigt, efterhånden som størrelsen af ​​datasættet øges.
2. Antal sammenligninger: Boblesorteringsalgoritmen udfører et stort antal sammenligninger, selv når arrayet allerede er sorteret. Dette kan føre til unødigt tab af ydeevne og ressourcer.

Alternativer til boblesorteringsalgoritmen

Efterhånden som datasæt bliver større og mere komplekse, er det vigtigt at overveje mere effektive alternativer til boblesorteringsalgoritmen. Nogle af de populære alternativer inkluderer:

1. Indsættelsessorteringsalgoritme: Denne algoritme opdeler listen i en ordnet del og en uordnet del og indsætter hvert element i den uordnede del i den korrekte position inden for den ordnede del. Den har en tidskompleksitet på O(n^2) i værste fald, men er i de fleste tilfælde mere effektiv end boblesorteringsalgoritmen.
2. Valgsorteringsalgoritme: Denne algoritme opdeler listen i en ordnet del og en uordnet del og vælger gentagne gange det mindste element fra den uordnede del og placerer det i slutningen af ​​den ordnede del. Den har en tidskompleksitet på O(n^2) i værste fald, men er også mere effektiv end boblesorteringsalgoritmen i de fleste tilfælde.

Ofte stillede spørgsmål om boblealgoritme

1. Hvad er tidskompleksiteten af ​​boblesorteringsalgoritme?

Boblesorteringsalgoritmen har en tidskompleksitet på O(n^2), hvor "n" er antallet af elementer, der skal sorteres. Det betyder, at køretiden for algoritmen øges kvadratisk i takt med, at listens størrelse øges.

2. Hvornår er det passende at bruge boblesorteringsalgoritmen?

Boblesorteringsalgoritmen er velegnet, når listen over elementer, der skal sorteres, er lille. På grund af dets tidskompleksitet anbefales det ikke til brug på store datasæt, da mere effektive algoritmer er tilgængelige.

3. Er boblesorteringsalgoritmen stabil?

Ja, boblesorteringsalgoritmen er en stabil sorteringsalgoritme. Det betyder, at den bevarer den relative rækkefølge af elementer med lige store nøgler under sorteringsprocessen.

4. Hvad er det bedste alternativ til boblesorteringsalgoritmen?

Valget af det bedste alternativ til boblesorteringsalgoritmen afhænger af konteksten og problemets specifikke krav. Imidlertid er nogle mere effektive algoritmer, såsom quicksort og mergesort , meget udbredte på grund af deres lavere tidskompleksitet.

5. Kan boblesorteringsalgoritmen forbedres?

Ja, der er varianter og optimeringer af boblesorteringsalgoritmen, såsom "tovejs boblesortering" og "forbedret boblesortering". Disse optimeringer reducerer antallet af sammenligninger og antallet af iterationer, der kræves for at sortere en liste.

6. Hvor kan jeg finde mere information om sorteringsalgoritmer?

Du kan finde mere information om sorteringsalgoritmer i pålidelige kilder som Wikipedia. Her er nogle nyttige links:

• Sorteringsalgoritmer i Wikipedia
• Boblesortering på Wikipedia

Konklusion

I denne artikel har vi udforsket boblesorteringsalgoritmen i programmeringssprogene C og Java. Vi har lært, hvordan denne algoritme fungerer trin for trin, og vi har set dens praktiske implementering på begge sprog. Vi har også diskuteret fordele og ulemper ved boblesorteringsalgoritmen og udforsket mere effektive alternativer.

Selvom boblesorteringsalgoritmen er enkel og nem at implementere, er det vigtigt at overveje dens effektivitet på større datasæt. I sådanne tilfælde er det tilrådeligt at overveje mere effektive sorteringsalgoritmer, såsom indsættelsessortering eller udvælgelsessortering.

Vi håber, at denne artikel har givet dig en solid forståelse af boblesorteringsalgoritmen.