Vadovėlis/Paieška ir Rikiavimas

Atlikęs praeito skyriaus uždavinius, jau daug žinai apie sąrašo sukūrimą ir visus bazinius sąrašo metodus. Dabar pasinaudosime įgytomis žiniomis ir susipažinsime su labai dažnai sutinkamais uždaviniais: paieška ir rikiavimas.

Paieška

Paieškos algoritmai naudojami norint rasti konkretų elementą sąraše ar duomenų masyve. Yra keletas paieškos algoritmų, tačiau parodysiu du dažniausiai naudojamus - tiesinę paiešką ir dvejetainę paiešką.

Tiesinė paieška

Tiesinė paieška - tai paprastas paieškos algoritmas, kuris, ieškodamas tikslinės reikšmės, peržiūri kiekvieną sąrašo elementą. Pažiūrėk į tiesinės paieškos funkcijos pavyzdį "Python" kalba:

def tiesinė_paieška(sąrašas, ieškomas_žodis):
    for i in range(len(sąrašas)):
        if sąrašas[i] == ieškomas_žodis:
            return i
    return -1  # ieškomas_žodis nerastas

Ši funkcija priima masyvą sąrašas ir tikslinę reikšmę ieškomas_žodis ir grąžina tikslinės reikšmės indeksą masyve. Jei tikslinė vertė nerandama masyve, funkcija grąžina -1. Labai praprasta ir aišku.

Dvejetainė paieška

Kita vertus, dvejetainė paieška yra efektyvesnis paieškos algoritmas, kuris veikia tik surikiuotose masyvuose (sąrašuose). Jis veikia pakartotinai dalydamas paieškos intervalą per pusę, kol randama tikslinė reikšmė. Painu? Daug aiškiau bus pažiūrėjus šį pavyzdį:

def dvejetainė_paieška(sąrašas, tikslas):
    # išsisaugome sąrašo pirmą ir paskutinį indeksą
    apačia = 0
    viršus = len(sąrašas) - 1
    
    while apačia <= viršus:
        # atrandame vidurį pagal formulę: (pradžios indeksas + pabaigos indeksas) padalintas per pusę, be liekanos
        viduriukas = (apačia + viršus) // 2
        # patikriname, ar `viduriukas` indekse yra mūsų ieškomas tikslas, ir jį atradus grąžiname indeksą.
        if sąrašas[viduriukas] == tikslas:
            return viduriukas
        # jeigu ne, tai pagal tai, kurioje pusėje yra ieškomas elementas pakeičiame viršutinį arba apatinį indeksą
        elif sąrašas[viduriukas] < tikslas:
            apačia = viduriukas + 1
        else:
            viršus = viduriukas - 1
        # ir kartojame iš naujo, bet jau su nauju, per pus mažesniu rėžiu
    
    return -1  # tikslas nerastas

sąrašas = [1,2,3,4,5,6,7,8,9,10]
print(dvejetainė_paieška(sąrašas, 7)) # 6

Panagrinėkim detaliai, kaip vyksta procesas. Ieškome, kur yra skaičius 7, sąraše [1,2,3,4,5,6,7,8,9,10]. Funkcijos pradžios kintamieji:

 apačia = 0
 viršus = 9 # (ilgis 10 - 1 )

Pirmas `while` ciklas:

 viduriukas = 4 # (0 + 9) // 2
 # sąrašas[4] saugo reikšmę 5. Ne mūsų ieškomas skaičius.
 # kadangi tikslas yra surasti 7, tai mūsų kito ciklo metu ieškosime viršutinėje sąrašo dalyje, todėl nusistatome naują apačios reikšmę, viduriukas + 1.
 apačia = 5 # (4 + 1)

Antras `while` ciklas:

 viduriukas = 7 # (5 + 9) // 2
 # sąrašas[7] saugo reikšmę 8. Jau arčiau, bet ne dar vis ne mūsų ieškoma reikšmė 7. Nustatome šįkartą naują viršutinę reikšmę, viduriukas - 1
 viršus = 6 # (7 - 1)

Trečias `while` ciklas:

 viduriukas = 5 # (5 + 6) // 2
 # sąrašas[5] saugo reikmę 6. Vėl pro šalį. Nustatome naują apatinę reikšmę:
 apačia = 6 # (5 + 1)

Ketvirtas `while` ciklas:

 viduriukas = 6 # (6 + 6) // 2
 sąrašas[6] saugo reikšmę 7. Valio! Radom. Grąžinam indeksą 7.

Atkreipk dėmesį, kad dvejetainės paieškos algoritmas atrado reikšmę per 4 ciklus. Kaip manai, kiek ciklų prireiktų tiesinės paieškos algoritmui? Pasufleruosiu... Daugiau :)

Rikiavimas

Rikiavimo algoritmai naudojami duomenų sąrašui išdėstyti tam tikra tvarka. Rikiavimo algoritmų yra daug ir įvairių, bet papasakosiu tik kelis naudingiausius. Pateiktus algoritmus tu gelėsi nesunkiai pritaikyti ir kitokiems duomenų tipams, ne tik žodžiams. Bet apie tai vėliau.

