Määratlemata

7. lab: Sorting

Lab materials

Tasks

This lab has one task which can be extended by 2 extra tasks.

Lab task: 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, they 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! Displaying the numbers in the opposite order does not require sorting!
  • You are to create 4 functions within 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 the question: You can observe both the count of comparisons and swaps. Which one will be reduced by our optimization 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 already start reusing the functions from last week. Copy the ones that suit this program over and adjust them as needed for this task. Then just add the function call.
  • 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: 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!

Extra task 2: matrix sort

In this part you will jump a little bit ahead and have to familiarize yourself with 2-dimensional arrays.

  • Solve this task as a separate program. Use the original code as a template to build upon. Keep the original, you will need the functions later on!
  • You are permitted to solve this task without using functions as we haven’t covered passing 2-d arrays to functions.
  • Instead of a 1-d array, you will need to sort a 5 x 5 matrix.
  • Sorting is performed line-by-line (independently)
  • Matrix must be initialized. Use the following matrix as your test data.
Sorted matrix
Hint

Wish to use the sorting function that you just did within the base task? In C, you can pass rows of a matrix to a function (in reality it it’s a bit more complex, but it serves our purpose). Pass it to the sort function as follows:
SortArray(numbers[rowIndex], rowLength); This way your code will look a lot cleaner.

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