Burbulų rūšiavimo algoritmas C, Java ir Python

Informatec Digital » Algoritmai » Burbulų rūšiavimo algoritmas C, Java ir Python

Burbulų rūšiavimo algoritmas yra vienas iš paprasčiausių ir pagrindinių algoritmų, naudojamų sąrašo elementams rūšiuoti. Dėl savo paprastumo jis yra puikus pasirinkimas norint suprasti pagrindines rūšiavimo algoritmų sąvokas. Šis algoritmas dažniausiai naudojamas programose ir programose, kuriose rūšiuojamų elementų skaičius yra mažas.

Šiame straipsnyje daugiausia dėmesio skirsime burbulinio rūšiavimo algoritmo įgyvendinimui dviejose populiariose programavimo kalbose: C ir Java. Išnagrinėsime veiksmus, reikalingus šiam algoritmui įdiegti kiekvienoje iš šių kalbų, analizuosime šaltinio kodą ir pateiksime išsamius paaiškinimus.

Burbulų rūšiavimo algoritmas C ir Java

Burbulų rūšiavimo algoritmas, kaip rodo pavadinimas, veikia lygindamas gretimų sąrašo elementų poras ir atlikdamas apsikeitimus, jei jie yra neteisinga tvarka. Šis procesas kartojamas tol, kol sąrašas bus visiškai surūšiuotas.

Kaip burbulų rūšiavimo algoritmas veikia C ir Java?

Burbulų rūšiavimo algoritmas vadovaujasi paprastu, bet veiksmingu elementų rūšiavimo metodu. Bendras algoritmo veikimas parodytas žemiau:

1. Pradedame nuo netvarkingo prekių sąrašo.
2. Pakartojame sąrašą, lygindami kiekvieną gretimų elementų porą.
3. Jei elementai yra neteisinga tvarka, mes juos sukeičiame.
4. Toliau kartojame sąrašą, kol jis bus visiškai surūšiuotas.
5. Iteracijos procesas kartojamas tiek kartų, kiek reikia, kol per visą eigą nebebus atliekami apsikeitimai.

Burbulų rūšiavimo algoritmo įgyvendinimas C

Žemiau pateikiame burbulinio rūšiavimo algoritmo įgyvendinimą C kalba :

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

Šiame burbulo algoritmo kode apibrėžėme funkciją, vadinamą bubbleSort kuris kaip parametrus paima masyvą ir jo dydį. Funkcija atlieka burbulų rūšiavimo algoritmą naudodama dvi kilpas for. Pirmoji kilpa for kartojasi per masyvo elementus ir antrąją kilpą for atlikti reikiamus palyginimus ir pasikeitimus.

Galiausiai, funkcijoje main, sukūrėme pavyzdinį masyvą ir apskaičiavome jo dydį. Tada vadiname funkciją bubbleSort perduodamas masyvą ir jo dydį kaip argumentus. Galiausiai surūšiuotą masyvą atspausdiname ekrane.

Burbulų rūšiavimo algoritmo įdiegimas Java programoje

Žemiau pristatome burbulų rūšiavimo algoritmo įgyvendinimą Java kalba:

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

Šiame kode mes apibrėžėme klasę, vadinamą BubbleSort. Šioje klasėje paskelbėme statinį metodą, vadinamą bubbleSort kuris imasi masyvo kaip parametro. Metodas bubbleSort atlieka burbulų rūšiavimo algoritmą naudodamas dvi kilpas for, kaip ir C įgyvendinime.

Metodoje main, sukūrėme pavyzdinį masyvą ir pavadinome metodą bubbleSort masyvo perdavimas kaip argumentas. Galiausiai naudojame Arrays.toString(array) norėdami atspausdinti surūšiuotą masyvą į konsolę.

Burbulų rūšiavimo algoritmo įgyvendinimas Python

Python burbulų rūšiavimo algoritmo atitikmuo:

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)

 

Burbulų rūšiavimo algoritmo privalumai

Burbulų rūšiavimo algoritmas turi keletą privalumų, tokių kaip:

1. Paprastumas: burbulų rūšiavimo algoritmą lengva suprasti ir įgyvendinti. Tai nereikalauja sudėtingų žinių ir tinka pradedantiesiems programuoti.
2. Žemas kodo sudėtingumas: Kodas, reikalingas burbulų rūšiavimo algoritmui įgyvendinti, yra gana trumpas ir glaustas. Tai leidžia greitai surūšiuoti nedidelį elementų skaičių.

Burbulų rūšiavimo algoritmo trūkumai

Nepaisant savo paprastumo, burbulų rūšiavimo algoritmas taip pat turi tam tikrų trūkumų:

