97

UNIT IV

LISTS,TUPLES,DICTIONARIES
Lists: list operations, list slices, list methods, list loop, mutability, aliasing, cloning
lists, list parameters; Tuples: tuple assignment, tuple as return value; Dictionaries:
operations and methods; advanced list processing - list comprehension; Illustrative
programs: selection sort, insertion sort, merge sort, histogram.

4.1 LIST:
Python offers a range of compound datatypes often referred to as sequences.
List is one of the most frequently used and very versatile datatype used in Python.
Like a string, a list is a sequence of values. In a string the values are character , but
in a list they can be any type.

4.1.1 List Creation:

In Python programming, a list is created by placing all the items (elements) inside
a square bracket [ ], separated by commas.

It can have any number of items and they may be of different types (integer, float,
string etc.).

Example:

# empty list
my_list = []

# list of integers
my_list = [1, 2, 3]

# list with mixed datatypes

my_list = [1, "Hello", 3.4]
 98

Also, a list can even have another list as an item. This is called nested list.

# nested list

my_list = ["mouse", [8, 4, 6], ['a']]

4.1.2 Accessing Elements in a List:

There are various ways in which we can access the elements of a list.

4.1.2.a List Indexing

We can use the index operator [] to access an item in a list. Index starts from
0. So, a list having 5 elements will have index from 0 to 4.

Trying to access an element other that this will raise an IndexError. The
index must be an integer. We can't use float or other types, this will result
into TypeError.

Nested list are accessed using nested indexing.

Example 1:
>>>my_list = ['p','r','o','b','e']

>>>print(my_list[0])
# Output: p

>>>print(my_list[2])
# Output: o

>>>print(my_list[4])
# Output: e

i)Nested indexing
Example 1:
>>>n_list = ["Happy", [2,0,1,5]]
 99

>>>print(n_list[0][1])
# Output: a

>>>print(n_list[1][3])
# Output: 5

ii)Negative indexing
Python allows negative indexing for its sequences. The index of -1 refers to
the last item, -2 to the second last item and so on.

>>>my_list = ['p','r','o','b','e']
>>>print(my_list[-1])
# Output: e

>>>print(my_list[-5])
# Output: p

4.1.2.b List Slices:

We can access a range of items in a list by using the slicing operator (colon).

Example 1:

>>>my_list = ['p','r','o','g','r','a','m','i','z']
>>>print(my_list[2:5])
# elements 3rd to 5th

>>>print(my_list[:-5])
# elements beginning to 4th

>>>print(my_list[5:])
# elements 6th to end

>>>print(my_list[:])
 100

# elements beginning to end

Slicing can be best visualized by considering the index to be between the elements
as shown below. So if we want to access a range, we need two index that will slice
that portion from the list.

4.1.2.c Concatenating and repeating list:

We can also use + operator to combine two lists. This is also called
concatenation.

The * operator repeats a list for the given number of times.

odd = [1, 3, 5]
Example 1:
>>>print(odd + [9, 7, 5])
# Output: [1, 3, 5, 9, 7, 5]
Example 2:
>>>print(["re"] * 3)
#Output: ["re", "re", "re"]
 101

4.1.2.d Testing Membership in a List:

We can test if an item exists in a list or not, using the keyword  “in” or “not
in”.It returns true or false after evaluating the expression.

Example 1:
>>>my_list = ['p','r','o','b','l','e','m']
>>>print('p' in my_list)
# Output: True

>>>print('a' in my_list)
# Output: False
>>>print('c' not in my_list)
# Output: True

4.1.3 Built in List Methods:

4.1.3.a Adding and Changing Elements in a list
List are mutable, meaning, their elements can be changed
unlike string or tuple.

We can use assignment operator (=) to change an item or a range of items.

Example:

>>>odd = [2, 4, 6, 8]

>>>odd[0] = 1
>>> print(odd)
# change the 1st item
# Output: [1, 4, 6, 8]

>>>odd[1:4] = [3, 5, 7]
>>> print(odd)
# change 2nd to 4th items
# Output: [1, 3, 5, 7]
We can add the element in the list by using append() and extend() method.
Both are used to add items at the end of the original list.
 102

i) append()
We can add only one item to a list using append() method .

Syntax:
Listname.append(object)

Example 1:
>>>odd = [1, 3, 5]
>>>odd.append(7)
>>>print(odd)
# Output: [1, 3, 5, 7]

ii) extend()
To add several items using extend()method.

Syntax:
Listname.extend(seq)

Example 1:
>>>odd.extend([9, 11, 13])
>>>print(odd)
# Output: [1, 3, 5, 7, 9, 11, 13]

4.1.3.b Inserting items to a List:

Furthermore, we can insert one item at a desired location by using the
method insert() or insert multiple items by squeezing it into an empty slice of a list.

