7. labor: sorteerimine

Labori 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 tunnitöö millele on välja pakutud kaks lisaülesannet.

Tunnitöö: 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, et kirjutad optimeeringu nii sisemisse kui välimisse tsüklisse!
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.
Sorteerida tohid kogu programmi vältel massiivi vaid ühel korral! Teises suunas massiivi kuvamiseks uuesti seda sorteerida ei tohi!
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

Sa saad juba alustada eelmisel nädalal kirjutatud funktsioo! Eelmise nädala tunnitöödest on sul mõned funktsioonid juba olemas. Kopeeri sisse ja vajadusel modifitseeri neid, lisa juurde mis puudu.
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 on esimene, vähim viimane.

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

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 põhjaliku ja tõendusliku testiga (selleks on spetsiaalsed tööriistad) aga võib mõnel juhul vea nähtavaks tuua.

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

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: 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.

Lisaülesanne 2: Maatriksi sorteerimine

Selles ülesandes hüppad veidike teemades ette ning pead omapäi tutvuma 2-dimensioonilise massiivi ehk maatriksiga.

Lahenda ülesanne eraldi programmina, kasutades varasemalt tehtud põhjana. Jäta algne lahendus alles! Varem tehtud funktsioonid kuluvad tulevikus ära!
Antud lisaülesande võid lahendada funktsioonideta kuna me pole veel maatriksi edastamisest funktsioonidesse rääkinud.
Massiivi asemel tuleb sorteerida 5 x 5 maatriks
Sorteerimine toimub rida-rea haaval.

Maatriks peab olema algväärtustatud. Kasuta järgnevat maatriksit testimiseks

#define LEN 5

int main(void)
{
    int numbers[LEN][LEN] = {{1, 2, 3, 4, 5},
                             {5, 4, 3, 2, 1},
                             {-10, -25, -5, -105, -44},
                             {-3, 3, -3, 3, -3},
                             {0, 0, 0, 0, 0}};
    return 0;
}

#define LEN 5

int main(void)

{

int numbers[LEN][LEN] = {{1, 2, 3, 4, 5},

{5, 4, 3, 2, 1},

{-10, -25, -5, -105, -44},

{-3, 3, -3, 3, -3},

{0, 0, 0, 0, 0}};

return 0;

}

Näite maatriksi väljatrükist ja tsüklitest leiad siit: https://blue.pri.ee/ttu/programmeerimine-i/koodinaited/muutujate-algvaartustamine/

Oodatav tulemus

   1    2    3    4    5
   1    2    3    4    5
-105  -44  -25  -10   -5  
  -3   -3   -3    3    3
   0    0    0    0    0

1 2 3 4 5

-105 -44 -25 -10 -5

-3 -3 -3 3 3

0 0 0 0 0

Vihjeid

Soovid oma juba loodud mullsorteerimise funktsiooni ära kasutada? C keeles on võimalik edastada funktsiooni maatriks “rea-kaupa” (tegelikkus on veidi keerulisem aga täidab meie eesmärki. Selleks kutsu funktsioon nii:
SortArray(numbers[rowIndex], rowLength); Sedasi näeb su kood oluliselt ilusam välja.

Pärast tundi peaksid oskama järgmist

Peaksid saama aru mis asi arvu alus on
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