Algoritmų sudarymas ir analizė laboratorinis (2)


Informatikos laboratorinis darbas.

Užduotis. Rikiavimo uždavinys.Realizavimas. Rūšiavimo algoritmų tyrimas. Rūšiavimas „suliejimu“. Rūšiavimas „suliejimu“ sąraše. Algoritmo ekspermentinis tyrimas. Rūšiavimo algoritmas „Bucket sort“. Algoritmo ekspermentinis tyrimas.


Dešinėje pažymėta, kiek kartų vykdomos eilutės. Skaičiavimo algoritme skaičiuosime tik tas eilutes, kurios yra susijusios su algoritmu.

return sujungti(f, w, rusiuoti(f, w, [of1_f, of1_t]), rusiuoti(f, w, [of2_f, of2_t]))2Trusiuoti

while i < (left[1] - left[0] + 1) and j < (right[1] - right[0] + 1):n

return sujungti(f, w, rusiuoti(f, w, [of1_f, of1_t]), rusiuoti(f, w, [of2_f, of2_t]))Tsujungti(2Trusiuoti)

Algoritmas testuojamas rikiuojant sveikuosius skaičius. Buvo sugeneruota daug atsitiktinių skaičių, nurodant failo dydį.Rikiuojant buvo skaičiuojama rikiavimo trukmė, palyginamas rikiavimas masyve ir sąraše. Duomenų imtis 200 iki 100.000.

Šis rikiavimo metodas remiasi „Skaldyk ir valdyk“ paradigma. Metodas – rekursinis. Algoritmo viekimo tvarka:

*Pertvarkomas masyvas į du kitus masyvus taip, kad tam tikras pasirinktas elementas būtų didesnis arba lygus už iš vieno masyvų visus elementus, o už kito masyvo elementus jis būtų mažesnis arba lygus. Elementas įvardintas kaip tam tikras elementas yra paskaičiuojamas pačioje pertvarkymo pusėje

*Kadangi masyvai jau yra surikiuoti ir vienoje vietoje, taigi nėra reikalo juos sujungti. Visas masyvas surikiuotas

for j in xrange( kaire + 4, desine + 4, 4):n

Trusiuoti = 2 + n + 27 + 2Trusiuoti + 1 = 2Trusiuoti(n/2) + n + 30

*Įterpiant reikšmę į kategoriją, ši reikšmė yra iš karto įterpiama taip, jog seka būtų nuosekli

*Suliejimo metu nuosekliai imamos reikšmės nuo žemiausios kategorijos ir palaipsniui imamos vis kitos reikšmės iki pačios aukščiausios reikšmės.

Algoritmų sudarymas ir analizė laboratorinis (2). (2017 m. Birželio 04 d.). http://www.mokslobaze.lt/algoritmu-sudarymas-ir-analize-laboratorinis-2.html Peržiūrėta 2017 m. Spalio 20 d. 10:08