Syntax:

Listname.insert(index,object)
 103

Example1:
>>>odd = [1, 9]
>>>odd.insert(1,3)
>>> print(odd)
# Output: [1, 3, 9]

>>>odd[2:2] = [5, 7]
>>>print(odd)
# Output: [1, 3, 5, 7, 9]
4.1.3.c Removing items from a list:
We can use remove() method to remove the given item or pop() method to
remove an item at the given index.

The pop() method removes and returns the last item if index is not provided.
This helps us implement lists as stacks (first in, last out data structure).

We can also use the clear() method to empty a list.

Example1:

>>>my_list = ['p','r','o','b','l','e','m']
>>>my_list.remove('p')
>>>print(my_list)
# Output: ['r', 'o', 'b', 'l', 'e', 'm']

>>>print(my_list.pop(1))
# Output: 'o'

>>>print(my_list)
# Output: ['r', 'b', 'l', 'e', 'm']

>>>print(my_list.pop())
# Output: 'm'

>>>print(my_list)
# Output: ['r', 'b', 'l', 'e']

>>>my_list.clear()
 104

>>>print(my_list)

# Output: []

Finally, we can also delete items in a list by assigning an empty list to a slice of
elements.

Example 1:

>>> my_list = ['p','r','o','b','l','e','m']

>>> my_list[2:3] = []
>>> my_list
Output:['p', 'r', 'b', 'l', 'e', 'm']
>>> my_list[2:5] = []
>>> my_list
Output:['p', 'r', 'm']

4.1.3.d Deleting elements from a list

We can delete one or more items from a list using the keyword del. It can
even delete the list entirely.

Example1:

>>>my_list = ['p','r','o','b','l','e','m']
>>>del my_list[2]
>>>print(my_list)
# delete one item
# Output: ['p', 'r', 'b', 'l', 'e', 'm']

# delete multiple items

>>>del my_list[1:5]
>>>print(my_list)
# Output: ['p', 'm']
 105

>>>del my_list
>>>print(my_list)
# delete entire list
# Error: List not defined

4.1.4.a Python List Methods

Methods that are available with list object in Python programming are
tabulated below.

They are accessed as list.method(). Some of the methods have already been
used above.

Python List Methods

append() - Add an element to the end of the list

extend() - Add all elements of a list to the another list

insert() - Insert an item at the defined index

remove() - Removes an item from the list

pop() - Removes and returns an element at the given index

clear() - Removes all items from the list

index() - Returns the index of the first matched item

count() - Returns the count of number of items passed as an argument

sort() - Sort items in a list in ascending order

reverse() - Reverse the order of items in the list

copy() - Returns a shallow copy of the list

Example :
>>>my_list = [3, 8, 1, 6, 0, 8, 4]
 106

>>>print(my_list.index(8))
# Output: 1

>>>print(my_list.count(8))
# Output: 2

>>>my_list.sort()
>>>print(my_list)
# Output: [0, 1, 3, 4, 6, 8, 8]

>>>my_list.reverse()
>>>print(my_list)
# Output: [8, 8, 6, 4, 3, 1, 0]

4.1.4.b Built-in Functions with List

Built-in
function ,like all(), any(), enumerate(), len(), max(), min(), list(), sorted() etc. are
commonly used with list to perform different tasks.

Built-in Functions with List

Function Description

all() Return True if all elements of the list are true (or if the list is empty).

Return True if any element of the list is true. If the list is empty,
any()
return False.

enumerate( Return an enumerate object. It contains the index and value of all the
) items of list as a tuple.

len() Return the length (the number of items) in the list.

list() Convert an iterable (tuple, string, set, dictionary) to a list.

max() Return the largest item in the list.

min() Return the smallest item in the list

 107

sorted() Return a new sorted list (does not sort the list itself).

sum() Return the sum of all elements in the list.

Example 1:
>>>listone=[‘cat’,’dog’,’lion’,’elephant’,’zebra’]
>>>len(listone)
Output:
5

Example 2:
>>>numberlist=[1,5,7,9,10,12]
>>>max(numberlist)
Output:
12

>>>listone=[‘cat’,’dog’,’lion’,’elephant’,’zebra’]
>>>max(listone)
Output:
Elephant

Example 3:
>>>numberlist=[1,5,7,9,10,12]
>>>min(numberlist)
Output:
1

>>>listone=[‘cat’,’dog’,’lion’,’elephant’,’zebra’,’ox’]
>>>min(listone)
Output:
Ox

Example 4:
 108

>>>numberstuple=[1,5,7,9,10,12]
>>>sum(numberstuple)
Output:
44

Example 5:
>>>numberlist=[10,5,7,9,5,12,1]
>>>sorted(numberlist)
Output:
[1,5,7,9,10,12]

