Praktikumi materjal
- Slaidid: Arvusüsteemid
- Slaidid: Sorteerimine
- Algoritm: https://blue.pri.ee/ttu/programmeerimine-i/algoritmide-ulesanded/#Algoritm_6_Vahima_arvu_aluse_leidmine
Esitamisele kuuluvad ülesanded
Selles tunnis on üks ülesanne, mida laiendab üks lisaülesanne
Tunnitöö [W07-1]: Mullsorteerimine
Tunnitöö raames sorteerid kasutaja poolt sisestatud arvujada kasutades mullsorteerimise algoritmi.
Nõuded
- Kasutajalt küsitakse 5 täisarvu, mis salvestatakse massiivi
- Sorteeri massiiv kasutades mullsorteerimise algoritmi
- Optimeeri tsüklite kestvust sedasi, et asjatult võrdlusi ei sooritataks – just nii nagu oli slaidil näidatud. Veendu, etoptimeerid nii sisemise kui ka välimise tsükli piire!
- Loenda ja kuva, mitu korda arve võrreldi omavahel. Kui tegid optimeerimise korrektselt, peaksid saama täpselt 10 võrdlust.
- Kuva massiiv kasvavas järjekorras
- Kuva massiiv kahanevas järjekorras
- Kogu programmi vältel tohid sorteerida vaid ühe korra
- Luua tuleb neli funktsiooni. Loetelu nõutud funktsioonidest on loetletud allpool
- Meeldetuletuseks!
- Muutujad lowerCamelCase
- Funktsioonid UpperCamelCase
- Makrod SCREAMING_SNAKE_CASE
- Maagilised numbrid koodist asendatud makrotega
- Massiivi pikkus antakse funktsiooni alati kaasa
Vasta küsimusele: jälgida saab nii võrdluste kui vahetuste arvu. Kumb neist meie optimeeringu tulemusel väheneb, kumb jääb samaks?
Lahenduses nõutavad funktsioonid
Selles programmis tuleb sul kokku luua 4 funktsiooni
- Numbrite lugemiseks massiivi
- Massiivi sorteerimiseks
- Kaks funktsiooni massiivi kuvamiseks
Vihjed
- Saad soovi korral korduvkasutada juba mõnda eelenvatel nädalatel koostatud funktsiooni
- Mullsorteerimise funktsioon on järjekordne funktsioon, mille peaksid oma varasalve panema. Kui funktsiooni endale talletad, võta sealt vahetuste loendamine ära – mida vähem kõrvalmõjusid funktsioonidel on seda parem.
Test 1: Tagurpidine järjestus
Tegu on kõige keerulisema juhuga mullsorteerimiseks. Suurim arv on esimene, vähim viimane.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
This program takes 5 numbers from the user and sorts them. Output is given in both ascending and descending order. Enter number 1 / 5: 5 Enter number 2 / 5: 4 Enter number 3 / 5: 3 Enter number 4 / 5: 2 Enter number 5 / 5: 1 Comparisons made during sorting: 10 Numbers in ascending order: 1 2 3 4 5 Numbers in descending order: 5 4 3 2 1 |
Test 2: Juhuslik massiiv
Juhuslik järjekord. Võrdluste arv jääb samaks. Testib ka kitsaid piirjuhte osadel arvutisüsteemidel, kui massiivi piirest üle minnakse. Tegu ei ole garanteeritud tulemust andva testiga (selleks on spetsiaalsed tööriistad), aga võib mõnel juhul vea nähtavaks tuua.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
This program takes 5 numbers from the user and sorts them. Output is given in both ascending and descending order. Enter number 1 / 5: -5 Enter number 2 / 5: 3 Enter number 3 / 5: 9 Enter number 4 / 5: 2 Enter number 5 / 5: -5 Comparisons made during sorting: 10 Numbers in ascending order: -5 -5 2 3 9 Numbers in descending order: 9 3 2 -5 -5 |
Lisaülesanne 1 [W07-2]: Tsüklite täiendav optimeerimine
Algselt kirjeldatud algoritmi üks puudustest on olukord, kui massiiv saab oluliselt varem sorteeritud, kui algoritmi täielik tööaeg ette näeb. Sellist olukorda on võimalik tuvastada ning ära kasutada.
- Kui massiiv saab sorteerituks enne viimast välimise tsükli läbikäiku, peata sorteerimine. Väldi tühja töö tegemist.
- Vihjeks: mõtle, millised tegevused tehakse sorteerimise käigus ning mida ei tehta arvude puhul, mis on juba sorteeritud.
- Kaitsmisel: Selgita, milliste sisendandmete puhul optimeeritud algoritm parema tulemuse annab, ning tõesta seda oma tulemusega.
Pärast tundi peaksid oskama järgmist
- Peaksid saama aru, mis on arvu alus
- Peaksid teadma enimlevinuid arvusüsteeme, muuhulgas kahend- ja 16ndsüsteemi.
- Peaksid aru saama, mis vahe on positsioonilisel ja mittepositsioonilisel arvusüsteemil.
- Peaksid aru saama, mis asi on bitt ja bait ning mitu bitti on baidis.
- Peaksid oskama teisendusi arvusüsteemides (10 -> 2, 10 -> 16, 10 -> 8, 2 -> 10, 2 -> 16, 16 -> 10, 16 -> 2, 8 -> 10)
- Peaksid aru saama, mis asi on täisarvu ületäitumine
- Peaksid mõistma, et sorteerimiseks on väga suur hulk algoritme ning õige algoritmi valimine on olulise tähtsusega reaalsetes rakendustes.
- Peaksid mõistma, et optimeerimisel ja võimsamal riistvaral on oma koht, kuid parem algoritm või lähenemine annab suurema võidu.
- Peaksid aru saama, kuidas mullsort töötab ning oskama seda oma rakendustes kasutada.
Täiendav materjal
Üldised viited
- Khan Academy: Binary and hexadecimal number systems
https://www.khanacademy.org/math/algebra-home/alg-intro-to-algebra/algebra-alternate-number-bases/v/number-systems-introduction - Sorting algorithms animations (compare speed, different input data, algorithms)
https://www.toptal.com/developers/sorting-algorithms - 15 and Hexadecimal – Numberphile
https://www.youtube.com/watch?v=9xbJ3enqLnA - Binary Addition & Overflow – Computerphile
https://www.youtube.com/watch?v=WN8i5cwjkSE - Base Number Jokes Explained – Numberphile
https://www.youtube.com/watch?v=Fmb3TCvlETk - Integer Overflow
https://en.wikipedia.org/wiki/Integer_overflow - Positional notation
https://en.wikipedia.org/wiki/Positional_notation - Sorting Algorithms
https://en.wikipedia.org/wiki/Sorting_algorithm - Bubble sort
https://en.wikipedia.org/wiki/Bubble_sort - Radix
https://en.wikipedia.org/wiki/Radix
Täisarvude ületäitumine reaalses elus
- Chrome and Firefox Are So Old They Might “Break” the Internet
https://www.reviewgeek.com/110211/chrome-and-firefox-are-so-old-they-might-break-the-internet/
Seotud viide: https://maqentaer.com/devopera-static-backup/http/dev.opera.com/articles/view/opera-ua-string-changes/index.html - Older Honda and Acura models hit by Y2K22 bug that resets clocks 20 years in the past
https://www.theverge.com/2022/1/8/22873403/honda-acuras-y2k22-bug-clocks-reset-2002 - Integer overflow in GPS:
https://en.wikipedia.org/wiki/GPS_Week_Number_Rollover - Gangnam Style overflows INT_MAX, forces YouTube to go 64-bit
https://arstechnica.com/information-technology/2014/12/gangnam-style-overflows-int_max-forces-youtube-to-go-64-bit/ - Computerphile – How Gangnam Style Broke
https://www.youtube.com/watch?v=vA0Rl6Ne5C8 - Overflow in the stock market: https://www.theregister.com/2021/05/07/bug_warren_buffett_rollover_nasdaq/
- Integer overflow in calendars (Y2K):
https://en.wikipedia.org/wiki/Year_2000_problem - Nuclear Gandhi:
https://en.wikipedia.org/wiki/Nuclear_Gandhi