Labs, Pr1_en

PR1EN7: Sorting

Lab materials

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 for 5 integers, that are stored in an array
  • Array is to be sorted using the bubble sort algorithm
  • You must optimize the loops in such a way that it skips the redundant comparison operations – just as was shown in the slide! Make sure to optimize both the inner and the outer loop lengths.
  • Count and show how many times the numbers were compared by the algorithm. If you count exactly 10, the optimizations are likely correct.
  • Display the sorted array in an ascending order
  • Display the sorted array in the descending order
  • You are allowed to sort the array only once during the program!
  • You are to create four functions to solve the base task (listed below)
  • Reminders!
    • Variables lowerCamelCase
    • Functions  UpperCamelCase
    • Macros  SCREAMING_SNAKE_CASE
    • Magical numbers must be replaced with macros
    • Array length must always be passed to the function

Answer this question: You can observe both the count of comparisons and swaps. Which one will be reduced by limiting the loops and why?

Create the following functions

Implement a total of 4 functions in your code

  • For reading the numbers
  • For sorting the array
  • Two functions for displaying the array
Hints
  • You can reuse functions from the tasks you completed previously
  • 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 – we typically don’t want side effects for our functions.
Test 1: Reverse order

This is the worst case scenario for bubble sort. All numbers are sorted in the opposite order to what they need to be.

Test 2: Random order

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.

Extra task 1 [W07-2]: Further loop optimization

The algorithm used initially can be improved upon even further. Initial design doesn’t detect if the array gets sorted earlier. This can however be detected easily and the sorting process can be stopped.

  • If the array gets sorted earlier than the last iteration of the outer loop, stop the sorting. Avoid doing unnecessary work!
  • 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.
  • During defense: explain which kind of data order benefits from this algorithm. Demonstrate that your algorithm indeed works!

After the class

  • You should understand what a number base (radix) is
  • You should recognize the most common numbering systems, including binary and hexadecimal.
  • You should understand what’s the difference between a positional and non-positional numbering system.
  • 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
  • You should understand basic conversion between bases (10 -> 2, 10 -> 16, 10 -> 8, 2 > 10, 2 -> 16, 16 -> 10, 16 -> 2, 8 -> 10)
  • You should be able to convert between any system positional numbering system and base 10 using the generic conversion algorithm.
  • You should understand what an integer overflow is, when it happens and how dangerous it can be
  • 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
  • You should understand, that optimization and faster hardware are important, however they will only have a limited effect compared to a faster algorithm
  • You should understand what a bubble sort is and be able to write and apply it

Additional content

Generic references

Integer overflow in real life