2

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.

PocketSpider
  • 139
  • 1
  • 9
  • It's doable, you just need to provide the write comparison function. Can you provide some source code? – Stephen Lin Mar 03 '13 at 08:45
  • How would you sort `{a,g,h,8,6}` and `{a,g,h,8,5}` by the first and fourth columns? How about `{a,g,h,8,6}` and `{a,g,h}`? – johnsyweb Mar 03 '13 at 08:46
  • @Johnsyweb are you asking me or OP? if I understand correctly, he wants the rows, using column one as the first key, then sorting by column four as the second in the cases where the values in column one are the same. it's not difficult if you use the right data structures and write an `operator<`, even if the number of columns is variable. – Stephen Lin Mar 03 '13 at 08:51
  • I was asking @QuinnMillir. – johnsyweb Mar 03 '13 at 08:52
  • @Stephen Lin I would, but my file server went down today and I lost my current work. – PocketSpider Mar 03 '13 at 08:56
  • @Johnsyweb the sort is required to be stable, so {a,g,h,8,6} and {a,g,h,8,6} would remain in the order they started in. and for the second sets, {a,g,h} would not be included in the sort (or removed from the vector) – PocketSpider Mar 03 '13 at 08:57
  • @QuinnMillir you can use `std::stable_sort` [(docs)](http://en.cppreference.com/w/cpp/algorithm/stable_sort) but you need to learn some STL [(minor caveat)](http://stackoverflow.com/questions/5205491/whats-this-stl-vs-c-standard-library-fight-all-about) – Stephen Lin Mar 03 '13 at 09:03

1 Answers1

1

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:

  1. Sort the given data range according to criterion C_i.
  2. 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.
ypnos
  • 50,202
  • 14
  • 95
  • 141