[['few", ‘words']}, this is a list with one clement, a list. () True. As Oth element of L[2: 3} list isa list [“few”, “words”] which hasa member “few" init. (¢) True. £{2] returns the list [‘few’, ‘words'], “few () L[2] = (Few, words’) an clement of this list. 12] U1] + U2) = [are’, ‘2, “fev, ‘words! 5. Lisanon-emply list of ints, Print the smallest and largest integer in L. Write the code without using a lop. Solution. length = len(L) Lesort() print ("smallest :*, print (“largest » L[@]) Lpength-a})7 LIST MANIPULATION ite the most appropriate Tist method to perform the following task. (a) Delete a given element from the tist, () Delete 3ril element from the list. (@) Addit an element in the end of the Hist, (d) Add an element in the beginning of the list. (2) Adi elements of list in the end of atist gatution. (@) Femove() (b) pop() (c) append) (d) insert() (¢) extend( ) 4, Given alist of integers, Ly write code to add the integers and display the sum. solution. pos = @ # start of list sum = @ # initial sum while pos < len (L) : # loop through entire list sum = sum + L(pos] # add current item to sun pos = pos +1 Hf move to next item in ilst print (sum ) # the answer , Given a list of integers, L, write code to calculnte and display the sum of all the odd numbers in the list. Solution. pos =@ # start of List sun=0 # initially no sun while pos < len (L) : # loop through List if L[pos] ¥2==1: # this is an odd nunber sum = sum + L{pos] # so add it pos = pos +1 next item in List print (sum ) # the answer 9, Examine the following code : Y nunlist = eval(input( "Enter list:")) pos = 0 odds = evens = @ Jength = len (num list) while pos < length : if numlist(pos] %2 == 0: evens = evens +1 else : odds = odds +1 Pos = pos +1 if odds > evens : print ("Balanced oddity") (2) What is this program calculating? (b) What does the program for thelist (1, 5,2, 3, 6, 6,9]? (©) What does the program print for the list |2, 5, 2, 3, 6, 6, 9]? How can we fix this ? Solution. (2) The given code is checking whether a list of numbers is ‘mostly odd’ — ie, whether there ate more odd numbers than even numbers in the list. (b) Balanced oddity (€) The code prints nothing. This if odds > evens : print ("Balanced oddity") else: print (“Unbalanced oddity") because there is only one print statement, the fix is :COMPUTER SCIENCE Wit} if they have al least one member py for le sake ofthe exercise, write jy using, sans “Overlapped” 10. Given tay fists, write # program Hat ri nero bul otherwise prints “Sqnarated™, You may use the tion. . oe = eval input("énter 14st] :°)) Lista = eval (input ("Enter ist2 :")) lent « len(1ista) Jen2 » len(1istB) for a in range(lenl) : ele = listafa) ifele in listB : princ(“Overlapped") break else : , print("Separated” ; LL Write a program te find the second largest number of a list af munbers. ‘loop ends normally, not because of break © Solution, Ast = eval (input("Enter list :")) length = len(1st) bineese = secondbiggest = 1st[@] # though logically not fair for 4 in range(1, length): Af Ist[i] > biggest: secondbiggest = biggest biggest = 1st[i} elif Ist[i] > secondbiggest: secondbiggest = Ist[i] print(“Largest nunber of the list :", biggest) print("Second Largest number of the list :" secondbiggest ) 12. Write program that inputs ats of numbers aut shifts all the zeros to right and all uon-zero mumbers toe, of the list. Solution, Ast = eval(input(“Enter list :")) Jength = len(1st) end = Jength-1 print("Original list : ", 1st) iro while (4 <= end): ele = Ist[i] ifele=0: for j in range(i, end): Ast[i] = Ist[jsa) else: Ast[end] = @ end = 1 4¥ Istip! i 4 # if after shitting, a Consecutive @ shifted to current place Print("zero shifted : ", Ast)en tn Che 81. Invoduction 82 Creating and Accessing Tuples 82. Tuple Operations 84 Tuple Functions and Methods 81 INTRODUCTION The Python tuples are sequences that Jeamt in earlier chapters that Python tuples of a tuple int place ; Python will create 3 fr tuple, Tuple is a type of sequence like string lists are mutable but strings and tuples are This chapter is dedicated to basic tuple man creating and accessing, tuples, various tuple built-in functions. are used to store a tuple of v Jues of any type. You have are immutable ie, you cannot change the elements 1 uple when you make changes to an element of s but it differs from them in the way that and Ti iment ailation iy Python. We shall be talking about operations and tuple manipulations through someCOMPUTER SCIENCE WITH) 8.2. CREATING AND ACCESSING TUPLES on “round brackets, ¢.-, following are me empty tuple oO a tuple with nomenbery le of integers 25 ) tuple of nurbers (integers and floating point) 1, 2.5, 3.799) ce ‘e,'e) #tupleof characters (3,1, , 3.5, zero) # tuple of mixed value type 0 # tuple of strings as Cone’, ‘Tho', ‘Three’) ‘Tuples are Immutoble sequen: Before we proceed and discuss how to create tuple oe a a ees Pion = that must be clear is that Tuples are i mutable a ners token non-modifiable) fe., you cannot change elements of ofa tupl $ nig 8.2.1 Creating Tuples Creating a tuple is similar to list creation, but here parentheses. Thal is, use round brackets to indicate the items by commas. For example : you need to puta mumber of expressionsin | the start and end of the tuple, and separate (2,4, 6) abe’, ‘deF) (4, 2.0, 3, 4.0) 0 Thus to create a tuple you can write in the form given below : T=() T= (value, ...) This construct is known as a tuple display construct. Consider some more examples : 1, The Empty Tuple The empty tuples (). Itis the tuple equivalent of 0 or", ‘You can also create an empty tupleas: T= tuple() It will generate an emply tuple and name that tuple as T. 2. Single Element Tuple Making a tuple with a single clement is trick brackets, Python considers it a value only, mo t=(1) vont a 00 raed 50 1. Fae etl oie eresian a heer y tent tape ¥y because if you just give a single element in rou eg.tuples lon . at tuple contains many formed by placing a elements, then t tuple of | acta © enter such [@=Pressions in parentheses, ples, YOU c0” Spt it across several ine 8 given aon a 3 sars= (8,2, 4, 9,36, 25, 35, 45, 64, on 4 256, 289, 324, 361, 499 00, + 121, 144, 169, 481,84, 520,59) cS 69, 196, 225, Notice fhe opening parenthesis and losing parenthesis PPear just in the beginning and end of the tuple. 4, Nested tuples Ifa tuple contains an element which is a tuple itself then itis called nested tuple e.g., following is anested tuple : t1=(1, 2, (3, 4)) The tuple tI has three elements in it: 1,2and 3,4). The third clement of tuple tl isa tuple itself, hence, t1 is a nested tuple. ing Tuples from Existing Sequences You can also use the bu ilt-in tuple type object (tuplet )) to create tuples from sequences as per the syntax given below : T= tuple() ‘where can be any kind of Sequence object including strings, lists and tuples. Python creates the indiv Sequence. If you pass in Conside idual elements of the tuple from the individual ele: another tuple, the tuple function makes a copy. * following examples : ments of passed >»; >»; Ch ET tepec helio) Tuple wis crated from another sequence «a sing “hello” ae 4 te generat iia elements fom the ‘ntivihas! 10) >>Ls EW, ete, ey] »>t2=tuple(L) Tupte teil nat sn i ae crated individual elements from the é inddua ements of the passed list L7 . 1 COMPUTER SCIENCE WITH PHO c raracters or single digits via on sing apes fs Norton | 08 You ean use this method of creates *e input. Consider the code below * on ; exe tuptec tnputenter tuple e76r= ee : ef cer tpl elenants 234567 sundae eterscns of tuple Ener uP Sn ge carter (2,38) S'S : scyou not put parenthesis, it will create a tuple Using See, with tuple() around input) even it Yost or Paonly used method tO input tury s jndividual characters as elements. But eval(inpul0) as shown below + tuple = val input("Enter tuple to be added: » print ("Tuple you entered :*, tuple) when you execute it, it will work somewhat like = enter tuple tobe added: (2, 4, "a, "bik31"» [3.4]) Tuple you entered : (2, 4, "3", “nIkI2", [344]) os o sure e the tuple ek If you are inputting a tuple with eval(), then make sure to enclose ple elements in ! parenthesis. ; : Prease note sometimes (not always) eval() does not work in Python shell, At that time, you can nun it through a script too. 8.2.2. Accessing Tuples Tuples are immutable (non-editable) sequences having, a progression of elements. Thus, other than editing items, you can doall that you can do with lists. Thus like lists, you can access its individual elements. Before we talk about that, let us learn about how elements are indexed in tuples. Similarity with Lists Tuples are very much similar to lists except for the mutability. In other words, Tuples are immutable counter-parts of lists. Thus, like lists, tuple-elements are also indexed, i.e, forward i indexing as 0, 1, 2,3... and backward indexing as ~1, ~2, ~3,,.. [See Fig 8.1(@)] fuptet = (-0",'6' 7, 01") Fowndbdeing>0 1 2 3 4 OH teplot| a etlou Totpet ta 472 Satan 9 wnat th tuplet -2) (0) Tuple Elements’ two way indexing Shapes { Each of the individuat item: red i 459 somawhere a nme 2 re egiduel tems ofthe tuple are. sto Fi Sue 8.1 (2) How tuples sre intemal organizedql Hema ime, y US ours its individ in ups @ Indexing and Slicing Ti returns the item at index i mae eB the Tli: {201 retums a new tuple a index j. Just like lists, © Membership operators. B Both ‘int work for other sequences, Thatie eed ROl it not in does the opposi That is, in tellsifan cement proce athe icon PPosite element is present in the tupl and tuple or not an first item has index 0), Ing the obj Objects between i and j excluding index j, 'uple containing every ym index j to j, excluding ing nith item fro i Concatenation and Replicati ‘plication o end of another. The * Laake inate The een opera The + operator adds one tuple ee ey cheer Rss tuple We sal e aig sou ese two 3 = Tuple Operations ‘ ™ sessing Individual Element Acct Is ‘As mentioned, the individual elem v ¢ ial clements of a tuple are accesses Fe ochete, Consiter the folloming ex re are accessed through their indexes given in poo vowels = ('a', "ey "S,'0', Ut) : >>> vowels [@] ‘While accessing tuple elements, IW you pass ina negative index, >>9 vowels [4] uw 59> vowels[- 2] Python adds the length of the : tuple to the inden to et : element's forward index. >>» vowels[- 5] © Sas “ if you passin a negative nde, Python adds the length of the tuple to the Recall that like strir Pat is, fora 6etement tupleT, TI-S}willbe intemal ‘computed as: index to get its forward inde TI-S+ 6]=T11], and soon. many ways yet there i. an important differnet in iitable, while lists are. You cannot change individual Spat ists allow you 10 40 50 lid for lists (BUT not for u rape Fruples are similar to ists In ey war the Indes sink Diference from Lists fe similar to lists in es are not Mm Although tuples ar mutability of the two. Tup! clements of a tuple in place inti fully ¥ ateme ist Land have ah Thatis, following s tuples), That is, if 3 L[i] = element rd accessing we is VALID for Lists. BUT (meni at ne a afer for Lists Mote sore tat tiles i} = process each Sten here i yarate lines : For example, following loop shows eae iter of a tuple Tin sep Feces yet) nq fora in’ } print (Tl2]) | The above loop will produce result as = A | , | el } a | How it works { The loop variable a in above loop will be assigned the Tuple elements, one at a time. S| Joop-variable a will be assigned ‘P' in fist iteration and hence ‘P’ will be printed; in second iteration, a will get element ‘y’ and °Y’ will be printed ; and so on. 1 {| Ifyou only need to use the indexes of elements to access them, you can use funetions range) , | and fen{) as per following, syntax : . i for index in range(1en(T)): 4 process Tuple[index] here \ | Consider program 8.1 that traverses through a tuple using above format and prints each itemet a tuple L in separate lines along with its index. 8.1 Program to print clements of a tuple (‘Hello’, “1 r nts of @ tuple ("Hello’, “Isn't, ‘Python’, ‘fun’, «2° fines along | ‘ \ , with etement’s both inden (postive ond negate), ” > 2") Im separate | | Trogram Tet 'tsn't, 4 i = (Hello, "Isn't, ‘Python’, *furt, "2" i Jength = len(T) : | fora inrange(length) : | print (‘At indexes’, a, ‘and ', (a- length), ‘element :', Ta]) i At indexes 0 and -5 elenent : Hello | At indexes 1 and -4 element Isn't At indexes 2 and -3 element Python | At indexes 3 and -2 element : fun At indexes 4 and -1 element : ? Now that you know about tuple traversal, let us talk about tuple operations. a perations.at atime s, | ed; in seed tions ray goon TURES a gg. TUPLE OPERATIONS 5 ‘The most common operations that tuples. In this section, we are goj You perform with tuple ng to tak about the ee MeIUEE olning tuples and slicing 3.1 Joining T uples Joining two tuples is very easy just lke y concatenation operator, when used with td reste ition: literally 2). The + operator, the Consider the example given below : 'uples, joins two tuples. ooo tpl = (4, 3, 5) >>> tpl2= (6, 7,8) >>> tpli + tpl2 ——— peo eosatenas mo pk er: sod crater ne te As you con see that the resultant tuple has firstly elements of first tuple [st? and followed by elements of second tuple Ist2. You can aisojoin tivo or more tuples 10 formanew tuple eg >>> tpl = (ie, 12, 14) >> tpl2= (22, 22, 24) 92, tpL9 + (38, 32, 36) ‘The + operator is use! w concatenaie po>tpl=tpli+tpl2+tpl3 thre iia wples 10 get 2 ne ooo tpl Sct! wpe (10, 12, 14, 20, 22, 24, 30, 32, 34) The + operator when used with tuples requires that both the operands must be of tuple types. You cannot add a number or any other value toa tuple. For example, following expressions will result into error: tuple + nunber tuple + complex-nunber tuple + string tuple + List ERROR < WN Consider the following examples : = See err geet when wmting Sid hawt ule atid le >>> tpl = (10, 12, 14) poo tpl +2 cal last): Traceback (most recent Line 1, in File "" tpli2 Typetrror: can or > ‘tpl + "abe" Traceback (most recent ¢é File “epyshelLead>", Line, tpl + "abe" Typeerror: can onl} nay concatenate tuple (not “int") to tuPle a} last! in «nodule? y concatenate tupte (not “str) f° tuplecomputer SCIENCE WITH PYTHON 2g: smotimes you need to concatenate a (U) wee ple (say tpl) with another tuple containing only ong if you write statement like ¢ element, In that case, po tpl + (3) wn will return an error like : tt Traceback (nost recent call las File “epyshelli4s", Line 1, in «nodule? tuple + (3) saint” 2 typeErrort con only concatenate tuple (not “int") to tuple ‘The reason for above error is that a number enclosed in ()is consicered number only. To make Festaple with ost one clement, just add a comma ater the only element ie. makeit 3). Now Python won't relum any error and successfully concatenate the two tuples. >>> tpl =(10, 12, 14, 28, 22, 24, 38, 32, +34) Sint tome tpl e “pa tpl + (3,) 4 (20, 12, 14, 20, 22, 24, 30, 32, 34, 3) Repeating or Replicating Tuples Like strings and lists, you can use" operator to replicate a tuple specified number of times, ¢g, if tpl1 is (1, 3, 5), then js tpt +3) ¢_——— The * orator repos tuple speis eed Ley ‘mumber of tes and eats tew ple” 8.3.2 Slicing the Tuples Pie [When used with tuples, the ke list-slices or string slices are the sub parts of ; reallBons ‘operator requires both the ia racted out. You can use indexes of tuple elements ‘operands as tupletypes; and | fe slices as per following format : the * operator requires a if and an integer | ‘seq=T[start:stop]. = = The above statement will create a tnple slice namely s le T on indexes ate a tuple slice namely vi i fat dart ain p eq having elements of tupl i p-1. Recall that index on last limit is not i i e slice The tuple stce is a tuple in itself that is y riled pahepmenesensaie cntuples ein iself that fs you can perform all operations on it just like you perform Consider the following example : >>> tpl (18, 12, 14, 20, 22, 24, 38, 32, 34) > $eq = tpl [ 3:-3] * >>>.seq (26, 22, 24)Beg, ig: TUPLES yornormal indexing, if the resi jon raises an IndexEree ni poundaries instead, Vand theres goon. Si le the tuple, a a ult wpe Msnanpen et Pe septs ore * Python sim ‘OP given bey. thot fall Between specified penn "PY retums hee 01 ies, i ns the elemen| itany, nis >> tpl =(10, 12, 14, 29 +14, 20, 22, wn [3:30] 32, 38) Ging ure (28, 22, 24, 38, 32, 34) yin litt ay bod he sof he wpe but tel [15-7] lene ft ak fling rong © (20, 22, 24, 20, 22, 24, 39) Tuples also support slice st other element of the tuple, there range OU following format : Giving ‘ant to extract, not consecutive but every th vay ere is a way out ~ the slice steps. The slice steps are used as per seq=T[start:stop:step] Consider some examples to understand this, 22> tpl (2, 12, 14, 28, 22, 24, 30, 32, 34) EZ] intl at mat te in berger. Check ring poo tpl (a: 1 | (20, 14, 22, 30, 34)* pop tpl? 20: STS padecoy attr es 2 tt (14, 24, 34) goo tpl: 3] Nesta tion, Oa ei a 8 (ap, 20, 38) Tats fom the ein le, ik very Bl element ft pie Consider some more examples: seq=T[:: # get every other item, = vt every other item, seq=Tl Fe ener, Inox a sixth element ators with tuple slices too. For [NOTE al You can use the + and * ope 5, as (2,4,5,7-8:9 lr Istsartz stops stp creates 2) starting with the first starting with the example, i » namely Tp has values 2 ample, if a tuple namely TP vemomarems 2,34), then : sone eet mio a See andthe fll te ments between yo Tp 12:5] *3 a (5, 7, 8, 5, 72 8: 52728) i 4 a + operator has da! the doo TpL2iS] + (3s 4) je en est (5, 7, 8 3,4)COMPUTER SCIENCE WITH PTW | write code with loops for it having to I= etc. wo tuples withou ye mee fet . 7 P oneno er of two pls AIAG al the comp tuples 3 OP ie Consider following, Com es read earlier pat you have rales thot ¥ yar (23) pode (243) praeed Troe Ss TW LN a ) Fo ef lesen al racing alu val a ed flo ith rscing PI Se eed egal sorce (24 past False porard False pode (2.0, 3.0) podra False pordeea Troe vere (2, 3,4) Troe You can refer to table 7.1 that discusses non-equality comparisons of two sequences. Elements in tuples are also compared on similar lines Creating a tuple from a set of values is called packing and its reverse, ie, creating individu ‘Values from a tuple’s elements is called ‘unpacking. Unpacking is done as per syntax : svariablel>, , net of Where the number of variables in the left side of assignment must match the number ‘lements in the tuple. For example if we have a tuple as : 01,2, 8) she levgth of above tuple tis 4as there are four elements in it. NOW to unpack it, we can writ Ky ret SA ties neve chs the vrisls on LTS im porrthesis. I wil give you same reat.s eo Pere thon will now assign each of 4 gssignment operator. That is, yo a the elem: ents of tupk P 7 le to the vari | gomewhat like : an now indivi oat ‘0 the variables on the left side of : '¥ Print the values of these variables, print () print (x) print (y) print (2) The above code will yield the result ae = ‘i : 2 w v As per Guido van Ros i the creator of Python language — “Tuple unpacking requires that the list of var ist of variables on the te Sea f variables on the left has the same number of 1 Deleting Tuples ‘The del statement of Python is used to delete clements and objects but as you know that tuples are immutable, which also means that individual elements of a tuple cannot be deleted, ic. if ||| you give a code like : oo del t1(2] Then Python will give you a message like : | Traceback (most recent call last): | ", line 2, in File "cipython-input-83-cad7b2caBee3> del t1[?] tuple’ abject doesn’t support Aten deletion complete tuple with del statement as = TypeError: But you can delete a del For example, poo th = (5) 75 34 9 12) >>> tr (5, 7, 3, 9, 12) >>> del ti Ae >>> print (41) st)? Traceback (most recent an 730070739? ine 1, in enodule> File “eipython-inpyt print (t1) _COMPUTER SCIENCE WITH pypaa. THODS a e sions and methods for tuple manipulation, Yo, any builtin oe Hon) In earlier chapters: In this section, you wy Mt he ram, uch met — ‘worfull tuple mel ‘yseful built-in (Upl hhods of Python used for tuple mani ae Je manipulation methods. other bull oT Ton) t808 ‘This method returns 1 Syntax? | ren etuple>) Tes tle name a argu th of the tuple, be the count of elements in the tuple, J length of : ip auf and retrrus an integer Example fo enployee = (John, 10008, 99> Len(enployee) a = he nt) rears the count of ele 2: The mox()) method ‘This method retums the element from the tuple having maximum value. 24, ‘Sales') tuple Syntax: ‘max() = Takes tuple maxima Example : >>> tpl = (10, 12, 14, 20, 22, 24, 36, 32, 34) > max(tpl) 4<——_ 3 Maxima value from ple tpt» med >>? tpl2 = ("karan, “Zubin” >2>max(tpl2) ‘obi’ «———__ Mavinwom value from tuple tp és retunted () 01 lists too to find maximum element {rom a Je that al) i! | | _ Please not | applied on sequen pepe vi | Contains values ofsame tyne ees ete ill return a maximum val je ONLY TF the see | will give you an error at ee your tuple (or list) contains values of different datatypes = f) i © >a, a that mixed type comparison is not possible : (alll * (1, 2.5, "1", (3, i >>>max(ab) (4), (3,4) ) Ht Traceb; a ‘ack (ost recent cal) last): File “", line 1, in ig TUES. >>>ab= ([3,4], Traceback (most p, Cet ca 1 File ") = = Takes tuple mane as a et ‘ple name as argument end retums a "5 aM abet (the element with i ut wit ima ved i >>> tpll= (10, 12, 14, 29, , 12, 24, 20, 22, >>> min(tpl) 74,38, 22, 34) i | ne Masiorurn vate from tape tis earn) iL] >>> min(tpl2) >> tpl2 = ("Karan", "Zubin","Zara", | pl2 = ("Karan", "Zubin","Zara", ana") iN" | 1 An riun re | are trad HH Like max( ), for min( ) to wark, the elements of tuple should be of same type, H Hy 4qThe index( ) method The index( ) works with tuples in thesame way itworks \sithlists-Thatis tretumstheindexof ||| an existing, element of a tuple. His used as : | ‘ctuplenane> . index (>> t1= [3 4, 5, 6-8) | “nae mit? 144 5 a (99? t index (5) ; ypes tnenstt 2 valuetior exception \} But if the given item does not jnjeet in 3 giver sSP80—° aber element eb mae 8 The count( ) function , The count( ) method returns tht (istftupte). You can use the count( rear fe count of 8 TN jowingExample? 9, 33,752) poo te (2a dy pp9 ta eoune(2) por ta.count(7) 2 poo tiecount (22) 2, 50 77 42 89 3 ara element it in Tuple, ives 0 (zero), 62 Tha tuple( ) method id to create tuples from different This method is actually constructor method that can be user “types of values. Syntax ‘tuple(esequence>) = Takes an optional arguinent of sequence is eraply tuple pe; Returns « tuple. = With no argument, it retun Exaniple = © Creating empty Inple © Creating a tuple from a list 90> tuple) >> t= tuple([1,2,3]) oO pot © Creating tuple from a string (12,3) >>> t= tuple(“abe") Dont (2,8) AS you ca tice Pyt ‘ tuple Butone th that, Python has considered only the key’s of the passed dictionary to creat® yee ont thing that you must ensure is that the tuple( ) can receive argument of sequere® ;, ’e,, either a string or a Ii ena dieti an error. See below : 1g or a list or even a dictionary. Any other type of value will ead! >>> t= tuple(a) NOTE aad Traceback (nost recent call last): le “cpyshelli#1>" With tuple), the Rem t= tuple(1) eae teen eee ee ie sequen aa a string ora lst 3 dT! 1 : . ‘yeeError: ‘int’ object is not iterable ie lupe ) and tisi( Passed sequence, Jan Possible, THe ae constructors that let you create tuples and lists respecte Following eat can be exploited asa trick to modify tuple, whieh one formation box talks about the same.hat et) iy les called immutable types ? pot are mutable COUNteNpaTtS of eyes can we hove in a tuple ? pothey all have to be the same type”? ow are individual clements of tuples accessed? tow do you create the following tuples ? () (4, 5, 6) @) (-2, 4,3) (9 (-9, -8, -7, -6, -5) () (-9, -10, -11,"-12) fe) (8, 1, 2) a= (5, 4,3, 2, 2, 0) evaluate the following expressions : @) ao} etal Anand", 35000, 35, “Admin") ©) aft} : . © afatey) (anand , 35000, 35, ‘Adnin') (@ afat-1]) (© afafata{2}+1J]] Gn you change an clement of a sequence ? What if the sequence is a dictionary ? What if the sequence is a tuple? What dees a + b amount to if a and b Be tuples ? >>> 1st 1] = 45000 Whar does a + >>> Ist. b b © tuples 2 mount tows and ['Anand, 45000, 35, ‘Admin’) that a toyte and a 7) amnunt te it a a 3. Create a tuple from the modified list with wpleQ, hyecttiAg the same as a tuple of >>? tpl « tuple(1st) acters > >>> tpl. pica have an integer, a string, a ['Anand’, 45000, 35, ‘Admin'] a tupie 9 and a tuple of strings ‘Tuples are immutable: t ‘Counterparts of lists. If you need to modify 'e contents often of a sequence of mixed types, then you should 60 for lists only. However, if you want ta ensure that a sequence of mixed types is not accidently changed or modified, you go for {uples. But sometimes you need 10 retain the sequence as tuple and sill need to modify the contents at one point of time, then you Can use one of the two methods given here. (0) Using Tuple Unpacking Tuples are immutable. To change a tuple, we would need to first unpack it, change the values, and then again repack it: tpl = (11, 33, 66, 99) 1. First unpack the tuple : a,b,c,d= tpl 2, Redefine or change desired variable say, © c=77 3. Now repack the tuple with changed value tpl = (a,b, c,d) {b) Using the constructor functions of lists and tuples i.e., lisi( ) ond tuple( ) ‘There is another way of doing the same as explained below : 1, Convert the tuple to list using list() : >>> Ist = List(tpl) >>> Ist (Anand, 35000, 35, ‘Admin’] 2. Make changes in the desired element in the list Isn't the trick simple? ©. ~ Progress in Computer factical component-book Pleose check the rein ahora in PriP 8.1 under Chepler & otter) Science with Prin ically doing it on the compuler- povteee . theend of eur chapter. Let us quickly revise what Wehaveteingy With this we have come to far. Let Us REVISE = ‘ples are immutable sequences of Pyton i, yu cannot change elements of a tuple In place The empty round brackets ie.,() indicate an empty tuple | ‘ples index thee cements just lke strings or fists, Le. bo way indexing . I 4 Tuples are stored in memory exactly lke strings, except that because some of their objects ore larger tha abe they store a reference at each index instead of single character as in strings. ‘¢Tuples ore sinilor to strings in many ways like indexing, slicing and accessing individual elemenss exbdqet * immutable just like strings are. \ Function lea(L) returns the number of items (count) in the tuple L. | ‘Membership operator in tells if an element is present in the tuple oF riot and rot in does the opps. | ‘& The + operator adds one tuple tothe end of another. The * operator repeats a tuple. i 4 Tuple slice is an extracted part of tuple; tuple slice is @ tuple in itself. ‘ Tistartstop] creates a tuple slice out of tuple T with elements falling between indexes start and op rte I stop. i % Common wple manipulation functions are : ten( ), max(), min( ), and tuple( ). 3 \ Siiied Problems w How are tuples different from lists when both are sequences ? Solution. The tuples and lists are different in following ways : © The tuples are immutable sequences while lists are mutable. ® Lists can grow or shrink while tuples cannot.7 ries: oo A 1 say that a tuple iS an ordered list of objects ? nyu = pes OF uple is an ordered list of objects. This is evidenced by the fact that the objects can ue stom a ough the use of an ordinal index and for a given index, same element is retumne vase 3 time ow coe is trying to create a tuple with a single item. But when we try to obtain the length of the tuple ellen es error. Why? What is the solution ? 3. pytiion sie po t= (6) poo ten(t) qraceback (most recent call last): File “epyshell#8>", line 1, in cmodule> len(t) aypeError: object of type "int’ has no len() solution. The syntax for a tuple with a single item requires the item to be followed by a comma gs shown below tera") Thus, above code is not creating a tuple in t but an integer, on which lent ) cannot be applied. To crate a tuple in t with single element, the code should be modified as : oop t= (6) >>> len(t) What is the lengtit of the tuple shown below 2 t= CCCI, 14°, "e), ', 2), 'e 3) Solution. The length of this tuple a careful look at the theta a wet, 33 = t2, "a", 2 t= (t3,"e", 3) Gn tuptes be nested? 3 because there are just three elements in the given tuple. Because ‘0 tuple yields that tuple ¢ is made up of : Solution. Tuples can contain other compound objects, inclu Hence, tuples can be nested. i lists, dictionaries, and other tuples. Ke © Given a tuple namely cars storing car names as elements : Toyota’ ‘Honda’, "GH", ‘Ford’, ‘BHi", “Volksuagon", “ercedes', *Ferrai*, "rite a progrann to print names ofthe cars in the inde range 2 to 6, both inclusive, The output showtd also *Porshe*) include the index in words as shown below : One Honda Two GM Solution, Cars w (x . ne (Toyota! Honds','GM, Ford "SM, Volkswagon Seber «Zero, “On: "xin range(2,7: Print (Nunber[x], ears{x]) a ‘Mercedes’ Ferrart','Porshe) ey “Two", “Three”, "Four", "Five", "Six", "Seven", “Eight, "Nine™)COMPUTER SCIENCE WITH Py ay rents Replace fist four element flit nit sth sine cleric fis for fis eT, 2,72 PD Tacrisel nr ake ts exfore al afler Une Ht Is modifi, Nig | gl Co Gicen a Tet single s! ee four eee ” Se aN ce ery ners, ensne “ort “eupte] a Theta, Senet ar ro rane ‘caefore unpacking She | yw? pete a aL EIT gen) 5 oer fo}, CLT, Ud Le . ; e prams (9 seston ftce change He square brackets of ccond Fe fo round pg “ge antheunner olf press es if : reg, te) ames? sult he the impact of this change pater waltzen intoerror because now Lisnota lis but tuple (because Brakes chang tuple is immutable, hen ignments are not possible. 4 » So, Python will display like 2 Before Unpacking the list is (hello, ‘there’, ‘are’, ‘sone’, ‘numbers’, ‘coming, “front, “tuple’) Traceback (most recent cal] last): . File °C: /Python36/Pythonliork/prog.py", line 5, in «modules * 4 Ufo], ft], L¢2], 113] =T : Typetrror: ‘tuple’ object docs not support item assignment 9 Write a Python function secondLargest(T) which takes as inpul w tuple T and returns the send lye element in the tuple, You can use any of Uie standard Python functions to obtain your result. 7 Solution T= (23, 45, 34, 66, 77, 67, 70) maxvalue = max(T) ‘ Jength = len(T) secnax = 6 ; for 2 in range(length) : ; if secmax < T[a] < maxvalue : . secmax = TLa} 2 print ("Second Largest value is :", secmax) 4 t , . 5 i . 10. Write a function getPowers(x) that returns a tuple containing x, x2, x and x*, Read fice integers fe 1 user, and for each integer read, print that value raised to the powers 2, 3 and 4. , Ype | Solution. | for n in range(S) : x= int (input ("enter Number :")) T= (x, x02, x93, x14) print (number, “raised to powers 1, 2, 3, 4a1 2. Introduction 92. Dictionary ~ Key: Value Pairs 93. Working with Dictonanes 94 Dictionary Functions and Methods INTRODUCTION You must have realized that Python offers many different ways to organize collections (é bunch of values in a single “variable”) of data items, such as strings, lists, dictiona Of these you have alre, ies, tuples ete. dy worked! with strings, lists and tuples in previous chapters. Now is the line to work with other collection types. So, in this chapter, we shall be talking about dictionaries, In this chay pler, you shall be teaming about how data-items are organized in a Python dictionary, ‘ how you can access items from a dictionary, various operations that you can Perform on a dictionary and various related functions and methods, a acompute SCIENCE WITH PYTHON . ev : PAIRS coe ealled a dictionary. Dictionag, 92 bycronany =KEVNALUE PA isa voy verse pect Rather than having om yailt-in Python data YPC Thon, but wl x ries in Python hay. Among toe a 0 ee oe tr ic eee ey ae simply are dotaitem (ust KET ges are acolestion O° hepa. Sesociated with na Fo That is, Python diction jetiouaries you can search for a toy be aed Kit oa a there isa mins eee cords) and associated values Gist ize FG i eee Exgist ee hat essocinle ApETA TROT DET Se neon tse ere aa ot nt seconati, ar have to know the Key to find the element eval pats that mack keys to values. in the dictionaries. ” ‘All this will become clear to you w following sections. hile you go through 9.2.1. Creating 0 Diclionary 7 ; ‘To ereate a dictionary, you need to include the key value pairs 3m curly braces as per following syntax: value>..+ } edietionary-nane> = { , , "Line 1, in «module» dict3 = {[2,3]:"abe"} TypeError: unhashable type: ‘List’ oe IMPORTANT The above error TypeError: toassign a key with mut. unhashable type always means that you have tried | able type and Python dictionaries do not allow this, 422 ‘Accessing Elements of a Dictionary _ While accessing elements from a dictionary, you need the key. While in lists, the elements are denen, tough their index ; in dictionaries, the elements are accessed through the keys defined in the key:vulue pairs, as per the syntax shown below : Sdictionary-name> [ ckey>] i to access the value for key defined as “Karen” in above declared teachers dictionary, you will write “ >>> teachers [*karen*]_ 8rd Python will return Sociology } : “milarly, following statement > Brant Cxaren teaches", teachers('karen']) | Will give Output as ; aren teaches. Sociologycounuter SCIENCE WITH PYTHON 84 ou access only rack ening jude square Awhile giving Ary tose aie mentioned Ee tre vale correspon TS fy square rackets B i the toons meets of he eons displays the entire 6 Consider following example: pot, "Vouel4” : "6", “Vowels” "arp svorel2" 2 (vowel "3s aordet sake coments of cia Note the Disp asi concent fro order a ura "vowel2! ‘vonel4 :'0', ‘Vowel? uf dictionary Prat nt er far rer of eerments ib >>» print (2) se, Vowel! :'3'} prin sees unaly sy ven d[*vowel2") the _— ee ost, tie ht en a AP i ae yop df'vouel4") eepenpunng ales string type. a “Asperabove examples, we con say that key order isnot guaranteed in Python This is becausein Python ditionsees, the elements (ey: tahte pars) are wionfered ; one cannot access elements per specific order. The only way to access a value is through key. Thus we can say that keys ct like indexes to access values from a di ‘Also, altempting to access a key that doesn’t exist causes an error. Consider the following sistent key (13) from dictionary d. onary statement that is trying to access a 10 yoo [23] NOMEN Traceback (most recent call last): Th fytos geen File “", Line 1, in clements (key : value pais) dkeyError : 13 unordered; one cannot a [13] elements 3 pt spate re The above error means that before we can access the value of a particular key using expression such as d[“13"], we must first ensure the key (13 here) exists in the dictionary. Like list elements, the | dictionary and values of a Followin x stored through their references. dictions 9.1 illustrates the same for a ‘ Boose" :3, “tern” :3, "hawk" : 1} Figure 9,1. References of keys and V4 are stored in a dictionaryhere are ae of tse in ment as coys act lowing 25 gs OCTIONARES qraversing © Dictionary edt tof a collectiox HP avers MIEOMS aecessin sans eon same and 824 proces se for 1OOP MAKES IE CDSS 10 ayers gntX SOF loop gor .keys() and toseeay mnlues in one go, you may write .values( ), as shown below (for the same dictionary | d created above) : >>> d.keys() dict_keys([ ‘Vowels’, ‘Vowel4’, 'Vowel3', 'Vowel2', ‘Vowel1']) >>> d.values() dict_values(('u. As you can sev that the keys() function retums all the keys defined in a dictionary in the formol a sequence and also the values() function returns all the values defined in that dictionary inthe form of a sequence. You can convert the sequence returned by keys( ) and values( ) functions by using list() as shown below : >> list(d.keys()) ['VowelS', "Vowel4", "Vowel3*, “Vowel2', ‘Vowel1' } >>> list(d.values( )) Tut, to" 'i', te', fat] A dictionary is a unordered set of key : value pairs. Ils values can contain references toan 7° of object. 2. Not a Sequence uae sting list and tuple, a dictionary is not a sequence because it is unordered ad ‘ments. The sequences are indexed by a range of ordi lence, ts." q 7 J , they are buta dictionary is an unordered collection. a! RUMErS. Hence, they 2%orm of inthe t() as wise, yr set of zero © og: DICTIONARIES pine OF Ro: No! Numb: 40 yiaionaries are indexed by i ‘eys. strings and numbers qpc2: Actor I fi fi le contains immutable oy; | poy But the values in ie iia | dictionary. ] Following dictionary diet has, poo dict1 = { y } >>> diet [0] ‘value for key | <—————— +f grape por dict1[(4, 5)] ‘value for a tuple-as-a-key >>> dict1[4, 5] ‘Value for a tuple-as-a-key poo dict1["3"] ‘Value for a string-as-a-key 4. Keys must be Unique Each of the keys within a diction dictionary, there cannot be However, tivo unique keys declared above : » Birdcoun = Notice that two different Keys SiMitoble: Like lists, dictionaries are 2° : ent Using the assignment statemt ‘[edictionary>[conmutlh SCIENCE VATE PYTHON — 9 1 288 sod above : Forevample, conser the dictionary det del ye ora key a oy waged ine saa oe tiangee assigmiirer) stasemer seaieta["3"] « "changed tonew strs7” por diet21("3"] hanged to new string! ; ban toa dictionary using, 2 simple assignment stateren, 4 can even add a new heya Ifthe key already evists, then value is simply Jd be unique “But the key being added show das jement abov changed as in the assignment stat “>>> dtces[ned"] ="aneu pair ds aes” >>> dieta . (01 Value for key 8, 12: Value for key 1) (4 5 ipte-as-avhey, 3: Volue fora string-35-2 Mnew :'a new pair is added) Sy 6. Internally Stored os Mappings “Internally, the fey:value pairs of 2 dictionary internal function (called hash-function'). This way’ ): Value for a key’, ‘and for fur! : 7, are associated with one another with some of linking is called mappin; Keys Hash function Stored values koyt oye Valued | i Koy Key > / Figure 8.2 Internally Keys being mapped to Yalves 9.3. WORKING WITH DICTIONARIES Alter basics of dictionaries, let us discuss about various operations that you can perform o* dictionaries, such as adding cloments to dictionaries, updating and deleting elements dictionaries. This section is dedicated to the same. i! 9.3.1 Mulliple Ways of Creating Dictionaries You have leamt to create dictionaries by enclosing key:alue pair other ways of creating dictionaries too that we going fo discuss here. H “Hah function ian internal algorithm to map and link & Key with a stored vatues curly braces. TherepICTIONARIES HON 9 Diclionary 1, method all the key:y, : alue pri ft sets jand enclosed in curly brane” © 1 ave already worked with thi © Written colle t Yorgpntssmethod, eg fatowing ta ‘ Testively, separated by ictionary Bee tionatis wate, snpleyee = Came: Soh eatery moloyce salsobeingccern aes ested + 10000, fed the same way : _ age : 2a tema paraiess vale Poirs 10 on Ematy Dict , Sen, GAN gis method, firstly an empy dic Heory Simply ne pair ata time. FEBonary is created and then k anid values are added to it __-@ Te create an emply dictionary, thore “(by giving dictionary contents in ‘Employees = {) Gi) by using dictionary constructor di w y oF diet() as show mutaeiien iet() as shown bolow : 9 Next step is to add key are two ways : empty curly 'PLy curly braces as shown below ‘alue pairs, one at a time as per [¢key>] = evalues synlax given below : some ) For example, in the adjoining statements we are first adding a |"Enployesl hey:value pair of ‘name's ‘John’, next statementsadds ane employee salary] = 1008 | eget i 10000 for Key “salary’ and the third and ast statement adds pe] = 24 ralue 24 for key ‘age’. This method of creating dictionaries is used lo create dictionaries dynamically, at runtime. 4. Creating @ Di {sing the diet() constructor of dictionary, you can also create anew dictionary initalize from specified set of keys and values. There are multiple ways to provide Keys and rales to dct) constructor. (0) Specify Key: Value pairs as keyword arguments 10 dicl() function, r the argument names are taken as keys of String type. nary from nome and value Pairs Keys as arguments and Values as their values. Here " 5 Pt ene Employee arene ="John’, salary = 10200, 28° = 24) cannon rm OF >>> Employee ames to ~ (‘salary : 10008, ‘age’? (i) Specify comma separated key vale P tenivd need to enclose them in cus braces 8 SHO" acs) ay ynet : ‘Johny salary #20200) 24, ‘name’ = “Jobe } sna. To give hey ste pa in this format, you pairs. ants of 359 Employee = dict ((™™ bo Employee --{salary’: 10000, "982? 2, john") ‘name’COMPUTER SCIENCE WITH PYTHON, a arately. In this method, “ ding values separately. hey, k arately and correspon iments atinspecity eysuep parately in parentheses? and are given as arguments to the 2H) function, which is then given as argument of dict( ). - oe 7 Fint group contalns al ond Be tree im spe tcl (iene ‘ eee naa frrurient to ep funtion. The nit) function li phen | thet of corresponding key, eS | St anpument of dict) constructor ~ Jerre : >>> Employee = dtct( 2ipt Cnane’ ‘salary’, ‘age’), CJohrt, 18008, 24)) >>> Employee iD, J {salary : 1080, ‘age’ : 24, ‘nane’ : “John’} ‘The: ip func FECT with the first value of second set, se, = ‘ip function clubs first value from first set with the firs v (Second value fom, first set with the at value of second set, and so on, ¢g.,in above example, ‘name’ ig With ‘John, ‘salary’ with 10000 and ‘age’ with 24. Using these clubbed values, the dig) constructor method creates key: value pairs for the dictionary. » Uiv) Specify Key: Value pairs separately in form of sequences, tuple argument is passed to dict(). This argument (passed list or tu individual key: value pairs. That is, akey : value pairis In this method, one tq, ple) contains lststupleg Specified in the form of alist and there are as many lissasitemsof Outer list as there are key: value pairs in the dictionary. Consider the following example : See, there i one list ppe argument passed to dict )consiuctor, This st argument, it 1wm contains all keyvalue pain as late (5 list ype entries in one list here.) >>> Employee = dict({{"nand, “Joh, ['salory ', 10000), ['age, 247)) >>> Employee ay (salary : 10000, ‘age’ : 24, ‘nane! John’) You can also pass a tuple containing key : value pairs as list-clement or tuples as elements. Se following examples : The dict } meta is ‘contains Uist-etements | >>> Empl2= diet((['nane’, “John*], ['salary', 10000), [‘age', 24) ))/ | >» Empl2 {'salary : 10008, ‘age’ : 24, ‘name: ‘John’ } Provided tuple argument, The posed ile 8 of hey. values (5 lit entries in one ele The dict) method i proved tuple argument, The passed tuple comains uple-elemet of ey, sues (5 tuple entries in one tuple) >>> Empl3 = dict((Cnamd, obr), (salary, 16000), Cage, 24))) I >>> Emp13 : _ Csalary’ : 10000, ‘age’ : 24, ‘name’ : ‘Johr’} = >>> 2, ie, astuples.gig Elements to Dictionary, 2 add new elements (key ; 1 ‘you caf 8! nts (key value pain) , BUT the key being added mu) © 8 di an exists, then this statement aa St not exist ‘rare’, Using assignment as peta Med to dictionary. change the value of ling ep be tng. ene sy no egictdonary? [] = > Employee = (‘name : "John __ rn enployee(dept'] ='Sales' >>> Employee Newent added {'salary’ : 10082, ‘dept’ : ‘sales’, ' 1 "Salary : 10060, age: 24) AEE #24, ‘mane’: “Johny storing a dictionary inside another dictionary is called nesting Cf diine must know about nesting of dictionariesis that, you can erect eee dictionary. You cannot have a key of dictionary type ; you know the reason — only immutable types can form the keys of a dictionary, 9.2 A Dictionary contains details of ovo workers with their names as keys and other details in the form of dictionary as value. Write a program to print the workers* information in records format. | fon Employees = (John ; {age’: 25, ‘salary’ : 20000), Diya : Cage : 35, "salary : 5ee00)) for key in Employees : a ” Carefully notice, how the print ("Employee”, key, ernie Bot print (‘Age :', str ( Enployees[key]['age’] )) inner dictionaries, stores as vulues print (‘Salary :', str ( Employees[key][’salary] )) , Employee John + | Age: 25 Salary: 20000 | Employee Diya : | wget 35 \ Salary: 50000 933 Updating Existing Elements in a Diclionoy snows Tet you Updating an element is similar to what we did jus change value of an existing key using assignment as per following sy" dictionary>[] = >> Employee = (‘name : ‘John, 'sa1aY | 959 Employee['salary’] = 20000 | >>> Employee ys John} | {'salary - 2eeaq. ‘age’ 2 24, ‘nameCOMPUTER SCIENCE WITH PTHON «5 it in the dictionary as Inpietionaries the updation ang must ex But make sure that the key ce onsry. " stwciae new entzy will be added to the ate —_-nditlon of elements ae sy i othervvise new entry epeatue pairs you con eres In symtae. But for 383ton he Using this technique of adding bey 1g input (OM fey must OL AL Im the { ly at runtione By a6c:P! dictionary and for updation, the Key must exist the detionay, Zi —— i po! dictionaries interactive Following program illustrates this. ining names of competition winner student 8 Keys and 9.3 Write a program wo crecie a dietionary cont | ruber lr wis 0 ves n= dnt(Anput(’How many students ?“)) Comphinners = (} For a inrange(n) . ; key = Input("Hane of the student :°) value = int (input(*Munber of compet Conphlinners[key) = value Gh stitdons won :*)) print ("The dictionary now $5 2 print (Conphinners) - The sample run of above program is on fame of the student : Rohan i Nunber of competitions won t § .. i Name of the student 1 zeba | teeter of exeeritions to: 2 ane of the student : nihar umber of conpetitions wan : 3 ane of the student : Roshan Number of competitions won : 2 ty name of the student : James a urber of coapetitions won : 5 The dictionary now is : (Mihae £3, Rohar! = 5, Zeba': 3, Roshan! 2, anes! : 5) H How many students 75 3.4 Deleting Elements from © Dictionary : There are Ie» methods for deleting elements from a dictionary. Noy (9 To delete a dictionary element or a dictionary entry, ie, 3 heyoalue Pair, you can use del ‘“ command, The syntax for doing so is as given belowC 9 : DICTIONARIES 293“ consider the following example : »>2 empl3 {’salary’ : 10882, ‘age’: 24, ‘name’ = ohn} ypvdel empl3['2ge') areenpl3 4 Sse, the dictionary now has {salary 10002, ‘name: “Johny fat enry remove put with del statement, the key that you are giving to delete must exist in the dictiona: otherwise Python raises exception (KeyError), if - = See below : _>>del emp]3(‘new] «——___ Trying to delete a non-existent key raceback (most recent cali last): File "cpyshell#22>", line, in «nodules del emp13[‘new) | KeyError : ‘new (i) Another method to delete elements from a dictionary is by using pop( ) method as per _ following syntax : .pop() | Thepopt ) method will not only delete the key:value pair for mentioned key but also return the corresponding value. Consider following code example >> employee _ fisalary’: 10000, ‘age’ : 24, ‘name! + ‘John’ 99> employee. pop(‘age') 26 ae show here forthe erent dea >>> employee Element delete from dictionary {salary : 10000, ‘name’ : 'John'} aa I you try to delete a key which does not exist, the Python returns error. See below : >>> employee .pop('new) Traceback (most recent call last): File “", Line 1, in employee. pop("new) KeyError : ‘new . However, pop() method allows you to specify what to display when ra given ey does not Okist mates teen the default error message. This can be done as per following syntax : edictionary>.pop(, «in-case-ef-error-show=ne7) For example : >>> emplayee.pop(‘new, "Not Found?) t Found: message. See, nove Python returned the specified message in Place Of exronmeseagCOMPUTER SCIENCE WITH PYTHON ~ 3 “294 9.3.5 Checking for Existence of @ Key seth dictionaries as wel But they can ch paren orsoniyTo check for whether value is present ‘eased on reverse leapt nea este a aie Proper ‘rode for that. (Solved Pr ‘oblem ay vie nei To Se eenbeithip operator for a Key's presence in a dictionary, YO tas per syntax given below ! ckey> An key? not dn ¢dictionary> — The in operator will retum = The not in operator will re otherwise False, the dictionary, otherwise False vyis present in ot present in the dictionary, Trueif the given ke; i turn Truc if the given key 1s ni Consider the following examples = >o>enpl » (salary : 10008, ‘age : 24, __>>7age! An empl True >>>"John' in emp] False ‘name’ : ‘John'} ZA pr done not in eepl Yohn' is not a key, hence Python rewurned False, as in only ~ heck in heya of the detioray. >2>‘age' not in emp] False Please remember that the operators in and not in do not apply on values of a dictionary, if youuse them with dictionary name directly. That is, if you search for something with in or not in operator witha dictionary, it willonly look forin the keysof the dictionary and not values, >>> dict1 {‘age’: 25, ‘name’: 'xyz', ‘salary’: 23458.5) , , The In and not In operator check >>'name in dict fee winrned Fab Uf you bid for membership only In eys of True a search for a value in a dictionary using the dictionary and notin values. Sa pootxyz" indict2 False However, if younced tosearch for a value in a dictionary, th i ; then y i th ‘edictionary. name>.valuest ), ic, ry, then you can use the in operator W! >>>"xyz! in dict. values() True a ding ecictionary> ve Fats eaten value(s can ook ' 9.3.6 Preity Printing @ Dictionary You generally use print function to print a dictionai | i 7 7 ry in Python, eg, if iti as Winners = Rohan’ :5, ‘Zeba’: 3, ‘Roshan’: 1, 4 8 if you have a dictionary | print it, Python will give result as : shan’: 1, ‘James’: 5) and if you give a print() 1° >>> print (Winners) a in ada wey of prt {‘Nihar': 3, 'Rohan': 5, ‘Zeba': 3, ‘Rosha sae ei detec nO 2 "James": 5}1cronaats 25 a i pove aye of ater can still make out the keys and values, but i te se le ed presentable ? \y way of printing dictionary in a way that mal there certainly is a way. For this, you need to import json module by giving statement wot json (recall that in a program the import statement should be given at the top.) pps en OU can use the function dumps()) of json module as per following syntax inside print( )+ son.duros(, indent» >» print(json.dunps (Winners, indent = 2)) { swihar" : 3, Dictionary name srohan"? 5, *zeba": 3, —.. * Keyvolue pairs in separate lines and 2 space in front of every Roshan {ine because you gave value 2 for indent (Indent = 2) syanes": 5 } 937 Counting Frequency of Elements in a list using Dictionary Since a dictionary uses key-value pairs to store its elements, you can use this feature effectively if you trying to calculate frequency of elements in sequence such as lists. You can do this as: © Create an empty dictionary # Take up an element from the list List (first element 1st time, second element 2nd time and so on) © Check if this clement exists as a key in the dictionary : Ifnot then add {key:value} to dictionary in the form { List-element : count of List-element in List} Following program illustrates this, But before we move on to the program code, it will be good if we talk about an interesting and useful function split() that you can use with text to split it in words, (it will come handy especially if try to find frequency of words in a sentence or in a text file). The split() works on string type data and breaks up a string into words and creates a list out of it, e.g., >>> text = "This is sample string” >>> text = “one, two, three” >> words = text. split() >>> words = text.split(", ") >>> words >>> words Uthis', '4s', ‘sample’, "string" Cone’, "two", ‘three’} a si AS SESS STF RT OTE {tus pes ata ods he eof never (), There ered Is namely were By default split() breaks up a text based on white spaces, but you can give a separator character €8,, see sample code on the right above. Now consider the following program. aCOMPUTER SCIENCE WITH PYTHON ~ yy 296 9.4 Program to count the frequency ofa list-lements using 2 dictionsny P : | counting frequencies in list ym import json ['this', "is', ‘ay ‘super’, sentence = "This is a super idea This \ idea’, "This', ‘idea’, ‘wit}', idea will change the idea of learning” | tenange’. ‘the’, ‘idea, words = sentence. split() (soft, *Tearning’] \ 80 nett ( | for one inwords: eye ‘ key sone AL (hey scountof hey) if key not ind: tw dictionary j count sverdsccint(key)—_/ [key] = count | | print("Counting frequencies in list \n", words) print (json.dunps(d, indent = 2)) The output produced by above code is shown on the right a 9.4 DICTIONARY FUNCTIONS AND METHODS Let us now talk about various built-in functions and methods provided by Python to manipulate Python dictionaries @ len{ ) method This method returns length of the dictionary, Le, the count of elements: (key:tulie pairs) in the dictionary. The sya to use this method is given below : : Jen() = Teles dictionary mam Example : argument and returns an integer 2»employee « (iasu : “Joh, “salary : 10000, ‘age’: 24) 222 1en(erployee) 3 —_ ji The lent } returns the evant of Aeystalae pn fom the sateray __ Pemployee|"dept’)} «Sales! >>>len (employee) 4 a Se oher alding a new entry the _2he clear{ ) method ‘eft cred This me | Abis method removes all items from the dictionary and the dictionary becomes empty diction? Post this method. The 16a Th 1d is given below : ‘Blethonary-etear(y ~ Takes no argument . returns no palue Bice $s _DICTIONARIES, ow ple: Lait Employee = (‘name ohn’. » >» Employee. clean() “5m Employee a € See. now the Alctionary emp The clear method does not de dictionary, x If, however, you want to delete the dictions JUSt delet. abject remains, then yoy Onary i ary iil 1 can use del slateme, alone For example : rents inside the © the dictionary, tionary is also r iti >>> Employee = removed and no ionary name (name: ‘394 lary : 199 [Siti 99> del Emplo ee . caemplivec ill dtee The ea) removes at the elements of a dictionary and makes. Traceback (most recent ca) last); sos Fille ">> empl {salary : 10898, ‘dept’ >>> enpli.get (‘dept’) | ‘Sales: key if key exists in the dictionary. If you only specify the ei ed value for gi en key if key exis ' a an ion does net exist in the dictionary, then Python will return error >>> empl get desig’) / Traceback (most recent call last) ae File "", line 1, in empl1. get (‘desig’) Jotined Nametrror: name ‘desig’ isnot ‘Sales’, ‘age’: 24, ‘name’ : ‘John’ te error message as sccond argument ; ‘ also specify your own custom " place of error, you can | >>? empl1.get(‘desig’, "Not yet") reer yet! ot found") >>> empl .get(‘desig,, "Error! ! Key n “Error! Key not foundCOMPUTER SCIENCE WITH PYTHON ~ xy “items{ ) method ic of (key, value) tuples. Not | Fu: method returns alo th tes nthe dtr sa evens kkey, ples. Note that these are returned in no particular order. items() - ; ~ Takes no argument ; Returns a sequence of (key, value) pairs Example : The adjacent code gives output as; e employee = {'nane! : "Johni, ‘salary’: 10000, ‘age’ : 24} (‘satary', 10000) i myList = employee.items() Cage’, 24) for x inmylist : ( tnane', "John! ) print (x) As the items( ) function retuns a sequence of (key value) pairs, you can write a loop having two variables to access key value pairs, ¢,., The adjacent code gives outputas: i enpl = {‘age': 25, ‘name: ‘shuvan', ‘salary’: 20000} | age } seq enpl.itens() thuvan name for ky, v1 in seq: 20000 salary print(val, key) This loop has two iteration variables ky, vl because the function items() returns a list of tuples and ky, vl is a tuple assignment that successively iterates through each of the key-value pairs in the dictionary ie, each key-value pair is assigned to loop variables ky and vl at a time. 5, The keys( ) method You have already worked with this method. This method returns all of the keys in the dictionary as a sequence of keys (in form of a list). Note that these are returned in no particular order. “.keys() anita = Takes no argument ; Returns a list sequence of keys Example : >>> employee {'salary : 10000, ‘dept’: ‘Sales, ‘age’ : 24, ‘name’ :‘John'} >>> enployee.keys() [salary, ‘dept’, ‘age’, ‘name'] - The values( ) method ‘This method retums all the values from the dictionary as a sequence (a list), Note that these are Teturned in no particular order, The syntax to use this method is given below : .values() ~ Takes no argument ; Returns a list sequence of values Example : >>> employee {salary : 10000, ‘dept’ : ‘Sales’, ‘age’ : 24, ‘name’: ‘John'} fo» employee. values() [10208, ‘sale: 24, "John’}y ‘ DICTIONARIES oot ypdatel ) method 2 ‘ey: 5 1, js method merges Key : value pairs from the new dictionary into the original dictionary, adding acing as needed. The items in the new ai i ales "realy there with the som oe cteonary are added tothe old one and override qhe syntax to use this method is given below : pre 7 This dictionary’sierts will be takert we , update ( >? employeel = {iname' : “Iohn’, ‘salary : 1¢280, ‘age’ : 24) ements of dictionary >>> employee? = {‘nane’ : ‘Diya’ i i set ave overridden the Ployee2 = {'nane’ : ‘Diya’ , ‘salary : 54008, ‘dept’ : ‘Sales'} a of dictionary — >>> employeel update (employee2) feager! having the sate heys >>> employee vifos ‘nae’ ard “salary” {salary : 54920, ‘dept’ : ‘sales’, ‘nae’: ‘Diya’, ‘age’: 24} >>> employee2 {salary : 54000, ‘dept! : ‘Sales’, ‘name’ : ‘Diya'} 1. Why are dictionaries called mutable types ? | 2 What are different ways of creating dictionaries ? | 3. What values can we have in a | dictionary 2 | 4 How are individual elements of dictionaries accessed ? 5. How is indexing of a dictionary ferent from that of a list or 2 string ? §& Which of the following types qualify to be the keys of a dictionary ? (6) String (b) tuple (c) Integer (@) float (e) list (f) dictionary 7% Can you change an element of 2 Yequence or collection ? What if the collection is a dictionary ? What if the Hequence is a string ? S Wat do you understand by ordered Collection and unordered collection ? 4, int examples a eaisting dictionary ? & Alctionary and if so, how ? How do you add key:value pairs to #7) ‘This method is equivalent to the following Python statement: for key innewDict.keys() snewOict 1s employee2 here dictionary[k]=newict[k] DICTIONARY HANDLING = ) AND |ANIPULATION (peAnrUATiON Progress In Python 9.41 Sei This PrP session aims at strengthening skills related to Dictionary handling and manipulation. pep dece vi ve have come to the end of our chapter. Let us With ss wt we have learnt s0 far. quickly revise w Gan you remove key: value pairs from &COMPUTER SCIENCE WITH PYTHON _ 300 ler Us REVISE / Jemenes inthe form of a keyvatue pair thet associate Keys 10 values, Dictionaries ore mutable with el 4 The hays of a dictionary must be of iminitable (yPes- iat 1r moppings oF hashes. %1 Dictionories are also called associative arrays oF mo — “dmenetn, In Python dictionaries, the elements (hey: value pairs) are unordered ; one Cr inot access Per speclficondey, through {) and through dici() constructor, jictionories c ted in multiple ways — : snares ain et ot ita in syntax. But for addition, the hey must noc exig In Dictionaries, the updation and addition of elements are si in the dictionory and for updation, the key must exist tn the dictionary. hal . er e pop( ) method. % To delete an clement, you con cither use del statement or use pop Some useful dictionary methods and functions are : fen(), ctear(), ge). Krems(), keys), values() and updarep, ih dictionary % 4 Keys of a dictionary must be unique. % & ork % % The membership operaiors in and wot in only — The clear( ) function removes all the items from ictivnary but the dictionary ubject exists as an empty dictionary. % The del statement removes a dictionary object atong with is items. After this, there exists no dictionary object Solved Problems (er A cs 1. How are dictionaries different from lists ? Solution. The dictionary is similar to lists in the sense that iL is also a collection of data-itemsjust like lists BUT itis different from lists in the sense that lists are ‘Sequeutial collections (ordered) and dictionaries are non-sequential collections (unordered). Inlists, where there is an order associated with the data-items because they act as storage units for other objects or variables you've created. Dictionaries are different from lists and tuples because the group of objects they hold aren't in any particular order, but rather each object has its own unique name, commonly known as a key. 2. How are objects stored in lists anc dictionaries different ? Solution. The obje or values stored ina dictionary can basically be anything (even thenothing, type defined as None), but keys can only be immutable type-objects. eg., strings, tuples integers, etc. ° 3. Wher are dictionaries more useful than lists ? Solution. Dictionaries ean be much more useful than lists, For exemple, suppose we wanted © Store all our friends’ cell-phone numbers. We could create a list of pairs, (name of friend, phone ‘number), but once this list becomes long enough searching this list for a specific phone numbst Will get tite-consuming. Better would be if we could index thelist by our friend's name. Ts Precisely what a dictionary does. Gar sequence operations such as slicing and concatenation be applied to dictionaries ? Why ? io Solution. Noy Sequence operations like slicing and concatenation cannot be appl, sctionaries. The treason being, a dictionary is not a sequence. Because it is not maintal j Any specific order, operations that depend on a specific order cannot be used.coupler 9: DICTIONARIES Why can't Lists erm be used as keys ? 5 Solution. Lists cannot be used as key’ i ol ts eys in a dicti ‘Jictionary can have only keys of imimutseae? because they are mutable, And a Python ¢ types. Ifthe auditio rw key:valie &_ Ifthe audition of mew key-value pair causes the size of the dictionary to grow beyond is original » keyoud ils original size, an error occurs. True or false ? Solution, False. There cannot occur an . an ertor because Dicti . Soli gow or shrink on and as-needed! basis -ause Dictionaries being the mutable types, they Consider the following code fragments. What outputs will they produce ? () aDict = {"Bhavna':1, “Richard":2, “Firoza™:1@, “Arshnoor”: temp =@ ° 128, nor” :20) for value in aDict.values() : temp = temptvalue print(temp) (i) adit = { "Bhayna":1, “Richard":2, “Firaza":20, "arshnoor™:28} tenp =" " for key in aDict: if temp ¢ key print(temp) *zeshnoor™:20) (ii) avict = { 'Bhovna’:2, "Richard™:2, "Firora"s20y k= “Bhavne ve-l 4 k in aDict: abiet[k] print(aDict) Solution. 33 (i) Richard — 1, 'Richard’ :2, ‘Firoza’ = 10% *arshnoor’ 20} ny soork seith Keys of @ dictionary ut le check for the presence of a value in a (if) { "Bhavna" 8, The membership operators dictionary, you need to write jane that print the correspon acoule. part of given dictionary or secks whether the given value es print an error mess Write a Python prose fakes a value and ¢ i ding key otleerevise nol, If itis, it should Solution. dicta = (0 :"Zero", 2 3 :*Three", 4 s*Four", 5 :°FAve") ans = "y" while ans =* ‘y' on ans == 'Y": val = input (“enter value print(*value", val, end © for kin dict : if dicta[k]== val: print ("exists at”) 2 :*TWo"s k) else: print(*net found”) ane = input ("want to eneck more values? (yin) =")COMPUTER SCIENCE WITH FrMHON _ 302 yea ond “Zt tree sb a EIST leg, hyn” or 19, Marks of theee students “Sun! itionarssreepetiely +70, 3178) a (24,2570, 3¢ Parte 270, 2188, 3! areeme herr deta along th tet asad hen rit hut g a ores the marks det Cratea ested dictionary that shown below : | Hane | yma j Subject (key) Marks (value) : 40 3 80 3 ee ane Zeba Subject (key) Marks (value) a 70 2 80 GI 3 90 tose & Sunitd Subject(key) _Marks(value) Me 1 40 he 2 7 ii 3 70 Solution, OL (2:40, 25 70,3: 70) Ns a0 62) : om B= (2 $0, 3: 99) del i, *Ryna” : d2, "Zeta" : d3} Typ for x in ds.keys() + print (" ] print (x) : print (* Subject(key)", '\t, "Marks(value)*) 3 for y in eax}. keys() : print (°°, y,\t\t, dapxdty]) 4 print() : 10. Consider a dictionary my_points with single-leterheys, cach followed by a 2-element tuple representing ‘ coordinates ofa point ins an x-y coordinate plane, my_points = { tat (4, 3), 'B' : (1,2), "et 5 (5, a) ) ’ Writea program to prin the maxirtwm value from within al of he values tuples a see inde ' For example, maxinnn for 0% index will be comy puted from values, and, ie. all the entries at tk indexi* the valne-tupte.JONARES 303 + on “ha, om? ts, ri theres in flloncing format: raxinun Value at index(ey_petmts, e) = § raxinun Value at index(eypetnts, 4) 23 setution mypoints = ("as (4, 3),'¥: (1, 2), ! Pring highest = (8, 6] , hen inte = 0 for » in range(2) : init «8 for b tn ey_potnts.keys(): val = ay. points[b) {a} IF inte oe 82 highest{a) = val inte se a Af val > highest[a) = highest (a] = val print ("Maximus Value at index(ay_points, *, a" 5.1) } GLOSSARY 2 ae ‘Amuse, unordered collection wth elements inthe form of @ key-value pai thet extotate keys to velue. | atonery | mopping inking of @ her wth © value rough sme intemal neton (hath arto. Mestng Having on element of similar type inside enother element leotip ——_-Adictonary opertion that fates Ley and finds tha corresponding volve. Assignments Type A: Short Answer Questions/Conceptual Questions Jered collection of objects 7 dictionaries ? ‘cannot always be used as keys in a dictionary. What is the 1. Why is a dictionary termed as an unord) 2. What ype of objects can be used! as Keys int 3. Though tuples are immutable type, ye! they condition to use tuples as a hey in a dictionary ? "y store in: (e) ictionary-values 2 (b) dictionary-keys ? What all types of values can yor is contents, it, can you sort the contents of a dictionary 7 CCan you change the order of dictionary Inno more than ane sentence, explain the following Python error and how it could arise: Typetrrer: uohashable type: '14st" Can you cheek fora vale inside a deionay wi 8 dictionary using in operator ? & Dictionary is a mutable type, which means you cay modify its contents ? What all is modifiable in a dictionary ? Can you modify the keys of 2 dictionary ? 9. How is det 1 and det D[ehey>] different from one another if D isa dictionary 7 ow is clear) function different from del edit statement? gin operator? How will you check for a value inside10s Understa nding Sorting Fg soa Introduction What is Sorting 7 ‘a INTRODUCTION In general terms, as you see in many junior level activities, sorting means — from a pile of Miced objects, picking and placing identical objects into separate groups. But in computer tems, sorting has different meaning. Computers often deal with sequences having multiple tlements, Sorting in computer terms means arranging these ¢ ‘ments ina specific order cs increasing order or decreasing order. In this chapter, we shall discuss what sorting means in ‘computer terms and two techniques of doing it — bubble sort and insertion sort.COMPUTER SCIENCE WITH PYTHON . t 10.2 WHAT IS SORTING ? arranging elements in 2 spel oe oe decenaing é song oi noose HY mo jncreasing order of descen ta ™ AWE ZED ee Sorin, ik compel te 3 ding order will be: {efecs to arranging eleme the sored sequen in aces specie order cee 5 [12,4 5,6, 8) descending a and in decreasing order, it would be: fig ea boi : y rectly in your day to day life, ¢g, if yoy ‘sorting ues’ unknowingly, indirectly 9 day te eg You have used oe of containers with different sizes, what do you do? v0 Pu 7 Bae aan ee en emaler than it into it, further smaller Into it an ; container fi ‘Smallest container in the last. This is sorting only. (sce below) vl uu? Uw 4 Similarly, when you arrange your books in the order of their thickness, it is also sorting, There are mulliple ways or techniques or algorithms that you can apply to sort a group of iutibte sort, heap’ sort, quick sort etc. Repeat orl ele In this chapter, we shall talk about two sorting algorithms ~ bubble sort andl insertion sort, 10.3 BUBBLE SORT The basic idea of bubble sortis to compare two adjoining values and exchange them if they are notin proper order. To understand this, have a look al figure 10.1 (on next page) that visually explains the process of bute sort For instanee, in following, figure (Fig. 10.1) unsorted array is being sorted in ascending order using bubble sort. In every pass, the hea its appropriate position in the bottom Renault iest element settles as Algorithm —8u28te SoRT IN Linear List Races 2. Fort=L TOU 2 ForJ=LT0[ (u-1)- 1] # need not consider alread A that ds why (u—1)—1, 3. Af AR[J] > AR[D +2] then + swap the values ly settled heavy elements “ tenp = AR] 5 AR[I) = AR[I +1) 6 AR(I +1] = temp #endof if : end of inner loop 7. EW, # end oF outer 1oopgeet 10° UNDERSTANDING SORTING 305 Two adjacent elements being compared are shown in shaded boxes. m ro Fg Fg |S pep ewe Felt oe tele be Gey Be : 3 [9 19 Ta] ys22 f i i 4t2 f [2] v7? Pr a7] 7 spy Lr ial 7 [Baltes [a ‘ il mess ! 4 aie poe ‘Again repeating the 2amo process (heaviest a) a3: fomep 5 5 = 3 3 5 13 (he) 3 a 7 7 3 ww [erence ays > a t: ie 2 ec a az iy a W Wir 19 ewan z 4 £ 4 ely as # # 8 = [22] (Secone L28 heaviest s 5 s] comes | 331 | sway 2 2 ares [21 wap A spprepeate| =| ik aie TV 4ro change = S|, “Desson) [13 ! air 2 fa7]y Tt swap 24 els 4 4 aly ow 9 3 1 19 (os 181 a 28 28 28 heawest) [2e rt 2 swap 5 + t : a az] $I ST a = ig Hi aye? ss tr a7 | W 7 MW 19 | 19 19 20] 2 22] (nextheaviesty [2s a frocrance 2), 2 5 [ot femap 4 3 4 [=] ity is 3 = fr 7 hi? | 9 19 19 2 Ea [zs] Figure 10.1 Bubble sort. Wecan now write code for bubble sort as shown in algorithm on previous page. Notice we have Kept in mind that since one heavy element settles at its right position in one complete iteration, Next time, we need not compare that element. That is, after first complete iteration, we can have 1)ess number of comparisons in next iteration (as 1 heaviest clement has settled in the end) ; alter second complete iteration, we can have 2 less number of comparisons in next iteration (as 2 heavy elements have setiled in their correct position by now) and so on. Following Program shows Python code for the same, the bubble sort technique.‘ COMPUTER SCIENCE wire, Pn, 30 " | 10.1 Program to sort a list using Bubble sor. alist «[ 15, 6, 13, 22, 3, 52,2] 4 —— We have taken a pre-iniiaticed ty (8M input a Tt prior yo nye You asaem print (“Original list 4s :*, alist) com ere tar 9 Tt peor t0 sorting ip n= len(alist) # Traverse through all List elenents for 4 inrange(n) : * Last i elements are already in place This expression will ensure that we for J in range(o, n-1-1): compare the heavier ee Rtraverse the list from@ ton-4-1 Thea sete at corer postin, # Swap 4¢ the element Found 4s greater # than the next element if aList[J} > alist{j+4] : aList(J], alist[J +1] = alist[j+1], alist[j] Print (“List after sorting :", alist) The output produced by above code is like. | originat ist is = OS, 6, 13, 22, 3, 52, 27 F | List after sorting : (2, 3, 6, 13, 15, 22, 82] Coleuloting Number of Operations Let us now consider number of operai Operations is an important aspect to know CPU time. Two programs with different logic can deliv will accomplish the {ask in lesser number of operations. | Tocalculate number of operations taking place tions taking place in above Program. Number of W as more number of operation. S Means more usage gf the same output but the efficienteny in above program, let us keep the things simple: 1 operation per statement that will include assignment, comparison and steap may take more than 1 operation to ering it as 1 operation for simplicity sake and underst Now consider this first : © Weil conside comparison swap ee [Please note Perform but we ar ‘anding sake] Wa. of Operation salist = (35, 6, 13, 22, 3, 52, 2] + print ( “Original list 4s = len(atist) alist) for 4 4n range(n) : F Last 4 elements are already in Place so aga for 4 tn range, nt-2) & | teauisesy > stssetsnay ; + conparsoree —] [ MASH), aLGstLJet] « aLtst( goa), alist(y] X<__tawapon___ } BrInt List after sorting: ') alist)yr peow 10: UNDERSTANDING SORTING ff $0 otal number of operations taking place in above code can be calculated as: Operations in Line 1+ Line 2+Line3 Ee =3 operations + Operations in Lines 4.7 (for loo a3 Eg) + Operation in Line 8 P) (Vo be calculated) Eq = 1 operation Let us calculate operations in Outer for loop : Outer for loop repeats m times [for n as 7, it is repeating 7 times} So total number of operations in outer loop, for loop are : Operations in Line 4.7 x7 times =Line 4=1 op = Line 5.7 = Inner for Loop Inner for loop is repeated (it~ i—1) times (s0 6 times first time, 5 tirmes second time, 4 times third tinte and so on) = Line 5=1o0p +Line 6 =1 op | + Line 7=1 op =3 ops Inner for loop performs 3 operations in single iteration | | So outer for loop operations are : | Ist iteration (= 0) | =1 op (Line 4) +3 ops (Line 5-7) x 6 times =19 ops inner for loop: 2nd iteration f= 1) =1 op (Line 4) +3 ops (Lines 5-7) x 5 times = 16 ops 3rd iteration (7 =2) = 1 op +3 ops x 4 times = 13 ops Ath iteration (7 =3) =1 op + 3 opsx 3 times = 10 ops Sth iteration (7 =4) = 1 op +3 ops x 2 times =7 ops 6th iteration (7 =5) =1 op +3 ops 1 times = 4 ops 7th iteration =1op+3x0 times =1o0p Total ops in outer for loop = 70 ops i So putting this value in reference eqn. (1) given above 4 ops Total operations =3 ops +70 ops +1 op One above given Bubble sort program takes approximately 74 operations when n is 7 for n=8 it will be about = 96 ops for m=9 it will be about = 121 ops | for n=6 it will be about = 55 ops forn=5 it will be about = 39 opsCOMPUTER SCIENCE WITH Pry, a So with larger values of 1 it increases. - Calculating number of operations this way will be cumbersome. Let us concentrate On cru operations taking place — Comparisons jd Suappings as these are major operations taking pj,. Total number of comparisons in bu [evens @v—2)40N-9+(N-D HD) om ble sort is ee (2)+0)=NN-1)/2ie, zn? Let us see how we have reached at this number : a ‘The outer Loop iterates once for each clement inthe given sequence Se N times, where N isthe number of elements in the given sequence. The inner loop iterates N ~1 times for first iteration of outer loop, N-2 times for second iteration of outer loop, N ~ 3times for third iteration of outer loop and this process continues, For the first iteration of the outer loop, when we are trying tO place the largest elementig] its correct position , N'~ 1 comparisons takes place {the first comparison is made between; the frst and second elements, the second comparison is made between the second and thing) elements, and so on until the (N - 1)" comparison is made between the (N—1)" and the N" clement.] | © For the second iteration of the outer loop, there is no need to compare against the last ‘element of the list, because it was put in the correct position on the previous pass, Therefore, the second iteration requires only N - 2 comparisons. ! © Similarly the third iteration requires (N - 3) comparisons, and so on. | Thus, Pass Comparisons 1 N-1 2 N-2 3 N-3 N-l 1 This gives us total number of comparisons as : (N=1)+(N =2) + (N=3) + (N =A) + ON — De) (I) =N(N = 1) /2= NF The number of swapping will vary depending upon th ments of the sequence : © In the best case, ie, when all the clements of the sequence are already sorted (fey i8 desired sort order), no swapping will take place. =n comparisons +0 swappings = N? ops ° Havre. in the bilo ie, when al elements are in opposite order, every comparisee ingen *N 2 comparions +N? swappings = 2N? ops we determine i y i kt crf otters es me program than programs with higher epee seein coud me SO |110: UNDERSTANDING SORTING owe Now that we have talked about . algorithms, let us quickly recap hove bane oF operations and efficiency of a bubble sort Look at the figure below that shows the wor every pass and changes after eve pass are shown with colour, king of Bubble sort, ie, it shows the array alter TY Swap takes place. The elements being compared in every f original 14st ts: (15. 6, 13, 22, 3, 52, 2) weeetteration 1 of outer Toop r ateratids 4d of = jon 4 of outer Toop — ust after pass 1: (6, 25, 13, 22, 3, 52, 2) Use after pass 1: (3, 6, 13, 2, 15, 22, 52) \ bus after pass 2: (6, 13, 25, 22, 3, 52, 2) List after pass 2: (3, 6, 13, 2, 15, 22. $2] | Uist after pass 3 (6, 13, 15, 22 32,2) List after pass [3, 6, 2, 23, 15, 22, 52) Ust after pass 4: (6, 13, 18, 3,°22, 52, 2] List after pass 5: (6, 13, 18, 3, 22, 521 2] —Iteration 5 of outer Toop —- List after pass 6: [6. 13, 15, 3, 22, 2, $2] List after pass 1: (2, 6 2, 23, 15, 22, 52] List after pass 2: (3, 2, 6, 13, 15, 224 52) —tteration 2 of outer loop —- List after pass 1: (6, 13, 15, 3, 22, 2, $27 Ust after pass 2. (6, 13, 15, 3, 22, 2, 52) Ust after pass 3: £6, 13, 3, 25, 22,2, 52)” bist after pass List after pass 4: (6, 13, 3, 25, 22, 2, 52) List after pass Sz (6, 13, 3, 15, 2, 22, 52] —tteration 6 of outer Toop — 2 (2, 3, 6, 13, 25, 22, $2) —tteration 3 of outer loop —- List after pass 1; (5, 23, 3, 15, 2, 22, 52] List after pass 2: (6, 3, 13, 25, 2, 22, 52] List after pass 3: (6, 3, 23, 15, 2, 22, $2) Ust after pass 4: (6, 3, 13, 2, 15, 22, 52] WA) current element CE 155 | 183 torn by {poston and ban pu co ‘element ( 11) at Hs correct postion [ss] oq G3] La ayaa] 14.25] 185] IFS erat tonone> ori [i163] Done. Sorted} to ght oy 1 positon and then pa ct lament (13.4) a ts correct POR”10: UNDERSTANDING SORTING docode for sortin, eps orting a Sequence A using inserti ——— yasgiven below. Notice that loop is started from nd ‘clement qawards (ie., index 1 onwards) because left to it is single element sub-list and a single clement list is always sorted. (Insertion sort passes: through |ford=1ton ' y : 3 key=A(i], J=ina 3] | whdde(j > 6) and (Af) > key)do 3) | A(j +1) =ACj) 3 jeje. ° AJ +1] = key python code for the same will be as listed in following program : alist = [15, 6, 13, 22, 3, 52, 2] op == print (“Original list is :", alist) for 1 in range(1, len(aList)) : key = alist(1) jei-a while j >= @ and key < aList[4] : aList[j+1]=aList[j] #shift elenents to right to make room for key je3-2 else: aList[j +1) = key print (“List after sorting :*, alist) p 10,2 Program to sort a sequence using insertion sort Output produced by above program is as shown below : |) original Vist is : (15, 6, 13, 22, 3, 52, 2) | Uist after sorting : (2, 3, 6, 13, 25, 22, 52] Number of Operations ‘As we mentioned during bubble sort discussion that two costly operations are comparisons and swapping/exchanges. Let us concentrate on these two costly operations while considering number of operations in insertion sort. Look at insertion sort code given below with highlighted comparison and exchange operations. for 4 in range(1, len(aList)) = j key = alist[i] jei-2 while j>=@ and key parteeseus REVISE LeT t 2 & ‘sorting of on array means arrongi ed and exchanged if Hey are ROE ues are compa? eq. In bubble sort, the adjoining ¥e % ing the array elements ino specified order. repeated until the entre orray is sorted. ied otan oven son each scesivciement picked Ise Ived Problems ; order using (i) Bubble Sort (ii) Insertion Sort, 89, 20, 31, 56, 20. Sort this array’ in ascend 89, 20, 31, 56, 20 Given an array Solution, Given array is (i) Bubble Sort " I 89, 20, 31, 56, 20 i 1126, 89, 31, 56, 20 TI 28,31, 89, 56, 20 (Bold elamenis sapit m1 IV 28, 31, 56, 89, 20 tat thay are 1 v 31, compa a v 20, 31, 56, 20, 69 eas) I 31, 56, 20, 89 VIT 28, 31, 56, 20, 89 VIII 26, 31, 20, 56, 89 IX 28, 31, 20, 56, 89 X 28, 31, 28, 56, 69 XI 28, 20, 31, 56, 89 (As you can see that Bubble Sort is taking up more number of operations (as more iterations) 89, 20, 20, 20, 20, than insertion sort to sort this same array (a very small array, though) Given the following steps to sort an array, which sort is this ? 62 4 4 4 4 Solution. Bubble sort. Which of the following sorting methods will be the best ficienty, considering the fact that the sequence size is (A) Bubble sort Solution. For smaller sized compared to bubble sort. not very large ? (B) Insertion sort You are asked to sort 15 randomly generated numbers. (A) Bubble sort You should prefer i (B) Insertion sort Solution. Insertion sort is a better choice for Small sized seq juences, {ii) Insertion Sort 20, 31, 89, 31, 31, 89, 31, 56, 20, 31, 56, 56, 56, 89, 56, COMPUTER SCIENCE WITH PYTHON In proper order. This process 5 cppropeiate postion Inthe previcusly sorted erry, if number of swappings done, is the only measure f Sequences, there are lesser number of swappings in insertion sort 85319: RSTANDING SORTING 1p: noe intenance work, i tof the miairl i YoU are entrusted wit £ an order, at the end of cach day. The ideal choice ine Ofrearvanging the library books in ashlfIn (a) Bubble sort ©) Insertion vo cowtion Insertion sort castle the follow Ist: 132, 33, 5, 2, 14, 4, 22, 39, 34, op ‘ ing is av , she following is a view ofa sort gn 1m Progress (after a few passes) ofthe above list. Identify the sorting oritha sed 2 1, 5, 14, 22, 32, 33, 34, ola }, 34, 39] 1-944, , “A, 2, 5, 14, 33, 22, 39, 34, solution: (2) Bubble Sort —(b) Insertion sort _—_ Oe atrill tite following list Look like oe ;, Wate ef ater 3 passes of insertion sor algorthom ? Show thelist after every pass. = 7 n 15 10 gelution. Elements being compared are shown in black shaded cells. First pass 16 ay u 15 10 No swapping - 16 1g u 15 10 Second Pass A 16 19 l nn 15 10 16 19 | i 15 10 ic a ee i 16 9 15 10 Third Pass iW 16 WW 5 10 n 16 vy 15 10 | SS u 15 16 » |. © Itong a !nwkich situation, would you prefer bubble sort over insertion sort ? Sltion, Bubble sort would be ideal sorting technique for situations where data can be read only i, Uentially (¢ , data stored on magnetic tapes). As bubble sortalso compares two adjacent records, be suitable (or such a situation. But, nowadays, such a situation is rare.