I have to write a program that takes in several rows of input, then sorts them based on several command line arguments given. The row can be of variable length, and each item on the row is separated by a comma, like this:
a,b,c,12,3
d,e,f,4,56
a,g,h,8,5
What the program has to do is sort the input on certain columns based on the argument given. That's simple, but the hard part is I also have to be able to sort on multiple arguments.
for example, the command line arguments 1,4 (both ascending) would output this:
a,g,h,8,5
a,b,c,12,3
d,e,f,4,56
So it sorts based on the first column, then the 4th column. I'm not sure how to sort something, then only sort the conflicting elements using the next argument without resorting the entire column. I'm currently storing the input in a vector of vectors.
As a side note, I've read some similar questions, but all of them only have a set number of things to sort by. For this program, the number of items per row can be anywhere from 1 upwards, and the number of arguments to sort by can be variable too.
First of all, use std::sort() which works with iterators first, last as input.
Then, use recursion. Recursion is key to your solution.
For each argument, i.e. sorting criterion C_i, you have one recursion level R_i. Within each recursion level R_i, you have two steps:
- Sort the given data range according to criterion C_i.
- Loop through the data range. Whenever the value C_i changes, call the next recursion level R_{i+1} with arguments:
- first: iterator to the last change, or, beginning of the range
- last: iterator to the current element (the first element with changed C_i)
- reference/pointer to the criterion list and i+1
That's it!
Discussion of this solution:
- Due to the iterators, this method is efficient, as the underlying data structure need not be re-initialized, copied around, etc.
- You need to write a custom comparator functor that is initialized with i and will always compare according to element i of a vector.
- It is debatable what is faster: doing one grand sort that has to go through all sorting criteria in every comparison, or sorting multiple times, as in my approach, and only checking one criterion each.
- In this solution a lot of vectors are swapped. However this is not a problem, as std::vector swaps are cheap.
