Solved

How does this Python sort work?

Posted on 2016-11-28
5
86 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
  • 2
  • 2
5 Comments
 
LVL 12

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 16

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 16

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

Does Powershell have you tied up in knots?

Managing Active Directory does not always have to be complicated.  If you are spending more time trying instead of doing, then it's time to look at something else. For nearly 20 years, AD admins around the world have used one tool for day-to-day AD management: Hyena. Discover why

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
How to create exe using python? 2 50
Any decent scenery blocks for my RTS 6 87
How to generate a random directed graph 5 62
Python 3.5: SQL Results to CSV dump 8 57
Less strange, but still introduction This introduction was added (1st August, 2011) to reflect some reactions.  Firstly, the term basics in the title of the article...  As any other word, it is a symbol with meaning attached to the word by some a…
Flask is a microframework for Python based on Werkzeug and Jinja 2. This requires you to have a good understanding of Python 2.7. Lets install Flask! To install Flask you can use a python repository for libraries tool called pip. Download this f…
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 modules and packages in Python. Every Python file is a module, ending in the suffix: .py: Modules are a collection of functions and variables.: Packages are a collection of modules.: Module functions and variables are accessed us…

777 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