4.1.5 List Loop

Using a  for loop we can iterate though each item in a list.

Example:
>>>for fruit in ['apple','banana','mango']:
>>>print("I like",fruit)

Output:
I like ‘apple’
I like ‘banana’
I like ‘mango’

4.1.6 Aliasing
If two list refers to same object is termed as aliasing.
Example:
>>>one=[10,20,30]
>>>two=one
>>>two[1]=40
>>>print(one)
Output:[10,40,30]
Although this behavior can be useful, it is error prone. In general, it is safer
to avoid aliasing when you are working with mutable objects
 109

4.1.7 Cloning Lists

If we want to modify a list and also keep a copy of the original, w need to
be able to make a copy of the list itself, not just the reference. This process is
sometimes called cloning, to avoid the ambiguity of the word copy.
Example:
A=[81,82,83]
B=a[:]
Print(a==b)
Print(a is b)
B[0]=5
Print(a)
Print(b)

Output:
True
False
[81,82,83]
[5,82,83]

4.1.8 List parameters

When you pass a list to a function, the function gets a reference to the list. If
the function modifies the list, the caller sees the change.

Example:
Def deletehead(t)
Del t[0]
>>>letters=[‘x’,’y’,’z’]
>>>print(letters)

Output:
[‘y’,’z’]

4.1.9 List Comprehension: Elegant way to create new List

List comprehension is an elegant and concise way to create new list from an
existing list in Python.
 110

List comprehension consists of an expression followed by for statement inside

square brackets.

Here is an example to make a list with each item being increasing power of 2.

Example:

>>>pow2 = [2 ** x for x in range(10)]

>>>print(pow2)
# Output: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]

This code is equivalent to

>>>pow2 = []
>>>for x in range(10):
>>>pow2.append(2 ** x)

A list comprehension can optionally contain more for or if statements. An

optional if statement can filter out items for the new list. Here are some examples.

>>> pow2 = [2 ** x for x in range(10) if x > 5]

>>> pow2
Output:[64, 128, 256, 512]
>>> odd = [x for x in range(20) if x % 2 == 1]
>>> odd
Output:[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
>>> [x+y for x in ['Python ','C '] for y in ['Language','Programming']]
['Python Language', 'Python Programming', 'C Language', 'C Programming']

4.2 TUPLE
In Python programming, a tuple is similar to a list.
 111

A tuple is a sequence of immutable python objects. The difference between

the two is that we cannot change the elements of a tuple once it is assigned
whereas in a list, elements can be changed.

Tuple uses parentheses

4.2.1)Creating a Tuple:
A tuple is created by placing all the items (elements) inside a parentheses (),
separated by comma. The parentheses are optional, but is a good practice to write
it.

A tuple can have any number of items and they may be of different types (integer,
float, list, string etc.).

>>>my_tuple = ()
>>>print(my_tuple)
# empty tuple
# Output: ()

>>>my_tuple = (1, 2, 3)
>>>print(my_tuple)
# tuple having integers
# Output: (1, 2, 3)

>>>my_tuple = (1, "Hello", 3.4)

>>>print(my_tuple)
# tuple with mixed datatypes
# Output: (1, "Hello", 3.4)

>>>my_tuple = ("mouse", [8, 4, 6], (1, 2, 3))

>>>print(my_tuple)
# nested tuple
# Output: ("mouse", [8, 4, 6], (1, 2, 3))

# tuple can be created without parentheses

# also called tuple packing
 112

Creating a tuple with one element is a bit tricky.

Having one element within parentheses is not enough. We will need a trailing
comma to indicate that it is in fact a tuple.

>>>my_tuple = ("hello")
>>>print(type(my_tuple))
# only parentheses is not enough
# Output: <class 'str'>

>>>my_tuple = ("hello",)
>>>print(type(my_tuple))
# need a comma at the end
# Output: <class 'tuple'>

>>>my_tuple = "hello",
>>>print(type(my_tuple))
# parentheses is optional
# Output: <class 'tuple'>

4.2.2 Accessing Elements in a Tuple

There are various ways in which we can access the elements of a tuple.

4.2.2.a Indexing
We can use the index operator [] to access an item in a tuple where the index
starts from 0.

So, a tuple having 6 elements will have index from 0 to 5. Trying to access
an element other that (6, 7,...) will raise an IndexError.

The index must be an integer, so we cannot use float or other types. This will
result into TypeError.

Likewise, nested tuple are accessed using nested indexing, as shown in the
example below.
 113

>>>my_tuple = ('p','e','r','m','i','t')
>>>print(my_tuple[0])
# Output: 'p'

>>>print(my_tuple[5])
# Output: 't'

>>>print(my_tuple[6])
# index must be in range
# If you uncomment line 14,
# you will get an error.
# IndexError: list index out of range

