Solved

How does this Python sort work?

Posted on 2016-11-28
5
19 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

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

The really strange introduction Once upon a time there were individuals who intentionally put the grass seeds to the soil with anticipation of solving their nutrition problems. Or they maybe only played with seeds and noticed what happened... Som…
"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 …
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 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…

706 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

Need Help in Real-Time?

Connect with top rated Experts

14 Experts available now in Live!

Get 1:1 Help Now