Solved

How does this Python sort work?

Posted on 2016-11-28
5
116 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 500 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 June's Course of the Month

June's Course of the Month is now available! Every 10 seconds, a consumer gets hit with ransomware. Refresh your knowledge of ransomware best practices by enrolling in this month's complimentary course 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

"The time has come," the Walrus said, "To talk of many things: Of sets--and lists--and dictionaries-- Of variable kinks-- And why you see it changing not-- And why so strange are strings." This part describes how variables and references (see …
Dictionaries contain key:value pairs. Which means a collection of tuples with an attribute name and an assigned value to it. The semicolon present in between each key and values and attribute with values are delimited with a comma.  In python we can…
Learn the basics of if, else, and elif statements in Python 2.7. Use "if" statements to test a specified condition.: The structure of an if statement is as follows: (CODE) Use "else" statements to allow the execution of an alternative, if the …
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…

734 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