Vadovėlis/Paieška ir Rikiavimas

Atlikęs praeito skyriaus uždavinius, jau žinai daug apie sąrašo sukūrimą ir visus bazinius sąrašo metodus. Dabar pasinaudosim įgytomis žiniomis ir susipažinsim su labai dažnai susidruriamais 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 naudojaus - tiesinė paieška ir dvejetainė paieška.

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šsisaugom sąrašo pirmą ir paskutinį indeksą
    apačia = 0
    viršus = len(sąrašas) - 1
    
    while apačia <= viršus:
        # aatrandame 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 = 4 + 1 = 5.

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 = 7 - 1 = 6

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 = 5 + 1 = 6

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

Burbulinis rikiavimas ( angliškai "Bubble sort" ) - 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ėkim 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ą.

Quicksort

Quicksort is a widely used sorting algorithm that follows a divide-and-conquer approach. It works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The process is then repeated recursively on each sub-array.

Here's an example of a quicksort function in Python:

def quicksort(arr, low, high):
    if low < high:
        # Partition the array
        pi = partition(arr, low, high)
        
        # Recursively sort the left and right sub-arrays
        quicksort(arr, low, pi-1)
        quicksort(arr, pi+1, high)

def partition(arr, low, high):
    # Select the pivot element
    pivot = arr[high]
    i = low - 1
    
    # Partition the array into two sub-arrays
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i+1

This function takes an array arr, a lower index low, and a higher index high, and sorts the array in ascending order using quicksort. The partition function is a helper function that takes the same arguments and returns the index of the pivot element after partitioning.

The quicksort algorithm has a worst-case time complexity of O(n^2), but its average time complexity is O(n log n), which is faster than many other sorting algorithms. In practice, quicksort is often faster than other O(n log n) sorting algorithms like merge sort, due to its efficient use of the cache and the fact that it sorts in place (meaning it doesn't require additional memory).

Merge sort

Merge sort, on the other hand, is a more efficient sorting algorithm that uses a divide-and-conquer approach. It works by dividing the list into smaller sublists, sorting those sublists, and then merging them back together. Here's an example of a merge sort function in Python:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]
        
        merge_sort(left_half)
        merge_sort(right_half)
        
        i = j = k = 0
        
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1
        
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
        
        while j < len(right_half):
            arr[k] = right_half