Practical Class #04 - Sorting
(14/10 to 18/10)
Exercises for submission
In what concerns the continuous evaluation solving exercises during the semester, the exercises you can submit in this class are:
Submission Deadline: November 2nd(submit to AED's Mooshak)
You are encouraged to talk to the professor and to your colleagues if you have difficulties. However, any more direct help you have received from other colleagues should be acknowledged in the comments of the code you submit.
After the deadline the problems will still be available on Mooshak, but the submissions will not count towards your grade.
Each class is worth 10 per cent of the grade for this component. As there will be 11 classes with submissions, you can get full marks even if you haven't done everything.
For a problem to count, you have to get all the tests right (i.e. accepted). Even if you solve all the problems, the maximum in a single class is 100 per cent.
it is guaranted that the main exercises on each class will sum to at least 100% of the class grade.
Lectures Content
This class is about sorting. It is therefore convenient that you know what was discussed on the lectures:
1. Using the sort function of C++
(the goal of this exercise is for you first to test a basic example of sorting in C++ and then use that knowledge to submit a problem)
- A sort example
Start by downloading the sort_example.cpp file. Open on your editor, understand it and then compile and execute it. You should have the following output:
Before sorting: 33 4 28 18 15 2 8 17 42 39
After sorting: 2 4 8 15 17 18 28 33 39 42
Have a look at the documentation about the function sort to see how cppreference explains to use the function, how it gives example code and how it states the time complexity: \(O(N \log N)\) comparisons for sorting \(N\) elements.
Notice how the default behavior of sort is to sort in increasing order using the natural comparison of the elements (experiment changing the vector from int to other types such as double, char or string, changing the stored values, and see what happens).
Note also that sort is not stable, that is, it does not guarantee that in case of a tie it keeps the initial order. However, C++ also has stable_sort, in case you need it.
For other exercises you will also need to understand how you could "tell" sort to use another order, but for now what you know is enough to solve your first Mooshak problem in this class 🙂
- Your first sorting problem
For this exercise you will be solving the problem [AED012] Game Tournament.
Desired time complexity: \(O(N \log N)\)
Read the problem statement and understand what it is asking.
In this case you want to compute the top-\(K\) values of a set of (distinct) elements. This problem becomes much easier if the values are sorted right?
You just need to read the values to a vector, sort it (as on the previous example) and then print the first \(K\) values.
Assuming you simply used sort without supplying any comparator function, the values will be sorted in increasing order. But that is not a problem since you can simply print the last \(K\) values (starting from the last). Et voilà, you should have your first Accepted!
2. Using a Custom comparator
- An example of sort with a custom comparator
Start by downloading the custom_sort_example.cpp file and the example input contained in persons.txt. Open on your editor, understand it and then compile and execute it, feeding the program with the input.
Note: if you are running the code on a shell and your executable is called custom_sort_example, then running the command ./custom_sort_example < persons.txt will execute the code giving the contents of persons.txt as its standard input.
Notice how the function comparePerson is defined and how this connects with sort. Try to change this comparator function to make it sort in a different order. For instance, can you change so that in case of a tie the names comes in decreasing lexicographical order? And what about sorting by decreasing age? Don't forget to test your program to see if it is working and doing what you expect.
Two more notes before going to your first custom sorting Mooshak problem:
- We used a comparator function that we defined outside of the sort in the code, but we could have also opted to use an anonymous function given directly as an argument in the sort call using the concept of lambda expressions.
Check the following code for an equivalent version of the previous example but using a lambda expression: lambda_sort_example.cpp
- In this example we used a simple struct to store a person (which has two attributes: name and age). We could have also used a C++ class, which besides storing attributes can also add functionality, but here we simply want to aggregate attributes and we are also focusing on the core contents of this lesson. Classes and a more object oriented approach will be explored on other practical classes.
- A problem that needs a custom comparator
For this exercise you will be solving the problem [AED013] Counting the Bits.
Desired time complexity: \(O(N \log N)\)
Let's now put to work your knowledge of sorting with a custom comparator function.
Start, as you always should, by reading the problem statement and understanding what it is asking.
Our suggestion is that you first create a function int countBits(int n) that receives an integer n and computes the number of 1 bits in its representation. Can you see how to do it?
Don't forget to test your implementation before advancing. For instance, here are some example calls and their correct outputs:
- countBits(15) should return 4
- countBits(7) should return 3
- countBits(3) should return 2
- countBits(2) should return 1
After doing this, what's left to solve the problem? You simply need to read all integers and sort with a custom comparator function that implements the desired order. You can for instance use the previous example as a blueprint and change both the struct (what should the attributes be?) and the comparator function to match what the problem asks.
3. Solving a problem that needs sorting as a basic building block
For this exercise you will be solving the problem [AED014] Computer Lab.
Desired time complexity: \(O(N \log N)\)
Read the problem statement and understand what it is asking. Can you think on how you could use sorting to help solve the problem? Try to think about the problem by yourself before seeing the hints. 😉
Hints
- Imagine you sort in increasing order all arrival and leaving times (which the statement guarantees are distinct)
- Now imagine you traverse the times in increasing order, as if you are "moving" though time, keeping a variable count with the current number of students in the lab:
. At the beginning count = 0
. If you pass an arrival time, there is one more person in the lab, so you should increase count by one
. If you pass a leaving time, there is one less person in the lab, so you should decrease count by one
. If you keep track of the maximum value count reaches, you have the desired answer!
4. Sorting everywhere!
For this exercise you will be solving the problem [AED015] Anagrams.
Desired time complexity: \(O(N \log N)\)
Read the problem statement and understand what it is asking.
- Checking for anagrams
Let's first concentrate on a simpler task: how can we determine if two words are anagrams? If you sort their contents, then they should produce the same word!
For instance, sorting the letters of "algorithm" and "logarithm" both produce the string "aghilmort".
More generally, for this problem, to check if two phrases are anagrams we could simply check if their sorted versions are the same, after we removed all the spaces and transformed all the letters to their lower case version.
Put this idea into practice by implementing a function string sortPhrase(const string & s) that receives a string s and returns a new string that corresponds to a sorted version of the initial string, without any spaces and with all letters converted to their lowercase version.
Don't forget to test your implementation before advancing. For instance, here are some example calls and their correct outputs:
- sortPhrase("seat") should return "aest"
- sortPhrase("logarithm") should return "aghilmort"
- sortPhrase("I am Lord Voldemort") should return "addeillmmooorrtv"
- Solving the problem
With the previous function implemented the problem is now much easier, right? Try to think about the problem by yourself before seeing the hints.
Hints
- Read all lines x and store them on a vector v the sortPhrase(x) versions
- To read a line you can use getline. For instance, getline(cin, x) will read a line from cin and store it on string x
- If you sort this vector v then all anagram classes will be next to each other! For instance, for the example input, the vector would be:
aeeglmnnt
aaeeglmnnt
acinoorrsuv
acinoorrsuv
addeillmmooorrtv
addeillmmooorrtv
aest
aest
aest
aest
aghilmort
aghilmort
eegmorrst
eeikmnorstwy
eeikmnorstwy
eilnst
eilnst
eilnst
ginorst
orst
- The classes are simply the colors in the listing. You can just traverse the sorted vector and whenever you find a repetition you increment a counter (taking care to not overcount when a class of anagrams has more than two phrases)
Extra Exercises for Consolidating your knowledge [extra]
5. Football Table
For this exercise you will be solving the problem [AED016] Football Table.
Desired time complexity: \(O(N \log N)\)
Read the problem statement and understand what it is asking. Implement, test and submit on Mooshak.
This is just a problem for you to test again that you know how to implement a custom comparator, right? 😁
6. Chocolate Boxes
For this exercise you will be solving the problem [AED017] Chocolate Boxes.
Desired time complexity: \(O(N \log N)\)
Read the problem statement and understand what it is asking. Implement, test and submit on Mooshak.
Can you think on how you could use sorting? Try to think about the problem by yourself before seeing the hints.
Hints
- If the values are sorted, is there any option better than using a consecutive sequence of k elements? Can you see why?
- Knowing this, after sorting in \(O(N \log N)\) you simply have to check all possible \(O(N)\) attributions, each one taking \(O(1)\) to check its difference (last value minus the first one)
- For the example input, the sorted version would become 1 4 4 5 5 6 7 9. Since we have K=5 children, our possibilities would be:
1 4 4 5 5 6 7 9 with difference = 5-1 = 4
1 4 4 5 5 6 7 9 with difference = 6-4 = 2 ← this is the best option
1 4 4 5 5 6 7 9 with difference = 7-4 = 3
1 4 4 5 5 6 7 9 with difference = 9-5 = 4
7. Ferris Wheel
For this exercise you will be solving the problem [AED018] Ferris Wheel.
Desired time complexity: \(O(N \log N)\)
Read the problem statement and understand what it is asking. Implement, test and submit on Mooshak.
Can you think on how you could use sorting? Try to think about the problem by yourself before seeing the hints.
Hints
- What is the best option to pair the heaviest child? If it cannot be paired with the lightest kid could it be paired with anyone else?
- We can solve this problem with a greedy approach (you will be talking in the future and on other courses of these types of algorithms):
. Sort the weights in increasing order
. Initialize a variable ans=0 to contain the answer
. Initialize 2 "pointers" l and h to keep track of lightest and heaviest child still not on a cabin
. If the heaviest and the lightest child can pair with each other, then pair them up and increase l by 1, decrease h by 1 and increment ans
. Otherwise, if the heaviest and the lightest child cannot pair, then the heaviest child will sit alone in one cabin: decrease h by 1 and increment ans
. Return the final ans after iterating over all the children
- Beware that, in general, a greedy approach does not always guarantee an optimal solution. However, for this particular problem we could prove that this strategy is correct. Can you see the intuition behind the idea we used?
Challenge Exercise [challenge]
The main idea of the challenge problems is to give you the opportunity of improving your problem solving abilities.
For this exercise you will be solving the problem [AED019] Counting Inversions.
Since this is a challenge, I will not give you any hints, but if
you are stuck just contact @PedroRibeiro on Discord. Feel free to
also contact @PedroRibeiro to discuss your accepted solution.
This problem is all about sorting and you can easily find information about it by searching for it on the web, but try to think for yourself before looking explicitly for hints. Obviously, a "brute force" approach in \(O(N^2)\) is not enough!
Happy coding! 😊