Last Updated: 8 Jul, 2022

Sort The Tuples

Easy

Problem statement

You are given an array of tuples ‘ARR’ of length ‘N’. All the tuples are of length ‘L’. Sort the tuples in non-decreasing order by the last element of tuples. If the last element of two tuples are equal then the tuple with the smallest index should be placed first.

Note: The length of all the tuples will be the same.

Example:

Input: ‘N’ = 3, ‘L’ = 2,  ‘ARR’ = [(1, 1), (5, 3), (8, 2)]. 

Output: [(1, 1), (8, 2), (5, 3)].

The last values of each type are (1, 3, 2). Sorting them in non-decreasing order we get (1, 2, 3). Hence the final result is [(1, 1), (8, 2), (5, 3)].

Input Format :

The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains two integers ‘N’ and ‘L’  where ‘N’ denotes the length of the array ‘NUMS’ and ‘L’ denotes the length of the tuples.

The next ‘N’ lines of each test case contain ‘N’ tuples of integers.

Output format :

For each test case, you don’t need to return anything just return the resultant array.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^5
Sum of total number of integers <= 10^5
1 <= ARR[i].length <= 1000

Time Limit: 1 sec

Solve now

Approaches

01 Approach

In the naive approach, we can use bubble sort. Iterate over each element of the array then run a second loop from the starting element and swap the adjacent tuples if the last element of the first tuple is greater than the last element of the second tuple.

The steps are as follows:-

Function sortTuples(vector<vector<int>>& arr):

Run a loop from 'i'=0 to 'N' -1:
- Run a loop from 'j' = 'i'+1 to 'N'-‘i'-2:
  - If the last element of 'j'th tuple is greater than the last element of the 'j'+1th tuple then swap the tuples.

Solve now

02 Approach

In this approach, we can modify the already existing in-built sorting function( stable_sort ) by writing our own compare function. Declare a function compare which takes two tuples as arguments and compares them according to their last element.

The steps are as follows:-

Function compare(vector<int>&a, vector<int>&b):

Define the comparison between two tuples as: if the last element of the first tuple is smaller or equal return true else return false.

Function sortTuples(vector<vector<int>>& arr):

Call the stable_sort function with custom compare function.

Solve now