PrioritySort

SRM 141 · 2003-04-10 · by schveiguy

Class Name: PrioritySort

Return Type: String[]

Method Name: sort

Arg Types: (vector<string>, vector<int>)

Problem Statement

Many times, when viewing a table of values, it is necessary to sort the table rows based on one field first, and another field second, and another field third, and so on. A phone book is a good example of a priority sorted list. The entries are sorted first by last name, and second by first name, and third by address.

You will be given a String[] values, which contains a list of table rows. Each row is a list of single-digit non-negative integers separated by single spaces. You will also be given a int[] priorities, which is a list of columns in decreasing priority. The return value should be the same table sorted by the columns given in priorities. The elements should be sorted in increasing order according to the first column in priorities. Then the elements which have the same value in the first priority column should be sorted according to the second priority column. Then elements that have the same values for the first two priority columns should be sorted according to the third, etc.

priorities will contain a 0-based list of column numbers. For example, if priorities were {2, 0, 1}, you would sort the elements first by column 2 (the third column), then by column 0 (the first column), and finally by column 1 (the second column).

Notes

In the case that the given priority columns all tie for two particular elements, the order of those elements should be the order in which they were originally passed in.

Constraints

values will have between 1 and 50 elements, inclusive.
Each element in values will consist only of the characters '0' - '9' and the space character.
Each element of values will have between 1 and 49 characters, inclusive.
All elements of values will have the same length.
Each element of values will consist of single character integers separated by exactly one space.
There will be no leading or trailing spaces in each element of values
priorities will have between 1 and n elements inclusive, where n is the number of integers in each element of values.
Each element in priorities will be between 0 and n - 1 inclusive, where n is the number of integers in each element of values.
There will be no repeated elements in priorities.

Examples

{"1 2 4", "1 4 3", "1 2 3"}
{0}
Returns: { "1 2 4",  "1 4 3",  "1 2 3" }

Since all the strings have the same value for the 0 index, the list is already sorted.

{"1 2 4", "1 4 3", "1 2 3"}
{0,1}
Returns: { "1 2 4",  "1 2 3",  "1 4 3" }

Same example, but now the second column is the second priority. Here, the second and third elements are out of order because of the '2' in the third element and the '4' in the second element.

{"1 2 4", "1 4 3", "1 2 3"}
{0,1,2}
Returns: { "1 2 3",  "1 2 4",  "1 4 3" }

Same example, but now all three columns have a priority assigned to them. Since the first and third elements have the same 0 and 1 column, they are sorted according to the last column.

{"1 2 4", "1 4 3", "1 2 3"}
{2,1,0}
Returns: { "1 2 3",  "1 4 3",  "1 2 4" }

Same example, but with the priorities in reverse. Since the last two elements have the lowest third column, they come first. Since the third element has a lower second column, it comes before the second element.

{"3","2","3"}
{0}
Returns: { "2",  "3",  "3" }

Submissions are judged against all 53 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PrioritySort with a public method vector<string> sort(vector<string> values, vector<int> priorities) · 53 test cases · 2 s / 256 MB per case