Įterpimo rikiavimas (Insertion Sort)

Įterpimo rikiavimas yra paprastas rikiavimo algoritmas, kuris veikia padalydamas sąrašą į dvi dalis: surikiuotą ir nesurikiuotą. Tada iteratyviai paimamas elementas iš nerikiuotos dalies ir įterpiamas į reikiamą vietą surikiuotoje dalyje, kol visas sąrašas surikiuojamas. Pažiūrėkim, kaip tai atrodo:

def įterpimo_rikiavimas(sąrašas):
    for i in range(1, len(sąrašas)):
        raktas = sąrašas[i]
        j = i - 1
        while j >= 0 and sąrašas[j] > raktas:
            sąrašas[j+1] = sąrašas[j]
            j -= 1
        sąrašas[j+1] = raktas

Ši funkcija paima sąrašą sąrašas ir sutikiuoja jį didėjimo tvarka, naudodama įterpimo rikiavimą. Ji pradeda iteruoti per sąrašą nuo antrojo elemento (indeksas 1) iki galo. Kiekvieno elemento reikšmė išsaugoma kaip raktas, o jo indeksas - kaip i, tada einama atgal per surikiuotą sąrašo dalį (nuo indekso i-1 iki 0) ir ieškoma tinkamos vietos rakto reikšmei įterpti. Tai daroma lyginant rakto vertę su kiekvienu išrikiuotos sąrašo dalies elementu ir perstumiant didesnius elementus viena pozicija į dešinę, kol randama tinkama pozicija. Suradęs tinkamą poziciją, į ją įterpia rakto reikšmę.

Įterpimo rikiavimo laiko sudėtingumas blogiausiu atveju yra O(n²), o tai reiškia, kad didelių įvesties sąrašų atveju jis gali būti lėtas. Tačiau jis turi mažesnes pridėtines išlaidas nei kai kurie kiti rikiavivmo algoritmai ir gali būti efektyvesnis už juos mažiems įvesties sąrašams arba iš dalies surikiuotiems įvesties sąrašams.

Burbulinis rikiavimas (Bubble sort)

Burbulinis rikiavimas - tai paprastas rikiavimo algoritmas, kuris pakartotinai pereina per sąrašą, palygina gretimus elementus ir sukeičia juos vietomis, jei jų eiliškumas netinkamas. Pažiūrėkime į burbulinio rikiavimo funkcijos pavyzdį:

def burbulinis_rikiavimas(sąrašas):
    sąrašo_ilgis = len(sąrašas)

    for i in range(sąrašo_ilgis):
        for j in range(0, sąrašo_ilgis-i-1):
            if sąrašas[j] > sąrašas[j+1]:
                sąrašas[j], sąrašas[j+1] = sąrašas[j+1], sąrašas[j]

Ši funkcija paima sąrašą sąrašas ir surikiuoja jį didėjančia tvarka, naudodama burbulinį rikiavimą.

Greitasis rikiavimas (Quicksort)

Greitasis rikiavimas yra plačiai naudojamas rikiavimo algoritmas, kuriame taikomas "skaldyk ir valdyk" metodas. Jis veikia iš masyvo (arba sąrašo) išrenkant ašinį elementą ir kitus elementus suskirstant į du papildomus masyvus pagal tai, ar jie mažesni, ar didesni už ašinį elementą. Tada šis procesas rekursiškai kartojamas kiekviename pogrupyje.

Štai greitojo rikiavimo funkcijos pavyzdys "Python" kalba:

def greitasis_rikiavimas(masyvas):
    mažiau = []
    lygus = []
    daugiau = []
    if len(masyvas) > 1:
        ašis = masyvas[0]
        for x in masyvas:
            if x < ašis:
                mažiau.append(x)
            elif x == ašis:
                lygus.append(x)
            elif x > ašis:
                daugiau.append(x)
        # neužmiršk grąžinti rezultato!
        return greitasis_rikiavimas(mažiau) + lygus + greitasis_rikiavimas(daugiau)
    # Atkreipk dėmesį, kad naudojame `lygus`, o ne `ašis`
    else:  
        return masyvas

Funkcijos parametras masyvas yra sąrašas, kurį norime surikiuoti.

Pagrindinė funkcijos dalis yra sąlyga if len(masyvas) > 1:, kuri tikrina, ar sąraše yra daugiau nei vienas elementas. Jei sąraše yra tik vienas arba nulis elementų, tai jis jau yra surikiuotas, todėl tiesiog grąžinamas toks pat sąrašas.

Jei sąraše yra daugiau nei vienas elementas, algoritmas tęsiasi. Pirma, parenkamas elementas ašis, šiuo atveju tai yra pirmas sąrašo elementas masyvas[0]. Tuomet algoritmas eina per visus sąrašo elementus ir prideda juos į tris skirtingus sąrašus (mažiau, lygus, daugiau), priklausomai nuo to, kaip jie lyginami su ašis.

