Algoritmi un datu struktūras "Bubble Sort" šķirošana

3. izveidot testēšanas programmu, kas ģenerēs masīvus, šķiros tos un salīdzinās šķirošanai nepieciešamo patērēto laiku (milisekundēs); šķirot un ģenerēt trīs dažāda veida masīvus: pilnīgi sakārtotu masīvu, vidēji sakārtotu masīvu un pilnīgi nesakārtotu masīvu.

4. uzzīmēt trīs grafikus, kas atspoguļo nepieciešamā laika atkarību no masīva izmēra.

Tā kā laiks, kas nepieciešams šķirošanai, ir jāmēra milisekundēs, izmantošu C++ iebūvēto bibliotēku un tās iespējas, ko sniedz clock(), clock t. Tā kā ar šo funkciju palīdzību iespējams izmērīt procesora tikšķu skaitu, var iegūt šķirošanai nepieciešamo laiku, atņemot no beigu vērtības sākuma datus. Tā kā procesora tikšķi tiek pielīdzināti milisekundēm un ir praktiski vienādi ar tām, varu uzskatīt, ka tiek mērīts eksperimenta laiks milisekundēs.

Nepieciešams izveidot funkciju, kas, ņemot par pamatu dinamisko masīvu un elementu skaitu tajā, veiks šķirošanu pēc burbuļa metodes.

Nepieciešams arī izveidot funkciju, kas izskaitļos katrai operācijai nepieciešamo laiku. Tā kā šķirošana ar burbuļa metodi tika definēta iepriekš, es to droši varu izsaukt no patreizējās laika mērīšanas funkcijas.

Nepieciešams 10 reizes izmērīt šķirošanas laiku trīs dažādas sakārtotības pakāpes masīviem, turklāt katrreiz palielinot to izmērus. Eksperimentālā ceļā noskaidroju, ka minimālais masīva elementu skaits, ko šķirojot, programma var mērīt laiku, ir aptuveni 800, bet, lai iegūtu skaidrākus un vienkāršākus rezultātus, par pirmo izmēru pieņemšu 1000. Pēc katra šķirošanas bloka palielināšu šo izmēru par 1000, līdz ar to beidzamais masīvs saturēs 10000 elementus.