{"id":5464,"date":"2020-09-27T21:12:00","date_gmt":"2020-09-27T19:12:00","guid":{"rendered":"https:\/\/blue.pri.ee\/ttu\/?p=5464"},"modified":"2026-06-29T12:55:04","modified_gmt":"2026-06-29T10:55:04","slug":"7-lab-sorting","status":"publish","type":"post","link":"https:\/\/blue.pri.ee\/ttu\/labs\/7-lab-sorting\/","title":{"rendered":"PR1EN7: Sorting"},"content":{"rendered":"<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_85 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/7-lab-sorting\/#Lab_materials\" >Lab materials<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/7-lab-sorting\/#Tasks\" >Tasks<\/a><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/7-lab-sorting\/#Lab_task_W07-1_Bubble_sort\" >Lab task [W07-1]: Bubble sort<\/a><ul class='ez-toc-list-level-5' ><li class='ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/7-lab-sorting\/#Requirements\" >Requirements<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/7-lab-sorting\/#Create_the_following_functions\" >Create the following functions<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/7-lab-sorting\/#Hints\" >Hints<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/7-lab-sorting\/#Test_1_Reverse_order\" >Test 1: Reverse order<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/7-lab-sorting\/#Test_2_Random_order\" >Test 2: Random order<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/7-lab-sorting\/#Extra_task_1_W07-2_Further_loop_optimization\" >Extra task 1 [W07-2]: Further loop optimization<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/7-lab-sorting\/#After_the_class\" >After the class<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/7-lab-sorting\/#Additional_content\" >Additional content<\/a><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-12\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/7-lab-sorting\/#Generic_references\" >Generic references<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-13\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/7-lab-sorting\/#Integer_overflow_in_real_life\" >Integer overflow in real life<\/a><\/li><\/ul><\/li><\/ul><\/nav><\/div>\n<h3><span class=\"ez-toc-section\" id=\"Lab_materials\"><\/span><strong>Lab materials<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li>Slides: <a href=\"https:\/\/blue.pri.ee\/ttu\/files\/iax0583\/slaidid-en\/07_numeral_systems.pdf\"><strong>Numerical systems<\/strong><\/a><\/li>\n<li>Slides: <a href=\"https:\/\/blue.pri.ee\/ttu\/files\/iax0583\/slaidid-en\/07_Sorting.pdf\"><strong>Sorting<\/strong><\/a><\/li>\n<li>Algorithm:<strong> <a href=\"https:\/\/blue.pri.ee\/ttu\/programming-i\/algorithm-tasks\/#Algorithm_6_Finding_the_lowest_possible_number_base\">https:\/\/blue.pri.ee\/ttu\/programming-i\/algorithm-tasks\/#Algorithm_6_Finding_the_lowest_possible_number_base<\/a><\/strong><\/li>\n<\/ul>\n<h3><span class=\"ez-toc-section\" id=\"Tasks\"><\/span>Tasks<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>This lab has one base task, which can be extended by one extra task.<\/p>\n<h4><span class=\"ez-toc-section\" id=\"Lab_task_W07-1_Bubble_sort\"><\/span>Lab task [W07-1]: Bubble sort<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<p>In this lab task you will implement a bubble sorting algorithm that will sort an array of numbers entered by the user.<\/p>\n<h5><span class=\"ez-toc-section\" id=\"Requirements\"><\/span>Requirements<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<ul>\n<li>User is asked for 5 integers, that are stored in an array<\/li>\n<li>Array is to be sorted using the bubble sort algorithm<\/li>\n<li>You must optimize the loops in such a way that it skips the redundant comparison operations &#8211; just as was shown in the slide! Make sure to optimize both the inner and the outer loop lengths.<\/li>\n<li>Count and show how many times the numbers were compared by the algorithm.\u00a0<strong>If you count exactly 10, the optimizations are likely correct.<\/strong><\/li>\n<li>Display the sorted array in an ascending order<\/li>\n<li>Display the sorted array in the descending order<\/li>\n<li>You are allowed to sort the array only once during the program!<\/li>\n<li>You are to create four functions to solve the base task (listed below)<\/li>\n<li>Reminders!\n<ul>\n<li>Variables <span class=\"lang:default highlight:0 decode:true crayon-inline\">lowerCamelCase<\/span><\/li>\n<li>Functions\u00a0 <span class=\"lang:default highlight:0 decode:true crayon-inline\">UpperCamelCase<\/span><\/li>\n<li>Macros\u00a0 <span class=\"lang:default highlight:0 decode:true crayon-inline\">SCREAMING_SNAKE_CASE<\/span><\/li>\n<li>Magical numbers must be replaced with macros<\/li>\n<li>Array length must always be passed to the function<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p><strong>Answer this question:<\/strong> You can observe both the count of comparisons and swaps. Which one will be reduced by limiting the loops and why?<\/p>\n<h5><span class=\"ez-toc-section\" id=\"Create_the_following_functions\"><\/span>Create the following functions<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>Implement a total of 4 functions in your code<\/p>\n<ul>\n<li>For reading the numbers<\/li>\n<li>For sorting the array<\/li>\n<li>Two functions for displaying the array<\/li>\n<\/ul>\n<h5><span class=\"ez-toc-section\" id=\"Hints\"><\/span>Hints<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<ul>\n<li>You can reuse functions from the tasks you completed previously<\/li>\n<li>Bubble sort is another one of those functions that you should keep in handy for the future. Just make sure to remove the counting part from the code &#8211; we typically don&#8217;t want side effects for our functions.<\/li>\n<\/ul>\n<h5><span class=\"ez-toc-section\" id=\"Test_1_Reverse_order\"><\/span>Test 1: Reverse order<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>This is the worst case scenario for bubble sort. All numbers are sorted in the opposite order to what they need to be.<\/p>\n<pre class=\"theme:cisco-router toolbar:1 nums:false lang:default highlight:0 decode:true\" title=\"Sample: sort\">This program takes 5 numbers from the user and sorts them. Output is given in both ascending and descending order.\r\n\r\nEnter number 1 \/ 5: 5\r\nEnter number 2 \/ 5: 4\r\nEnter number 3 \/ 5: 3\r\nEnter number 4 \/ 5: 2\r\nEnter number 5 \/ 5: 1\r\n\r\nComparisons made during sorting: 10\r\n\r\nNumbers in ascending order: 1 2 3 4 5\r\nNumbers in descending order: 5 4 3 2 1<\/pre>\n<h5><span class=\"ez-toc-section\" id=\"Test_2_Random_order\"><\/span>Test 2: Random order<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>The order is randomized here. The number of comparisons remains the same. This may also trigger an edge case in some computer systems when an array bound is exceeded. NB! You should not assume this to be reliable, there are more specialized tools for that, however it may bring out some errors in some systems.<\/p>\n<pre class=\"theme:cisco-router toolbar:1 nums:false lang:default highlight:0 decode:true\" title=\"Sample: sort\">This program takes 5 numbers from the user and sorts them. Output is given in both ascending and descending order.\r\n\r\nEnter number 1 \/ 5: -5\r\nEnter number 2 \/ 5: 3\r\nEnter number 3 \/ 5: 9\r\nEnter number 4 \/ 5: 2\r\nEnter number 5 \/ 5: -5\r\n\r\nComparisons made during sorting: 10\r\n\r\nNumbers in ascending order: -5 -5 2 3 9\r\nNumbers in descending order: 9 3 2 -5 -5<\/pre>\n<h4><span class=\"ez-toc-section\" id=\"Extra_task_1_W07-2_Further_loop_optimization\"><\/span>Extra task 1 [W07-2]: Further loop optimization<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<p>The algorithm used initially can be improved upon even further. Initial design doesn&#8217;t detect if the array gets sorted earlier. This can however be detected easily and the sorting process can be stopped.<\/p>\n<ul>\n<li>If the array gets sorted earlier than the last iteration of the outer loop, stop the sorting. Avoid doing unnecessary work!<\/li>\n<li>Hint: think of what statements are being executed in a situation where the array is still being sorted, that will no longer be executed once it is sorted. Detect it and stop the sorting.<\/li>\n<li>During defense: explain which kind of data order benefits from this algorithm. Demonstrate that your algorithm indeed works!<\/li>\n<\/ul>\n<h3><span class=\"ez-toc-section\" id=\"After_the_class\"><\/span><span id=\"After_the_class,_you_should_be_able_to\" class=\"ez-toc-section\"><\/span><strong>After the class<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li>You should understand what a number base (radix) is<\/li>\n<li>You should recognize the most common numbering systems, including binary and hexadecimal.<\/li>\n<li>You should understand what&#8217;s the difference between a positional and non-positional numbering system.<\/li>\n<li>You should know what a bit, a byte and a nibble are, as well as how many bits are there in a byte or in a nibble<\/li>\n<li>You should understand basic conversion between bases (10 -&gt; 2, 10 -&gt; 16, 10 -&gt; 8, 2 &gt; 10, 2 -&gt; 16, 16 -&gt; 10, 16 -&gt; 2, 8 -&gt; 10)<\/li>\n<li>You should be able to convert between any system positional numbering system and base 10 using the generic conversion algorithm.<\/li>\n<li>You should understand what an integer overflow is, when it happens and how dangerous it can be<\/li>\n<li>You should know that there are a lot of sorting algorithms out there and for a practical application, you need to pick the right one<\/li>\n<li>You should understand, that optimization and faster hardware are important, however they will only have a limited effect compared to a faster algorithm<\/li>\n<li>You should understand what a bubble sort is and be able to write and apply it<\/li>\n<\/ul>\n<h3><span class=\"ez-toc-section\" id=\"Additional_content\"><\/span><strong>Additional content<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h3>\n<h4><span class=\"ez-toc-section\" id=\"Generic_references\"><\/span><strong>Generic references<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h4>\n<ul>\n<li>Khan Academy: Binary and hexadecimal number systems<br \/>\n<a href=\"https:\/\/www.khanacademy.org\/math\/algebra-home\/alg-intro-to-algebra\/algebra-alternate-number-bases\/v\/number-systems-introduction\">https:\/\/www.khanacademy.org\/math\/algebra-home\/alg-intro-to-algebra\/algebra-alternate-number-bases\/v\/number-systems-introduction<\/a><\/li>\n<li>Sorting algorithms animations (compare speed, different input data, algorithms)<br \/>\n<a href=\"https:\/\/www.toptal.com\/developers\/sorting-algorithms\">https:\/\/www.toptal.com\/developers\/sorting-algorithms<\/a><\/li>\n<li>15 and Hexadecimal &#8211; Numberphile<br \/>\n<a href=\"https:\/\/www.youtube.com\/watch?v=9xbJ3enqLnA\">https:\/\/www.youtube.com\/watch?v=9xbJ3enqLnA<\/a><\/li>\n<li>Binary Addition &amp; Overflow &#8211; Computerphile<br \/>\n<a href=\"https:\/\/www.youtube.com\/watch?v=WN8i5cwjkSE\">https:\/\/www.youtube.com\/watch?v=WN8i5cwjkSE<\/a><\/li>\n<li>Base Number Jokes Explained &#8211; Numberphile<br \/>\n<a href=\"https:\/\/www.youtube.com\/watch?v=Fmb3TCvlETk\">https:\/\/www.youtube.com\/watch?v=Fmb3TCvlETk<\/a><\/li>\n<li>Integer Overflow<br \/>\n<a href=\"https:\/\/en.wikipedia.org\/wiki\/Integer_overflow\">https:\/\/en.wikipedia.org\/wiki\/Integer_overflow<\/a><\/li>\n<li>Positional notation<br \/>\n<a href=\"https:\/\/en.wikipedia.org\/wiki\/Positional_notation\">https:\/\/en.wikipedia.org\/wiki\/Positional_notation<\/a><\/li>\n<li>Sorting Algorithms<br \/>\n<a href=\"https:\/\/en.wikipedia.org\/wiki\/Sorting_algorithm\">https:\/\/en.wikipedia.org\/wiki\/Sorting_algorithm<\/a><\/li>\n<li>Bubble sort<br \/>\n<a href=\"https:\/\/en.wikipedia.org\/wiki\/Bubble_sort\">https:\/\/en.wikipedia.org\/wiki\/Bubble_sort<\/a><\/li>\n<li>Radix<br \/>\n<a href=\"https:\/\/en.wikipedia.org\/wiki\/Radix\">https:\/\/en.wikipedia.org\/wiki\/Radix<\/a><\/li>\n<\/ul>\n<h4><span class=\"ez-toc-section\" id=\"Integer_overflow_in_real_life\"><\/span><strong>Integer overflow in real life<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h4>\n<ul>\n<li>Integer overflow in GPS:<br \/>\n<a href=\"https:\/\/en.wikipedia.org\/wiki\/GPS_Week_Number_Rollover\">https:\/\/en.wikipedia.org\/wiki\/GPS_Week_Number_Rollover<\/a><\/li>\n<li>Gangnam Style overflows INT_MAX, forces YouTube to go 64-bit<br \/>\n<a href=\"https:\/\/arstechnica.com\/information-technology\/2014\/12\/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\/<\/a><\/li>\n<li>Computerphile &#8211; How Gangnam Style Broke<br \/>\n<a href=\"https:\/\/www.youtube.com\/watch?v=vA0Rl6Ne5C8\">https:\/\/www.youtube.com\/watch?v=vA0Rl6Ne5C8<\/a><\/li>\n<li>Overflow in the stock market: <a href=\"https:\/\/www.theregister.com\/2021\/05\/07\/bug_warren_buffett_rollover_nasdaq\/\">https:\/\/www.theregister.com\/2021\/05\/07\/bug_warren_buffett_rollover_nasdaq\/<\/a><\/li>\n<li>Integer overflow in calendars (Y2K):<br \/>\n<a href=\"https:\/\/en.wikipedia.org\/wiki\/Year_2000_problem\">https:\/\/en.wikipedia.org\/wiki\/Year_2000_problem<\/a><\/li>\n<li>Nuclear Gandhi:<br \/>\n<a href=\"https:\/\/en.wikipedia.org\/wiki\/Nuclear_Gandhi\">https:\/\/en.wikipedia.org\/wiki\/Nuclear_Gandhi<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Lab materials Slides: Numerical systems Slides: Sorting Algorithm: https:\/\/blue.pri.ee\/ttu\/programming-i\/algorithm-tasks\/#Algorithm_6_Finding_the_lowest_possible_number_base Tasks This lab has one base task, which can be extended by one extra task. Lab task [W07-1]: Bubble sort In this lab task you will implement a bubble sorting algorithm that will sort an array of numbers entered by the user. Requirements User is asked &hellip; <a href=\"https:\/\/blue.pri.ee\/ttu\/labs\/7-lab-sorting\/\" class=\"more-link\">Loe edasi <span class=\"screen-reader-text\">PR1EN7: Sorting<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[75,77],"tags":[],"class_list":["post-5464","post","type-post","status-publish","format-standard","hentry","category-labs","category-pr1_en"],"_links":{"self":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts\/5464","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/comments?post=5464"}],"version-history":[{"count":9,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts\/5464\/revisions"}],"predecessor-version":[{"id":11540,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts\/5464\/revisions\/11540"}],"wp:attachment":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/media?parent=5464"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/categories?post=5464"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/tags?post=5464"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}