#my_tuple[2.0]
# index must be an integer
# If you uncomment line 21,
# you will get an error.
# TypeError: list indices must be integers, not float

4.2.2.b Negative Indexing

Python allows negative indexing for its sequences.

The index of -1 refers to the last item, -2 to the second last item and so on.

Example:

>>>my_tuple = ('p','e','r','m','i','t')
>>>print(my_tuple[-1])

# Output: 't'
>>>print(my_tuple[-6])
# Output: 'p'

4.2.3 Slicing
We can access a range of items in a tuple by using the slicing operator -
colon ":".
 114

Example:

>>>my_tuple = ('p','r','o','g','r','a','m','i','z')
>>>print(my_tuple[1:4])
# elements 2nd to 4th
# Output: ('r', 'o', 'g')

>>>print(my_tuple[:-7])
# elements beginning to 2nd
# Output: ('p', 'r')

>>>print(my_tuple[7:])
# elements 8th to end
# Output: ('i', 'z')

>>>print(my_tuple[:])
# elements beginning to end
# Output: ('p', 'r', 'o', 'g', 'r', 'a', 'm', 'i', 'z')

Slicing can be best visualized by considering the index to be between the

elements as shown below. So if we want to access a range, we need the index that
will slice the portion from the tuple.

4.2.4 Changing a Tuple

Unlike lists, tuples are immutable.

This means that elements of a tuple cannot be changed once it has been
assigned. But, if the element is itself a mutable datatype like list, its nested items
can be changed.
 115

We can also assign a tuple to different values (reassignment).

Example:

>>>my_tuple = (4, 2, 3, [6, 5])

>>>my_tuple[3][0] = 9
>>>print(my_tuple)

# we cannot change an element

# If you uncomment line 8
# you will get an error:
# TypeError: 'tuple' object does not support item assignment

#my_tuple[1] = 9
# but item of mutable element can be changed
# Output: (4, 2, 3, [9, 5])

>>>my_tuple = ('p','r','o','g','r','a','m','i','z')
>>>print(my_tuple)

# tuples can be reassigned

# Output: ('p', 'r', 'o', 'g', 'r', 'a', 'm', 'i', 'z')

We can use + operator to combine two tuples. This is also

called concatenation.

We can also repeat the elements in a tuple for a given number of times

using the * operator.

Both + and * operations result into a new tuple.

Example:

>>>print((1, 2, 3) + (4, 5, 6))

# Concatenation
# Output: (1, 2, 3, 4, 5, 6)
 116

>>>print(("Repeat",) * 3)
# Repeat
# Output: ('Repeat', 'Repeat', 'Repeat')

4.2.5 Tuple Membership Test

We can test if an item exists in a tuple or not, using the keyword in.

Example:

>>>my_tuple = ('a','p','p','l','e',)
>>>print('a' in my_tuple)
# In operation
# Output: True

>>>print('b' in my_tuple)
# Output: False

>>>print('g' not in my_tuple)

# Not in operation
# Output: True

4.2.6 Deleting a Tuple

As discussed above, we cannot change the elements in a tuple. That also
means we cannot delete or remove items from a tuple.

But deleting a tuple entirely is possible using the keyword del.

Example:

my_tuple = ('p','r','o','g','r','a','m','i','z')
del my_tuple
my_tuple
# can't delete items
# if you uncomment line 8,
# you will get an error:
# TypeError: 'tuple' object doesn't support item deletion
 117

#del my_tuple[3]
# can delete entire tuple
# NameError: name 'my_tuple' is not defined

4.2.7.1 Python Tuple Methods

Methods that add items or remove items are not available with tuple. Only
the following two methods are available.

Python Tuple Method

Method Description

count(x
Return the number of items that is equal to x
)

index(x
Return index of first item that is equal to x
)

Example:

>>>my_tuple = ('a','p','p','l','e',)
>>>print(my_tuple.count('p'))
# Count
# Output: 2

>>>print(my_tuple.index('l'))
# Index
# Output: 3

4.2.7.2 Built-in Functions with Tuple:

Built-
infunctions ,like all(), any(), enumerate(), len(), max(), min(), sorted(), tuple()etc.
are commonly used with tuple to perform different tasks.

Built-in Functions with Tuple

 118

Function Description

Return True if all elements of the tuple are true (or if the tuple is
all()
empty).

Return True if any element of the tuple is true. If the tuple is empty,

any()
return False.

enumerate( Return an enumerate object. It contains the index and value of all the
) items of tuple as pairs.

len() Return the length (the number of items) in the tuple.

max() Return the largest item in the tuple.

min() Return the smallest item in the tuple

Take elements in the tuple and return a new sorted list (does not sort
sorted()
the tuple itself).

