Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

How does this Python sort work?

Posted on 2016-11-28
5
Medium Priority
?
137 Views
Last Modified: 2016-11-29
Someone posted a solution on HackerRank to a sorting problem.  The challenge is simple, return a sorted string in this order: lowercase, uppercase, odd nums, even nums, and the solution looks like:

  abc = sorted(instring, key=lambda c: (-ord(c) >> 5, c in '02468', c))

I don't understand how the syntax in the lambda works.  It seems the lambda is returning a tuple, but how is that being interpreted as the key for the sort?  At first I thought maybe it was an alternative syntax for the ternary operator, but it just returns the tuple.

How does this work?
0
Comment
Question by:ugeb
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
  • 2
5 Comments
 
LVL 13

Expert Comment

by:Jeff Darling
ID: 41904688
This isn't an entire solution, but it should help reveal a couple of things.

The ordinal value of the character after bit shift returns a number.  By taking the negative value, the sort order goes in the reverse.  This is because in the ASCII coding system, uppercase normally comes before lowercase.

ascii chart
sample code

instring = '123456ABCabc'

abc = sorted(instring, key=lambda c: (-ord(c) >> 5, c in '02468', c))

print("Here it is sorted as requested!")

for c in abc:
    print( "%s -> %d " % (c, -ord(c) >> 5))

Open in new window


output of above

Here it is sorted as requested!
a -> -4 
b -> -4 
c -> -4 
A -> -3 
B -> -3 
C -> -3 
1 -> -2 
3 -> -2 
5 -> -2 
2 -> -2 
4 -> -2 
6 -> -2 

Open in new window

0
 
LVL 11

Author Comment

by:ugeb
ID: 41904710
Thank you, but actually my confusion is in how the tuple is being used.  We have a character passed to the lambda, and instead of -1, 0 or 1 being returned, we have a tuple being returned.

How does the sort function use a tuple as the key as in the above?
0
 
LVL 17

Accepted Solution

by:
gelonida earned 2000 total points
ID: 41904998
the lambda function (also called the sort's key function) transform your character into a sort key (in this case a tuple with three values).
then each character as if it had the value of this tuple.

Items will be sorted by the first value of the tuple if values are identical it will then sort by the second item of the tuple and if the second items are identical by the third tuple item.

It's a little like a phone book where you first sort by family name and if the family name is identical by the first name.

So first you try to sort by ord(c) >> 5 (which is -4 for lower case characters,  -3 for uppercase ones, -2 for other characters)
then it sorts by by the boolean value c in '02468' (False values first, then True values) so non digits first, then digits
then it sorts just by the normal characer order.

for c in instring:
     print "%s -> %2d %5s %s" % (c, -ord(c) >> 5, c in '02468', c)

1 -> -2 False 1
2 -> -2  True 2
3 -> -2 False 3
4 -> -2  True 4
5 -> -2 False 5
6 -> -2  True 6
A -> -3 False A
B -> -3 False B
C -> -3 False C
a -> -4 False a
b -> -4 False b
c -> -4 False c

Open in new window


You can look at python's documentation explaining the sorting (and sorting by key functions)
https://docs.python.org/2/howto/sorting.html
1
 
LVL 11

Author Closing Comment

by:ugeb
ID: 41905025
Thank you.  I thought it was probably something like that but my tests weren't giving expected results.  Got it now, though.

I did a number of web searches and checked the docs as well, but I could find no mention of this feature where the key can return a tuple used in hierarchical sorting.  Where is that documented?

Thanks again.
0
 
LVL 17

Expert Comment

by:gelonida
ID: 41905309
Well you're right.
It's not  that easy to find the information in the doc as it is mentioned rather 'implicitly'.

The documentation of the sort function mentions, that the key parameter allows to pass a key function, that creates for each  objects you want to sort into a key value, that will be used to determine the objects ordering.

So the key function can return whatever object has comparison functions implemented, (any object, that implements the operators <, > and ==)
and tuples and lists do implement comparison operators.

Then in the part of the documentation, that describes data structures you can see how tuples can be compared.
https://docs.python.org/3.3/tutorial/datastructures.html

You might also want to look at a small article on the python wiki.
https://wiki.python.org/moin/HowTo/Sorting
0

Featured Post

Enroll in September's Course of the Month

This month’s featured course covers 16 hours of training in installation, management, and deployment of VMware vSphere virtualization environments. It's free for Premium Members, Team Accounts, and Qualified Experts!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

A set of related code is known to be a Module, it helps us to organize our code logically which is much easier for us to understand and use it. Module is an object with arbitrarily named attributes which can be used in binding and referencing. …
The purpose of this article is to demonstrate how we can upgrade Python from version 2.7.6 to Python 2.7.10 on the Linux Mint operating system. I am using an Oracle Virtual Box where I have installed Linux Mint operating system version 17.2. Once yo…
Learn the basics of lists in Python. Lists, as their name suggests, are a means for ordering and storing values. : Lists are declared using brackets; for example: t = [1, 2, 3]: Lists may contain a mix of data types; for example: t = ['string', 1, T…
Learn the basics of while and for loops in Python.  while loops are used for testing while, or until, a condition is met: The structure of a while loop is as follows:     while <condition>:         do something         repeate: The break statement m…
Suggested Courses

722 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question