CODEWITHSUNDEEP
algorithmsorting
Thiloshon Nagarajah
Thiloshon Nagarajah

Reputation: 131

Find sorted order in table

I am given a table with three columns and have to find the order of columns used to sort. It can be column1 was used to sort first and column2 was used to break ties and then column3. or else it can be, column3 was used to sort first, column1 to break tie and so on.

This is in Java so i can store the values in array. But just idea itself is enough, i can implement. Is there a Algorithms paradigm related to this usecase? Any ideas are appreciated.

Edit: Example

Say, Ex 01

Movie = ["inception", "inception", "memento"]
rating = [5, 8, 7]
bo = [700, 652, 458]

Here sorted order is: movie, rating. There is no tie in rating so BO was not used in sorting.

Ex 02

Movie = ["inception", "inception", "memento", "memento", "memento"]
rating = [9, 8, 7, 6, 9]
bo = [652, 700, 458, 555, 555]

Here the sorted order is movie, bo, rating. BO is used to break the tie in movie and rating is used to break the tie in BO.

Upvotes: 1

Views: 376

Answers (2)

Yiğit Aras Tunalı
Yiğit Aras Tunalı

Reputation: 428

Well first thing that comes to my mind is; Scanning through the rows to find a sorted row. If this said sorted row has no duplicates it means this row was sorted by its own values and other rows weren't used. If it has duplicate elements you take the interval of duplicate elements and check other rows to see if the same interval in any of them is sorted. The row which has the sorted interval is used as a tie breaker. If that second row's interval which was used to sort has duplicates then the third row is definitely used for the last tie break.

Upvotes: 1

Dave
Dave

Reputation: 9065

Check each column for adjacent unordered pairs. The first column of the sort will have none of these. The others might also, in which case you have no way of telling which was the first sort column.

If you can identify a first sort column, identify the second by checking both of the other columns in the same way, but only for sets of identical values in the first sort column (i.e., where the second column of the sort has a chance to affect anything. At least one of the two remaining columns will have no adjacent unordered pairs (with the same element from the first column). If just one does, then you've found the second column, otherwise you can't.

Upvotes: 1

Related Questions