sum() Retrun the sum of all elements in the tuple.

tuple() Convert an iterable (list, string, set, dictionary) to a tuple.

Example 1:
>>>tupleone=(‘cat’,’dog’,’lion’,’elephant’,’zebra’)
>>>len(tupleone)
Output:
5

Example 2:
>>>numberstuple=(1,5,7,9,10,12)
>>>max(numberstuple)
Output:
12

>>>tupleone=(‘cat’,’dog’,’lion’,’elephant’,’zebra’)
>>>max(tupleone)
 119

Output:
Elephant

Example 3:
>>>numberstuple=(1,5,7,9,10,12)
>>>min(numberstuple)
Output:
1

>>>tupleone=(‘cat’,’dog’,’lion’,’elephant’,’zebra’,’ox’)
>>>min(tupleone)
Output:
Ox

Example 4:
>>>tupleone=(‘cat’,’dog’,’lion’,’elephant’,’zebra’,’ox’)
>>>sorted(tupleone)
>>>print(tupleone)
Output:
[‘cat’,’dog’,’elephant’,’lion’,’ox’,’zebra’]
(‘cat’,’dog’,’lion’,’elephant’,’zebra’,’ox’)

Example 5:
>>>numberstuple=(1,5,7,9,10,12)
>>>sum(numberstuple)
Output:
44

Example 6:
>>>tuple(“programmer”)
Output:
(‘p’,’r’,’o’,’g’,’r’,’m’,’m’,’e’,’r’)

4.2.8. Tuple Loop

 120

Using a for loop we can iterate though each item in a tuple.

Example:

for name in ('John','Kate'):

print("Hello",name)
# Output:
# Hello John
# Hello Kate

4.2.9 Tuple Assignment

Swapping of two variables can be done easily in python. The left side is a
tuple of variables, the right side is a tuple of expressions. Each value is assigned to
its respective variable.
Example 1:
>>>a=10
>>>b=20
>>>print(“before swapping”)
>>>print(a,b)
>>>a,b=b,a
>>>print(“after swapping”)
>>>print(a,b)
Output:
Before swapping
10,20
After swapping
20,10
Example 2:
 121

>>>email=’hodcse@gojaneducation.com’
>>>username,domain=email.split(‘@’)
>>>username
‘hodcse’
>>>domain
‘gojaneducation.com’

4.2.10 Tuples as return values

Tuple function returns more then one values
The built in function divmod takes two arguments and returns a tuple of two
values, the quotient and remainder. You can store the result as a tuple.
Example1:
>>>t=divmod(7,3)
>>>print(t)
Output: (2,1)
Example 2:
>>>quot,rem=divmod(7,3)
>>>print(quot)
2
>>>print(rem)
1
Example3:
Def min~max(t):
Return min(t),max(t)
 122

4.2.11 Advantages of Tuple over List:

Since, tuples are quite similiar to lists, both of them are used in similar
situations as well.

However, there are certain advantages of implementing a tuple over a list. Below
listed are some of the main advantages:

 We generally use tuple for heterogeneous (different) datatypes and list for
homogeneous (similar) datatypes.
 Since tuple are immutable, iterating through tuple is faster than with list. So
there is a slight performance boost.
 Tuples that contain immutable elements can be used as key for a dictionary.
With list, this is not possible.
 If you have data that doesn't change, implementing it as tuple will guarantee
that it remains write-protected.

4.3 Dictionaries
Python dictionary is an unordered collection of items. While other
compound data types have only value as an element, a dictionary has a
” key: value” pair.

Dictionaries are optimized to retrieve values when the key is known.

4.3.1Dictionary Creation
Creating a dictionary is as simple as placing items inside curly braces {}
separated by comma.

An item has a key and the corresponding value expressed as a pair, key:
value.

While values can be of any data type and can repeat, keys must be of
immutable type (string, number or tuple with immutable elements) and must be
unique.
 123

Example:

>>>my_dict = {}
# empty dictionary

>>>my_dict = {1: 'apple', 2: 'ball'}

# dictionary with integer keys

>>>my_dict = {'name': 'John', 1: [2, 4, 3]}

# dictionary with mixed keys

>>>my_dict = dict({1:'apple', 2:'ball'})

# using dict()

>>>my_dict = dict([(1,'apple'), (2,'ball')])

# from sequence having each item as a pair

As you can see above, we can also create a dictionary using the built-in
function dict().

4.3.2 Accessing a Dictionary

While indexing is used with other container types to access values,
dictionary uses keys. Key can be used either inside square brackets or with
the get() method.

The difference while using get() is that it returns None instead of KeyError,

if the key is not found

Example:
 124

>>>my_dict = {'name':'Jack', 'age': 26}

>>>print(my_dict['name'])
# Output: Jack

