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
Solved

How does this Python sort work?

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

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

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…
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 strings in Python: declaration, operations, indices, and slicing. Strings are declared with quotations; for example: s = "string": Strings are immutable.: Strings may be concatenated or multiplied using the addition and multiplic…
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…

856 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