Tutorial : STL Sort 2 ( Setting Sorting Criteria ) timer 2s memory 1024MB

The previous problem covered the basic usage of the sort function.

Now, we will try a slightly more difficult sort.

from functools import cmp_to_key

# left < right -> return negative number
# left == right -> return 0
# left > right -> return positive number (swap when sorting)
def comp(left, right):
    if  left[1] != right[1]:
        return -1 if left[1] < right[1] else 1
    if  left[0] != right[0]:
        return -1 if left[0] < right[0] else 1
    return 0

A = [ ("Bob", 15), ("Alice", 15), ("Ellie", 13) ]
A.sort(key = cmp_to_key(comp))

def priority(x):
    return ( x[1], x[0] )

A = [ ("Bob", 15), ("Alice", 15), ("Ellie", 13) ]
A.sort(key = priority)

<Quiz>

Let's sort the integers in the array "based on the digit in the ones place."

If there are multiple numbers with the same digit in the ones place, sort them "based on their magnitude."

In other words, the 1st priority for sorting is the "digit in the ones place", and the 2nd priority is the "magnitude".

For example, we want array A to be sorted as follows.

As you move to the right in array A,

the digit in the ones place increases, ( 1st priority sorting criterion )

and those with the same digit in the ones place are sorted based on their magnitude. ( 2nd priority sorting criterion )

Let's understand by looking at the code below.

#include <algorithm>
using namespace std;

// Left : The number on the left in the array
// Right : The number on the right in the array
bool comp ( int Left , int Right ){
    // If the digits in the ones place are different?
    // 1st priority sorting criterion: Compare by the digit in the ones place
    if((Left % 10) != (Right % 10)){ 
        return (Left % 10) < (Right % 10);
    }
    // If the digits in the ones place were the same? 
    // 2nd priority sorting criterion: Compare by magnitude
    return Left < Right;
}

int main(){
    int i;
    int A[7] = {16, 28, 8, 6, 3, 26, 83};
    sort( A + 0 , A + 7 , comp); //  A = [ 3, 83, 6, 16, 26, 8, 28 ]
}

Looking at the main function,

one more argument is added after the sort function. ( sort( A + 0 , A + 7 , comp ); )

The bool type comp function added at the end takes two numbers, compares them based on the sorting criteria set by the user, and returns the result.

A way to understand this intuitively is as follows.

Looking at the figure, you can see that "the digit in the ones place increases as you move to the right" in the array.

It's easy to understand if you name the two numbers received in the comp function Left and Right.

( Other variable names are possible. They were named this way just to help understanding. )

Left is the number on the left in the array, and Right is the number on the right in the array.

Since the digit in the ones place should increase as you move to the right, the digit in the ones place of Right must be larger than that of Left.

Therefore, this code is written inside the comp function.

return (Left % 10) < (Right % 10);

Now, you just need to put in the 1st and 2nd priority sorting criteria.

The 1st priority sorting criterion is the "digit in the ones place".

In other words, if the digits in the ones place of Left and Right are different, the two are compared based on the "digit in the ones place" unconditionally.

If the digits in the ones place of the two are the same, then they are compared based on the 2nd priority sorting criterion, "magnitude".

Therefore, the final comp function is as follows. There are comments explaining this in the first code, so read them carefully.

It is important to understand this content perfectly before moving on.

If you don't understand even after reading it several times, actively ask the teachers around you.

bool comp ( int Left , int Right ){
    if((Left % 10) != (Right % 10)) return (Left % 10) < (Right % 10);
    return Left < Right;
}

<Application Problem>

Input N three-digit integers and sort them in ascending order based on:

1st Priority: Digit in the ones place

2nd Priority: Digit in the tens place

3rd Priority: Digit in the hundreds place