Burbuļkārtošana

Apskatīsim burbuļkārtošanas algoritmu zem lupas..

Izpēti doto konstrukciju cikls ciklā! Iedarbini algoritmu kādā koda redaktorā un novērtē rezultātu!

for i in range(5):
    for j in range(5):
        print(i, j)

To var pielīdzināt skriešanai pa stadionu, kur skrējēji drīkst skriet 5 apļus tikai pa vienam. Kad noskrējis pirmais skrējējs, sāk nākamais un tā uz priekšu...

🔄️ Swap algoritms

Tā kā burbuļkārtojot nepieciešams apmainīt divas blakus stāvošas vērtības, jāpazīst kāds no t.s. swap algoritmiem.

🥛 Plaši pazīstams ir trešā mainīgā paņēmiens. Ja divās glāzēs ir ielieti šķidrumi un tie jāapmaina vietām, nepieciešama trešā glāze, kur ielej vienu no šķidrumiem. Tas pats princips strādā arī algoritmos.

a = 3
b = 5
c = a
a = b #a ir 5
b = c #b ir 3

➕ Otrs lietotais paņēmiens ir saskaitīšana

a = 3
b = 5
a = a + b #a ir 8
b = a - b #b ir 3
a = a - b #a ir 5

🐍 Python valoda piedāvā vienkāršotu paņēmienu, kur abus locekļus pieraksta pretējā secībā

a, b = b, a

🔢 Burbuļkārtošana

Apskati algoritmu Python valodā! Lasi komentārus un iedziļinies! i un j šajā gadījumā ir ciklu skaitītāji. i mainās indeksos 0 - 7, bet j katrā ciklā izpilda par vienu iterāciju mazāk, jo nesakārtotā virknes daļa kļūst katru reizi par 1 skaitli īsāka un to nav jēgas pārbaudīt...

virkne = [5, 8, 2, 4, 0, 2, 3, 1] #Definē virkni
virknes_garums = len(virkne) #Nolasa virknes garumu

# Definē for ciklu virknes caurskatīšanai
for i in range(1, virknes_garums):
    # Definē apakšciklu, kas secīgi salīdzina skaitļu pārus un maina locekļus vietām, kur nepieciešams
    for j in range(virknes_garums - i):
        if virkne[j] > virkne[j + 1]:
            virkne[j], virkne[j + 1] = virkne[j + 1], virkne[j]

Blokshēma

Kad esi sapratis algoritma pamatbūtību, izveido blokshēmu lietotnē Flowgorithm, kas īsteno burbuļkārtošanas algoritmu.