ebSkola

7. tēma / 7.2

7.2 Kārtošanas loģika

Stundas uzdevums: Efektīvai meklēšanai dati ir jāsakārto. Uzbūvē "kārtošanas dzinēju" un izpēti klasisko "burbuļkārtošanas" (Bubble Sort) algoritmu un mācīsimies manipulēt ar saraksta elementu pozīcijām, lai izveidotu funkcionējošu rezultātu (Highscores) tabulu.

SR 2.4.19. (Gatavi algoritmi tipveida uzdevumu risēšanai - kārtošana)

70 min plāns: Teorija un paraugs (~10 min) · 1. uzdevums (~15 min) - samaini divus elementus vietām · 2. uzdevums (~25 min) - uzraksti burbuļa pirmo gājienu · 3. uzdevums (~20 min) - pabeidz pilnu Bubble Sort. Papildu uzdevumu sāc tikai tad, ja pārējie trīs ir gatavi.

Pirms sāc: atver VS Code un izveido failu kartosana.py. Sāc ar diviem elementiem un tikai pēc tam ķeries pie pilna saraksta.

Teorija: Burbuļkārtošana un Apmaiņa

  • Kāpēc kārtot datus?
    • Lai izmantotu bināro meklēšanu.
    • Lai spēlē parādītu "Top 10" spēlētājus no lielākā rezultāta uz mazāko.
  • Mainīgo apmaiņa (Swapping):
    • Datorikā, lai samainītu divus elementus vietām, klasiski vajag trešo ("pagaidu") krātuvi.
    • Python to ļauj izdarīt eleganti vienā rindā: a, b = b, a.
  • Burbuļkārtošana (Bubble Sort):
    • Salīdzina pirmos divus elementus. Ja kreisais ir lielāks, tos samaina vietām.
    • Pāriet pie nākamā blakusesošā pāra un atkārto.
    • Viena pilna cikla beigās pats lielākais skaitlis "uzburbuļo" saraksta beigās.
    • Process jāatkārto tik reižu, cik sarakstā ir elementu.

Vides sagatavošana (Windows)

  1. Atver PowerShell.
  2. Ieej algoritmu mapē: cd Tema7_Algoritmi
  3. Izveido jaunu failu un atver to kodu redaktorā: ni kartosana.py; code kartosana.py

Praktiskie uzdevumi

1. uzdevums -

Samaini divus elementus vietām

Beigās tu pratīsi apmainīt vērtības vienā rindā.

  1. Ieraksti rezultati = [90, 45].
  2. Izdrukā sarakstu pirms maiņas.
  3. Ieraksti rezultati[0], rezultati[1] = rezultati[1], rezultati[0].
  4. Izdrukā sarakstu pēc maiņas.
  5. Mēģini to pašu ar diviem parastiem mainīgajiem a un b.
  6. Pieraksti, kāpēc te nevajag trešo pagaidu mainīgo.

Gatavs, kad: saraksts no [90, 45] kļūst par [45, 90] ar vienu koda rindu.

2. uzdevums -

Uzraksti burbuļa pirmo gājienu

Beigās lielākais skaitlis pēc viena gājiena būs saraksta beigās.

  1. Ieraksti sarakstu ar 6 nesakārtotiem skaitļiem.
  2. Uzraksti ciklu for i in range(len(rezultati) - 1):.
  3. Salīdzini ciklā rezultati[i] ar rezultati[i + 1].
  4. Samaini tos vietām, ja kreisais ir lielāks.
  5. Izdrukā sarakstu pēc viena pilna gājiena.
  6. Pieraksti, kurš skaitlis nonāca pašās beigās.

Gatavs, kad: pēc viena gājiena lielākais skaitlis ir saraksta pēdējā vietā, bet pārējie vēl nav sakārtoti.

3. uzdevums -

Pabeidz pilnu Bubble Sort

Beigās tavs algoritms sakārtos visu sarakstu.

  1. Ieliec savu gājiena ciklu iekšā otrā ciklā for j in range(len(rezultati)):.
  2. Palaid un izdrukā sarakstu pēc katra ārējā gājiena.
  3. Pārbaudi, vai saraksts galā ir pilnībā sakārtots.
  4. Pievieno skaitītāju, cik salīdzinājumu kopā tika veikts.
  5. Palielini sarakstu līdz 10 elementiem un pieraksti salīdzinājumu skaitu.
  6. Salīdzini ar 6 elementiem iegūto skaitli.
  7. Pieraksti vienu secinājumu: kā aug salīdzinājumu skaits, palielinoties sarakstam.

Gatavs, kad: saraksts ir pilnībā sakārtots, un salīdzinājumu skaits aug daudz straujāk nekā elementu skaits.

Papildu uzdevums - Apturi kārtošanu agrāk

Ja pamatdarbs ir gatavs, neļauj algoritmam strādāt velti.

  1. Ieraksti pirms katra gājiena mainits = False.
  2. Uzstādi to uz True, kad notiek apmaiņa.
  3. Pārtrauc ārējo ciklu ar break, ja gājiena laikā nekas nemainījās.
  4. Palaid ar jau sakārtotu sarakstu un pieraksti gājienu skaitu.
  5. Salīdzini ar variantu bez šī uzlabojuma.

Gatavs, kad: ar jau sakārtotu sarakstu algoritms beidz darbu pēc viena gājiena, nevis pēc visiem.

Koda piemērs (ligzdotie cikli un apmaiņa - grūtākā daļa)

# Grūtākā vieta: DIVI cikli, kas dara dažādas lietas.
# Iekšējais cikls veic vienu gājienu un aizstumj lielāko skaitli uz beigām.
# Ārējais cikls atkārto šo gājienu tik reižu, cik vajag.

def bubble_sort(saraksts):
    n = len(saraksts)
    salidzinajumi = 0

    for j in range(n):
        mainits = False
        for i in range(n - 1 - j):        # -j: beigas jau ir sakārtotas
            salidzinajumi += 1
            if saraksts[i] > saraksts[i + 1]:
                # apmaiņa vienā rindā, bez pagaidu mainīgā
                saraksts[i], saraksts[i + 1] = saraksts[i + 1], saraksts[i]
                mainits = True
        if not mainits:                   # jau sakārtots - nav jēgas turpināt
            break

    return saraksts, salidzinajumi

dati = [42, 15, 8, 99, 23, 4]
rezultats, skaits = bubble_sort(dati)
print(f"{rezultats} ({skaits} salīdzinājumi)")
Saraksts sakārtojas augošā secībā. Bez - j algoritms velti pārbauda jau sakārtotās beigas, bet bez mainits tas iet visus gājienus arī tad, kad saraksts jau ir kārtībā.