HOWTO Release2.7.9 GuidovanRossumandthePythondevelopmentteam Contents 1SortingBasics2KeyFunctions3OperatorModuleFunctions4AscendingandDescending5SortStabilityandComplexSorts6TheOldWayUsingDecorate-Sort-Undecorate7TheOldWayUsingthecmpParameter8OddandEnds December10,2014PythonSoftwareFoundation Email:docs@ 12233345 AuthorAndrewDalkeandRaymondHettingerRelease0.1Pythonlistshaveabuilt-inlist.sort()methodthatmodifiesthelistin-place.Thereisalsoasorted()built-infunctionthatbuildsanewsortedlistfromaniterable.Inthisdocument,weexplorethevarioustechniquesforsortingdatausingPython. 1SortingBasics Asimpleascendingsortisveryeasy:justcallthesorted()function.Itreturnsanewsortedlist:>>>sorted([5,2,3,1,4])[1,2,3,4,5]Youcanalsousethelist.sort()methodofalist.Itmodifiesthelistin-place(andreturnsNonetoavoidconfusion).Usuallyit’slessconvenientthansorted()-butifyoudon’tneedtheoriginallist,it’sslightlymoreefficient. >>>a=[5,2,3,1,4]>>>a.sort()>>>a[1,2,3,4,5] Anotherdifferenceisthatthelist.sort()methodisonlydefinedforlists.Incontrast,thesorted()functioneptsanyiterable. >>>sorted({1:'D',2:'B',3:'B',4:'E',5:'A'})[1,2,3,4,5] 2KeyFunctions StartingwithPython2.4,bothlist.sort()andsorted()addedakeyparametertospecifyafunctiontobecalledoneachlistelementpriortoparisons. Forexample,here’sacase-insensitiveparison: >>>sorted("ThisisateststringfromAndrew".split(),key=str.lower)['a','Andrew','from','is','string','test','This'] Thevalueofthekeyparametershouldbeafunctionthattakesasingleargumentandreturnsakeytouseforsortingpurposes.Thistechniqueisfastbecausethekeyfunctioniscalledexactlyonceforeachinputrecord. monpatternistoplexobjectsusingsomeoftheobject’sindicesaskeys.Forexample: >>>student_tuples=[('john','A',15),('jane','B',12),('dave','B',10), ]>>>sorted(student_tuples,key=lambdastudent:student[2])[('dave','B',10),('jane','B',12),('john','A',15)] #sortbyage Thesametechniqueworksforobjectswithnamedattributes.Forexample: >>>classStudent:def__init__(self,name,grade,age):self.name=nameself.grade=gradeself.age=agedef__repr__(self):returnrepr((self.name,self.grade,self.age)) >>>student_objects=[Student('john','A',15),Student('jane','B',12),Student('dave','B',10), ]>>>sorted(student_objects,key=lambda[('dave','B',10),('jane','B',12), student:('john', student.age)'A',15)] #sortbyage 3OperatorModuleFunctions Thekey-functionpatternsshownabovearemon,soPythonprovidesconveniencefunctionstomakeessorfunctionseasierandfaster.Theoperatormodulehasoperator.itemgetter(),operator.attrgetter(),andstartinginPython2.5aoperator.methodcaller()function.Usingthosefunctions,theaboveexamplesesimplerandfaster:>>>fromoperatorimportitemgetter,attrgetter >>>sorted(student_tuples,key=itemgetter
(2))[('dave','B',10),('jane','B',12),('john','A',15)] >>>sorted(student_objects,key=attrgetter('age'))[('dave','B',10),('jane','B',12),('john','A',15)] Theoperatormodulefunctionsallowmultiplelevelsofsorting.Forexample,tosortbygradethenbyage: >>>sorted(student_tuples,key=itemgetter(1,2))[('john','A',15),('dave','B',10),('jane','B',12)] >>>sorted(student_objects,key=attrgetter('grade','age'))[('john','A',15),('dave','B',10),('jane','B',12)] Theoperator.methodcaller()functionmakesmethodcallswithfixedparametersforeachobjectbeingsorted.Forexample,thestr.count()methodcouldbeusedputemessageprioritybycountingthenumberofexclamationmarksinamessage: >>>messages=['critical!
!
!
','hurry!
','standby','immediate!
!
']>>>sorted(messages,key=methodcaller('count','!
'))['standby','hurry!
','immediate!
!
','critical!
!
!
'] 4AscendingandDescending Bothlist.sort()andsorted()eptareverseparameterwithabooleanvalue.Thisisusedtoflagdescendingsorts.Forexample,togetthestudentdatainreverseageorder:>>>sorted(student_tuples,key=itemgetter
(2),reverse=True)[('john','A',15),('jane','B',12),('dave','B',10)]>>>sorted(student_objects,key=attrgetter('age'),reverse=True)[('john','A',15),('jane','B',12),('dave','B',10)] 5SortStabilityandComplexSorts StartingwithPython2.2,sortsareguaranteedtobestable.Thatmeansthatwhenmultiplerecordshavethesamekey,theiroriginalorderispreserved. >>>data=[('red',1),('blue',1),('red',2),('blue',2)]>>>sorted(data,key=itemgetter
(0))[('blue',1),('blue',2),('red',1),('red',2)] Noticehowthetworecordsforblueretaintheiroriginalordersothat(’blue’,1)isguaranteedtoprecede(’blue’,2). Thiswonderfulpropertyletsyouplexsortsinaseriesofsortingsteps.Forexample,tosortthestudentdatabydescendinggradeandthenascendingage,dotheagesortfirstandthensortagainusinggrade: >>>s=sorted(student_objects,key=attrgetter('age'))>>>sorted(s,key=attrgetter('grade'),reverse=True)[('dave','B',10),('jane','B',12),('john','A',15)] #sortonsecondarykey#nowsortonprimarykey,de TheTimsortalgorithmusedinPythondoesmultiplesortsefficientlybecauseitcantakeadvantageofanyorderingalreadypresentinadataset. 6TheOldWayUsingDecorate-Sort-Undecorate ThisidiomiscalledDecorate-Sort-Undecorateafteritsthreesteps:•First,theinitiallistisdecoratedwithnewvaluesthatcontrolthesortorder. •Second,thedecoratedlistissorted. •Finally,thedecorationsareremoved,creatingalistthatcontainsonlytheinitialvaluesintheneworder. Forexample,tosortthestudentdatabygradeusingtheDSUapproach: >>>decorated=[(student.grade,i,student)fori,studentinenumerate(student_objects >>>decorated.sort() >>>[studentforgrade,i,studentindecorated] #undecorate [('john','A',15),('jane','B',12),('dave','B',10)] Thisidiomworksbecausetuplesparedlexicographically;thefirstitemspared;iftheyarethesamethentheseconditemspared,andsoon. Itisnotstrictlynecessaryinallcasestoincludetheindexiinthedecoratedlist,butincludingitgivestwobenefits: •Thesortisstable–iftwoitemshavethesamekey,theirorderwillbepreservedinthesortedlist. •Theoriginalitemsdonothavetoparablebecausetheorderingofthedecoratedtupleswillbedeterminedbyatmostthefirsttwoitems.Soforexampletheoriginallistcouldplexnumberswhichcannotbesorteddirectly. AnothernameforthisidiomisSchwartziantransform,afterRandalL.Schwartz,whopopularizeditamongPerlprogrammers. Forlargelistsandlistswhereparisoninformationisexpensivetocalculate,andPythonversionsbefore2.4,DSUislikelytobethefastestwaytosortthelist.For2.4andlater,keyfunctionsprovidethesamefunctionality. 7TheOldWayUsingthecmpParameter ManyconstructsgiveninthisHOWTOassumePython2.4orlater.Beforethat,therewasnosorted()builtinandlist.sort()tooknokeywordarguments.Instead,allofthePy2.xversionssupportedacmpparametertohandleuserspecifiparisonfunctions. InPython3,thecmpparameterwasremovedentirely(aspartofalargerefforttosimplifyandunifythelanguage,eliminatingtheconflictbetweenparisonsandthe__cmp__()magicmethod). InPython2,sort()allowedanoptionalfunctionwhichcanbecalledfordoingparisons.Thatfunctionshouldtaketwoargumentstoparedandthenreturnanegativevalueforless-than,returnzeroiftheyareequal,orreturnapositivevalueforgreater-than.Forexample,wecando: >>>defpare(x,y):returnx-y >>>sorted([5,2,4,1,3],cmp=pare)[1,2,3,4,5] Oryoucanreversetheorderparisonwith: >>>defreverse_numeric(x,y):returny-x >>>sorted([5,2,4,1,3],cmp=reverse_numeric)[5,4,3,2,1] WhenportingcodefromPython2.xto3.x,thesituationcanarisewhenyouhavetheusersupplyingparisonfunctionandyouneedtoconvertthattoakeyfunction.Thefollowingwrappermakesthateasytodo: defcmp_to_key(mycmp):'Convertacmp=functionintoakey=function'classK(object):def__init__(self,obj,*args):self.obj=objdef__lt__(self,other):returnmycmp(self.obj,other.obj)<0def__gt__(self,other): returnmycmp(self.obj,def__eq__(self,other): returnmycmp(self.obj,def__le__(self,other): returnmycmp(self.obj,def__ge__(self,other): returnmycmp(self.obj,def__ne__(self,other): returnmycmp(self.obj,returnK other.obj)other.obj)other.obj)other.obj)other.obj) >0==0<=0>=0!
=
0 Toconverttoakeyfunction,justwraptheparisonfunction: >>>sorted([5,2,4,1,3],key=cmp_to_key(reverse_numeric))[5,4,3,2,1] InPython2.7,thefunctools.cmp_to_key()functionwasaddedtothefunctoolsmodule. 8OddandEnds •Forlocaleawaresorting,uselocale.strxfrm()forakeyfunctionorlocale.strcoll()forparisonfunction. •Thereverseparameterstillmaintainssortstability(sothatrecordswithequalkeysretaintheiroriginalorder).Interestingly,thateffectcanbesimulatedwithouttheparameterbyusingthebuiltinreversed()functiontwice: >>>data=[('red',1),('blue',1),('red',2),('blue',2)]>>>assertsorted(data,reverse=True)==list(reversed(sorted(reversed(data)))) •Tocreateastandardsortorderforaclass,justaddtheappropriateparisonmethods: >>>Student.__eq__=lambdaself,>>>Student.__ne__=lambdaself,>>>Student.__lt__=lambdaself,>>>Student.__le__=lambdaself,>>>Student.__gt__=lambdaself,>>>Student.__ge__=lambdaself,>>>sorted(student_objects)[('dave','B',10),('jane','B', other:other:other:other:other:other: self.ageself.ageself.ageself.ageself.ageself.age ==other.age!
=other.ageother.age>=other.age 12),('john','A',15)] Forgeneralparisons,themendedapproachistodefineallsixparisonoperators.Thefunctools.total_ordering()classdecoratormakesthiseasytoimplement. •Keyfunctionsneednotdependdirectlyontheobjectsbeingsorted.Akeyfunctioncanalsoessexternalresources.Forinstance,ifthestudentgradesarestoredinadictionary,theycanbeusedtosortaseparatelistofstudentnames: >>>students=['dave','john','jane']>>>grades={'john':'F','jane':'A','dave':'C'}>>>sorted(students,key=grades.__getitem__)['jane','dave','john']