>>>print(my_dict.get('age'))
# Output: 26

# >>>my_dict['address']
# Trying to access keys which doesn't exist throws error
# >>>my_dict.get('address')

4.3.3 Changing or adding Dictionary

Dictionary are mutable. We can add new items or change the value of
existing items using assignment operator.

If the key is already present, value gets updated, else a new key: value pair is
added to the dictionary.

Example:
>>>my_dict = {'name':'Jack', 'age': 26}
>>>my_dict['age'] = 27
>>>print(my_dict)
# update value
#Output: {'age': 27, 'name': 'Jack'}

>>>my_dict['address'] = 'Downtown'
>>>print(my_dict)
# add item
# Output: {'address': 'Downtown', 'age': 27, 'name': 'Jack'}

4.3.4 Testing Dictionary Membership

We can test if a key is in a dictionary or not using the keyword in. Notice
that membership test is for keys only, not for values.

Example:

>>>squares = {1: 1, 3: 9, 5: 25, 7: 49, 9: 81}

>>>print(1 in squares)
 125

# Output: True

>>>print(2 not in squares)

# Output: True

>>>print(49 in squares)
# membership tests for key only not value
# Output: False

4.3.5 Removing or Deleting Dictionary

We can remove a particular item in a dictionary by using the method pop().
This method removes as item with the provided key and returns the value.

The method, popitem() can be used to remove and return an arbitrary item

(key, value) form the dictionary. All the items can be removed at once using
the clear() method.

We can also use the del keyword to remove individual items or the entire

dictionary itself.

Example:

# create a dictionary

squares = {1:1, 2:4, 3:9, 4:16, 5:25}

>>>print(squares.pop(4))
# remove a particular item
# Output: 16

>>>print(squares)
# Output: {1: 1, 2: 4, 3: 9, 5: 25}

>>>print(squares.popitem())
# remove an arbitrary item
# Output: (1, 1)

>>>print(squares)
# Output: {2: 4, 3: 9, 5: 25}
 126

>>>del squares[5]
# delete a particular item

>>>print(squares)
# Output: {2: 4, 3: 9}

>>>squares.clear()
# remove all items
{}

4.3.6 Dictionary Methods:

4.3.6.1 Python Dictionary Methods
Methods that are available with dictionary are tabulated below. Some of
them have already been used in the above examples.

Python Dictionary Methods

Method Description

clear() Remove all items form the dictionary.

copy() Return a shallow copy of the dictionary.

fromkeys(seq[, v] Return a new dictionary with keys from seq and value equal

) to v(defaults to None).

Return the value of key. If key doesnot exit, return d (defaults

get(key[,d])
to None).

items() Return a new view of the dictionary's items (key, value).

keys() Return a new view of the dictionary's keys.

pop(key[,d]) Remove the item with key and return its value or d if key is

 127

not found. If d is not provided and key is not found,

raises KeyError.

Remove and return an arbitary item (key, value).

popitem()
Raises KeyError if the dictionary is empty.

If key is in the dictionary, return its value. If not,

setdefault(key[,d])
insert key with a value of d and return d (defaults to None).

Update the dictionary with the key/value pairs from other,

update([other])
overwriting existing keys.

values() Return a new view of the dictionary's values

Example:

Here are a few example use of these methods.

>>>marks = {}.fromkeys(['Math','English','Science'], 0)
>>>print(marks)
# Output: {'English': 0, 'Math': 0, 'Science': 0}

>>>for item in marks.items():

>>>print(item)
>>>list(sorted(marks.keys()))
# Output: ['English', 'Math', 'Science']

4.3.6.2 Built-in Functions with Dictionary

Built-in functions like all(), any(), len(), cmp(), sorted() etc. are commonly
used with dictionary to perform different tasks.

Built-in Functions with Dictionary

Function Description

Return True if all keys of the dictionary are true (or if the dictionary is
all()
empty).
 128

Return True if any key of the dictionary is true. If the dictionary is

any()
empty, return False.

len() Return the length (the number of items) in the dictionary.

cmp() Compares items of two dictionaries.

sorted() Return a new sorted list of keys in the dictionary.

Here are some examples that uses built-in functions to work with dictionary.

Example:
>>>squares = {1: 1, 3: 9, 5: 25, 7: 49, 9: 81}
>>>print(len(squares))
# Output: 5

>>>print(sorted(squares))
# Output: [1, 3, 5, 7, 9]

4.3.7 Dictionary Loop

Using a for loop we can iterate though each key in a dictionary.

Example:

>>>squares = {1: 1, 3: 9, 5: 25, 7: 49, 9: 81}

>>>for i in squares:
>>>print(squares[i])

4.3.8 Python Dictionary Comprehension

Dictionary comprehension is an elegant and concise way to create new
dictionary from an iterable in Python.