1. Didelių duomenų rinkinių neefektyvumas: Burbulų rūšiavimo algoritmas nėra efektyvus vykdymo laiko atžvilgiu, kai dirbama su dideliais duomenų rinkiniais. Jo laiko sudėtingumas yra O(n^2), o tai reiškia, kad vykdymo laikas sparčiai didėja didėjant duomenų rinkinio dydžiui.
2. Palyginimų skaičius: burbulų rūšiavimo algoritmas atlieka daug palyginimų, net kai masyvas jau surūšiuotas. Tai gali lemti bereikalingą našumo ir išteklių praradimą.

Burbulų rūšiavimo algoritmo alternatyvos

Kadangi duomenų rinkiniai tampa didesni ir sudėtingesni, svarbu apsvarstyti veiksmingesnes burbulų rūšiavimo algoritmo alternatyvas. Kai kurios populiarios alternatyvos apima:

1. Įterpimo rūšiavimo algoritmas: Šis algoritmas padalija sąrašą į užsakytą ir netvarkingą dalį ir įterpia kiekvieną netvarkingos dalies elementą į teisingą vietą užsakytoje dalyje. Blogiausiu atveju jo sudėtingumas yra O(n^2), tačiau daugeliu atvejų yra efektyvesnis nei burbulų rūšiavimo algoritmas.
2. Pasirinkimo rūšiavimo algoritmas: Šis algoritmas padalija sąrašą į užsakytą ir netvarkingą dalį bei pakartotinai pasirenka mažiausią elementą iš netvarkingos dalies ir deda jį į užsakytos dalies pabaigą. Blogiausiu atveju jo sudėtingumas yra O(n^2), tačiau daugeliu atvejų yra efektyvesnis nei burbulų rūšiavimo algoritmas.

Bubble Algorithm DUK

1. Koks yra burbulų rūšiavimo algoritmo laiko sudėtingumas?

Burbulų rūšiavimo algoritmo laiko sudėtingumas yra O(n^2), kur „n“ yra rūšiuojamų elementų skaičius. Tai reiškia, kad didėjant sąrašo dydžiui, algoritmo veikimo laikas didėja kvadratiškai.

2. Kada tikslinga naudoti burbulų rūšiavimo algoritmą?

Burbulų rūšiavimo algoritmas tinka, kai rūšiuojamų elementų sąrašas yra mažas. Dėl laiko sudėtingumo jo nerekomenduojama naudoti dideliems duomenų rinkiniams, nes yra efektyvesnių algoritmų.

3. Ar burbulų rūšiavimo algoritmas yra stabilus?

Taip, burbulų rūšiavimo algoritmas yra stabilus rūšiavimo algoritmas. Tai reiškia, kad rūšiavimo proceso metu ji palaiko santykinę elementų tvarką su vienodais raktais.

4. Kokia yra geriausia burbulų rūšiavimo algoritmo alternatyva?

Geriausios burbulinio rūšiavimo algoritmo alternatyvos pasirinkimas priklauso nuo konteksto ir konkrečių problemos reikalavimų. Tačiau dėl mažesnio laiko sudėtingumo plačiai naudojami kai kurie efektyvesni algoritmai, tokie kaip „quicksort“ ir „mergesort“.

5. Ar galima patobulinti burbulų rūšiavimo algoritmą?

Taip, yra burbulų rūšiavimo algoritmo variantų ir optimizacijų, tokių kaip „dvikryptis burbulų rūšiavimas“ ir „patobulintas burbulų rūšiavimas“. Šie optimizavimai sumažina palyginimų skaičių ir pakartojimų, reikalingų sąrašui rūšiuoti, skaičių.

6. Kur galiu rasti daugiau informacijos apie rūšiavimo algoritmus?

Daugiau informacijos apie rūšiavimo algoritmus galite rasti patikimuose šaltiniuose, pvz., Vikipedijoje. Štai keletas naudingų nuorodų:

• Rūšiavimo algoritmai Vikipedijoje
• Burbulų rūšiavimas Vikipedijoje

Išvada

Šiame straipsnyje mes ištyrėme burbulų rūšiavimo algoritmą C ir Java programavimo kalbomis. Žingsnis po žingsnio sužinojome, kaip veikia šis algoritmas, ir matėme jo praktinį įgyvendinimą abiem kalbomis. Taip pat aptarėme burbulų rūšiavimo algoritmo privalumus ir trūkumus bei ištyrėme efektyvesnes alternatyvas.

Nors burbulų rūšiavimo algoritmas yra paprastas ir lengvai įgyvendinamas, svarbu atsižvelgti į jo efektyvumą didesniuose duomenų rinkiniuose. Tokiais atvejais patartina apsvarstyti efektyvesnius rūšiavimo algoritmus, tokius kaip įterpimo rūšiavimas arba pasirinkimo rūšiavimas.

Tikimės, kad šis straipsnis padėjo jums gerai suprasti burbulų rūšiavimo algoritmą.