• Jei elementas x yra mažesnis už ašis, jis pridedamas į mažiau sąrašą.
• Jei elementas x yra lygus ašis, jis pridedamas į lygus sąrašą.
• Jei elementas x yra didesnis už ašis, jis pridedamas į daugiau sąrašą.

Tai vadinama dalijimo procesu. Po šio proceso turime tris naujus sąrašus: mažiau, lygus ir daugiau, kurie yra dalinai surikiuoti (mažesni už ašis, lygūs ašis ir didesni už ašis).

Toliau funkcija naudoja rekursiją ir kviečia save su mažiau ir daugiau sąrašais, taip pritaikydama dalijimo ir surikiavimo procesą šiems dviejams sąrašams atskirai. Rekursyviai kviečiant save, galiausiai bus pasiektas atvejis, kai sąrašai mažiau ir daugiau bus sudaryti iš nulio arba vieno elemento, o tai reiškia, kad jie jau surikiuoti. Tada funkcija grąžina sudėtą sąrašą: greitasis_rikiavimas(mažiau) + lygus + greitasis_rikiavimas(daugiau), kuris sudarys pilnai surikiuotą sąrašą.

Galutinis rezultatas yra surikiuotas sąrašas, kuris yra grąžinamas iš pradinių sąrašų iškvietimo vietos.

Pvz. jei iškviečiame funkciją greitasis_rikiavimas([3, 1, 4, 1, 5, 9, 2, 6, 5]), tai gražins [1, 1, 2, 3, 4, 5, 5, 6, 9], kuris yra pradinis sąrašas surikiuotas didėjimo tvarka.

Suliejimo rikiavimas (Merge sort)

Suliejimo rikiavimas - tai rikiavimo algoritmas, kuris veikia pagal dalinimo ir sujungimo principą. Tai efektyvus algoritmas, kuris naudoja rekursiją.

Šis algoritmas veikia taip:

• Jei sąraše yra nulis arba vienas elementas, tai jis jau yra surikiuotas. Grąžinamas tas pats sąrašas.
• Jei sąraše yra daugiau nei vienas elementas, sąrašas yra padalinamas į dvi lygias dalis.
• Kiekviena dalis yra rekursyviai rikiuojama naudojant merge sort algoritmą.
• Surikiuotos dvi dalys yra sujungiamos į vieną sąrašą. Sujungimo metu elementai yra palyginami ir sudedami į naują sąrašą didėjimo tvarka.

Šis procesas yra pakartojamas tol, kol visi sąrašai yra padalinti iki vieno elemento ir tada sujungti į vieną galutinį surikiuotą sąrašą.

Suliejimo rikiavimo algoritmas yra efektyvus, nes dalijimo ir sujungimo žingsniai yra vykdomi daug kartų, o kiekviename žingsnyje sąrašas yra padalintas į dvi lygias dalis. Tai leidžia efektyviai rikiuoti didelius sąrašus.

def suliejimo_rikiavimas(sąrašas):
    # sąraše yra nulis arba vienas elementas
    if len(sąrašas) <= 1:
        return sąrašas
    
    # Dalinimo žingsnis: padaliname sąrašą į dvi lygias dalis
    vidurys = len(sąrašas) // 2
    kairė = sąrašas[:vidurys]
    dešinė = sąrašas[vidurys:]
    
    # Rekursyviai rikiuojame kiekvieną dalį
    kairė = suliejimo_rikiavimas(kairė)
    dešinė = suliejimo_rikiavimas(dešinė)
    
    # Sujungimo žingsnis: sujungiame surikiuotas dalis į vieną sąrašą
    return suliejimas(kairė, dešinė)

def suliejimas(kairė, dešinė):
    rezultatas = []
    i = 0  # indeksas kairėje dalyje
    j = 0  # indeksas dešinėje dalyje
    
    # Lyginame ir sujungiame elementus
    while i < len(kairė) and j < len(dešinė):
        if kairė[i] <= dešinė[j]:
            rezultatas.append(kairė[i])
            i += 1
        else:
            rezultatas.append(dešinė[j])
            j += 1
    
    # Jei viena dalis baigiasi anksčiau, pridedame likusius elementus
    while i < len(kairė):
        rezultatas.append(kairė[i])
        i += 1
    while j < len(dešinė):
        rezultatas.append(dešinė[j])
        j += 1
    
    return rezultatas

# Pavyzdys naudojant suliejimo_rikiavimas funkciją
sąrašas = [3, 1, 4, 1, 5, 9, 2, 6, 5]
surikiuotas_sąrašas = suliejimo_rikiavimas(sąrašas)
print(surikiuotas_sąrašas)

Šis pavyzdys naudoja dvi funkcijas: suliejimo_rikiavimas ir suliejimas. suliejimo_rikiavimas funkcija atlieka dalinimo ir rekursyvaus rikiavimo žingsnius, o suliejimas funkcija atlieka surikiuotų dalių sujungimą.

Šio pavyzdžio rezultatas:

[1, 1, 2, 3, 4, 5, 5, 6, 9]