Dictionary comprehension consists of an expression pair (key: value)

followed by forstatement inside curly braces {}.
 129

Here is an example to make a dictionary with each item being a pair of a

number and its square.

Example:

>>>squares = {x: x*x for x in range(6)}

>>>print(squares)
# Output: {0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}

This code is equivalent to

>>>squares = {}
>>>for x in range(6):
>>>squares[x] = x*x

A dictionary comprehension can optionally contain more for or if

statements.

An optional if statement can filter out items to form the new dictionary.

Here are some examples to make dictionary with only odd items.

Examples:

>>>odd_squares = {x: x*x for x in range(11) if x%2 == 1}

>>>print(odd_squares)
# Output: {1: 1, 3: 9, 5: 25, 7: 49, 9: 81}

4.3.9 Advanced List Processing ~ List Comprehension

Python supports a concept called “list comprehensions”. It can be used to
construct lists in a very natural, easy way, like a mathematician is used to do.
Following function takes a list of strings, maps the string method capitalize to the
elements and returns a new list of strings.
Example:
>>>def capitalize~all(t):
>>>res=[]
 130

>>>for s in t:
>>>res.append(s.capitalize())
>>>return res
We Can write this more concisely using a list comprehension.

>>>Def capitalize all(t):

>>>Return[s.capitalize() for s in t]

4.4 ILLUSTRATIVE PROBLEMS:

4.4.1 The Selection Sort
The selection sort improves on the bubble sort by making only one
exchange for every pass through the list. In order to do this, a selection sort looks
for the largest value as it makes a pass and, after completing the pass, places it in
the proper location. As with a bubble sort, after the first pass, the largest item is in
the correct place. After the second pass, the next largest is in place. This process
continues and requires n−1n−1 passes to sort n items, since the final item must be
in place after the (n−1)(n−1) st pass.
On each pass, the largest remaining item is selected and then placed in its proper
location. The first pass places 93, the second pass places 77, the third places 55,
and so on. The function is shown in ActiveCode 1.
 131

Source code:
def selectionSort(alist):
for fillslot in range(len(alist)-1,0,-1):
positionOfMax=0
for location in range(1,fillslot+1):
if alist[location]>alist[positionOfMax]:
positionOfMax = location

temp = alist[fillslot]
alist[fillslot] = alist[positionOfMax]
alist[positionOfMax] = temp

alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist)
print(alist)
Output:
 132

[17, 20, 26, 31, 44, 54, 55, 77, 93]

4.4.2 The Insertion Sort

The insertion sort, although still O(n2)O(n2), works in a slightly different
way. It always maintains a sorted sublist in the lower positions of the list. Each
new item is then “inserted” back into the previous sublist such that the sorted
sublist is one item larger. The shaded items represent the ordered sublists as the
algorithm makes each pass.

We begin by assuming that a list with one item (position 00) is already

sorted. On each pass, one for each item 1 through n−1n−1, the current item is
checked against those in the already sorted sublist. As we look back into the
already sorted sublist, we shift those items that are greater to the right. When we
reach a smaller item or the end of the sublist, the current item can be inserted.
Figure shows the fifth pass in detail. At this point in the algorithm, a sorted sublist
of five items consisting of 17, 26, 54, 77, and 93 exists. We want to insert 31 back
 133

into the already sorted items. The first comparison against 93 causes 93 to be
shifted to the right. 77 and 54 are also shifted. When the item 26 is encountered,
the shifting process stops and 31 is placed in the open position. Now we have a
sorted sublist of six items.

The implementation of insertionSort (ActiveCode 1) shows that there are

again n−1n−1 passes to sort nitems. The iteration  starts at position 1 and moves
through position n−1n−1, as these are the items that need to be inserted back into
the sorted sublists. Line 8 performs the shift operation that moves a value up one
position in the list, making room behind it for the insertion. Remember that this is
not a complete exchange as was performed in the previous algorithms.
The maximum number of comparisons for an insertion sort is the sum of the
first n−1n−1 integers. Again, this is O(n2)O(n2). However, in the best case, only
one comparison needs to be done on each pass. This would be the case for an
already sorted list.
One note about shifting versus exchanging is also important. In general, a shift
operation requires approximately a third of the processing work of an exchange
since only one assignment is performed. In benchmark studies, insertion sort will
show very good performance.

Source code:
def insertionSort(alist):
for index in range(1,len(alist)):
 134

currentvalue = alist[index]
position = index
while position>0 and alist[position-1]>currentvalue:
alist[position]=alist[position-1]
position = position-1
alist[position]=currentvalue
alist = [54,26,93,17,77,31,44,55,20]
insertionSort(alist)
print(alist)

Output:

[17, 20, 26, 31, 44, 54, 55, 77, 93]

4.4.3 The Merge Sort

We now turn our attention to using a divide and conquer strategy as a way to
improve the performance of sorting algorithms. The first algorithm we will study is
the merge sort. Merge sort is a recursive algorithm that continually splits a list in
half. If the list is empty or has one item, it is sorted by definition (the base case). If
the list has more than one item, we split the list and recursively invoke a merge sort
on both halves. Once the two halves are sorted, the fundamental operation, called
a merge, is performed. Merging is the process of taking two smaller sorted lists
and combining them together into a single, sorted, new list. .
 135

Source code:
def
mergeSort(alist):
print("Splitting ",alist)
if len(alist)>1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
 136

i=0
j=0
k=0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:
alist[k]=righthalf[j]
j=j+1
k=k+1
while i < len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1

while j < len(righthalf):

alist[k]=righthalf[j]
j=j+1
k=k+1
print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

Output:

Splitting [54, 26, 93, 17, 77, 31, 44, 55, 20]
Splitting [54, 26, 93, 17]
 137

Splitting [54, 26]

Splitting [54]
Merging [54]
Splitting [26]
Merging [26]
Merging [26, 54]
Splitting [93, 17]
Splitting [93]
Merging [93]
Splitting [17]
Merging [17]
Merging [17, 93]
Merging [17, 26, 54, 93]
Splitting [77, 31, 44, 55, 20]
Splitting [77, 31]
Splitting [77]
Merging [77]
Splitting [31]
Merging [31]
Merging [31, 77]
Splitting [44, 55, 20]
Splitting [44]
Merging [44]
Splitting [55, 20]
Splitting [55]
Merging [55]
Splitting [20]
Merging [20]
Merging [20, 55]
Merging [20, 44, 55]
Merging [20, 31, 44, 55, 77]
Merging [17, 20, 26, 31, 44, 54, 55, 77, 93]
[17, 20, 26, 31, 44, 54, 55, 77, 93]

4.4.4 The Quick Sort

 138

The quick sort uses divide and conquer to gain the same advantages as the
merge sort, while not using additional storage. As a trade-off, however, it is
possible that the list may not be divided in half. When this happens, we will see
that performance is diminished.
A quick sort first selects a value, which is called the pivot value. Although
there are many different ways to choose the pivot value, we will simply use the
first item in the list. The role of the pivot value is to assist with splitting the list.
The actual position where the pivot value belongs in the final sorted list,
commonly called the split point, will be used to divide the list for subsequent calls
to the quick sort.
That 54 will serve as our first pivot value. Since we have looked at this
example a few times already, we know that 54 will eventually end up in the
position currently holding 31. The partition process will happen next. It will find
the split point and  at the same time move other items to the appropriate side of the
list, either less than or greater than the pivot value.

Partitioning begins by locating two position markers—let’s call

them leftmark and rightmark—at the beginning and end of the remaining items in
the list (positions 1 and 8 in Figure 13). The goal of the partition process is to
move items that are on the wrong side with respect to the pivot value while also
converging on the split point.  we locate the position of 54.
 139

We begin by incrementing leftmark until we locate a value that is greater

than the pivot value. We then decrement rightmark until we find a value that is less
than the pivot value. At this point we have discovered two items that are out of
place with respect to the eventual split point. For our example, this occurs at 93
and 20. Now we can exchange these two items and then repeat the process again.
At the point where rightmark becomes less than leftmark, we stop. The
position of rightmark is now the split point. The pivot value can be exchanged with
 140

the contents of the split point and the pivot value is now in place (Figure 14). In
addition, all the items to the left of the split point are less than the pivot value, and
all the items to the right of the split point are greater than the pivot value. The list
can now be divided at the split point and the quick sort can be invoked recursively
on the two halves.

The quickSort function shown in ActiveCode 1 invokes a recursive

function, quickSortHelper. quickSortHelper begins with the same base case as the
merge sort. If the length of the list is less than or equal to one, it is already sorted.
If it is greater, then it can be partitioned and recursively sorted.
The partition function implements the process described earlier.

Source code:
def quickSort(alist):
quickSortHelper(alist,0,len(alist)-1)
def quickSortHelper(alist,first,last):
if first<last:
splitpoint = partition(alist,first,last)
quickSortHelper(alist,first,splitpoint-1)
quickSortHelper(alist,splitpoint+1,last)
def partition(alist,first,last):
pivotvalue = alist[first]
leftmark = first+1
rightmark = last
 141

done = False
while not done:
while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1

while alist[rightmark] >= pivotvalue and rightmark >= leftmark:

rightmark = rightmark -1
if rightmark < leftmark:
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp
temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp
return rightmark
alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)

Output:

[17, 20, 26, 31, 44, 54, 55, 77, 93]