UNIT-IV

LISTS, TUPLES, DICTIONARIES

4.1 Lists

A list is a sequence of values. In a list, the values can be of any type. The values in a list are
called elements or sometimes items. There are several ways to create a new list; the simplest
is to enclose the elements in square brackets ([ and ]):

[10, 20, 30, 40]

['frog', 'worm', 'snake']

The first example is a list of four integers. The second is a list of three strings. The elements
of a list don’t have to be the same type. The following list contains a string, a float, an
integer, and another list:

['bunk', 2.0, 5, [10, 20]]

A list within another list is called nested list. A list that contains no elements is called an
empty list; you can create one with empty brackets, [].

As you might expect, you can assign list values to variables:

>>> namy = ['ram', 'imran', 'joseph']

>>> numby = [17, 123]
>>> empty = []
>>> print (namy, numby, empty)
['ram', 'imran', 'joseph'] [17, 123] []

How to access elements from a list?

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.

>>>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
Nested list are accessed using nested indexing

>>>n_list = ["Happy", [2,0,1,5]]

>>>print(n_list[0][1])
# Output: a
print(n_list[1][3])
# Output: 5
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.1List Operations

Lists respond to the + and * operators much like strings; they mean concatenation and
repetition, except that the result is a new list, not a string.

The + operator concatenates lists:

>>> a = [1, 2, 3]
>>> b = [4, 5, 6]
>>> c = a + b
>>> print (c)

# Output: [1, 2, 3, 4, 5, 6]

Similarly, the * operator repeats a list a given number of times:

>>> [0] * 4
[0, 0, 0, 0]
>>> [1, 2, 3] * 3
# Output: [1, 2, 3, 1, 2, 3, 1, 2, 3]

The first example repeats [0] four times. The second example repeats the list [1, 2, 3] three
times.

4.1.2 List Slices

We can access a range of items in a list by using the slicing operator (colon). So you've got an list,
you want to get specific sets of sub-elements from it, without any loops. Here is an example, just a
normal list with the numbers 1 through 8. Now let's say that we really want the sub-elements 2, 3,
and 4 returned in a new list. How do we do that?

>>> a = [1, 2, 3, 4, 5, 6, 7, 8]
>>> print(a[1:4])

#output: [2, 3, 4]

The 1 means to start at second element in the list (note that the slicing index starts at 0). The 4
means to end at the fifth element in the list, but not include it. The colon in the middle is how
Python's lists recognize that we want to use slicing to get objects in the list.

Few slicing techniques

If you omit the first index, the slice starts at the beginning. If you omit the second, the slice
goes to the end. So if you omit both, the slice is a copy of the whole list.

>>>my_list = ['p','r','o','g','r','a','m','i','z']

# elements beginning to 5th

>>>print(my_list[:5])

#output: ['p', 'r', 'o', 'g',’r’]

# elements 6th to end

>>>print(my_list[5:])

#output: ['a', 'm', 'i', 'z']

# elements beginning to end

>>>print(my_list[:])

#output: ['p', 'r', 'o', 'g', 'r', 'a', 'm', 'i', 'z']

4.1.3 List Methods

Python provides methods that operate on lists. Most of the l ist methods are all void; they modify the
list and return none. Methods that are available with list object in Python programming are
tabulated below.
Method Description
append() Add Single Element to The List
extend() Add Elements of a List to Another List
insert() Inserts Element to The List
remove() Removes Element from the List
index() returns smallest index of element in list
count() returns occurrences of element in a list
pop() Removes Element at Given Index
 reverse() Reverses a List
sort() sorts elements of a list
copy() Returns Shallow Copy of a List
clear() Removes all Items from the List

For example, append adds a new element to the end of a list.

>>> t = ['a', 'b', 'c']

>>> t.append('d')
>>> print (t)
#output: ['a', 'b', 'c', 'd']

extend takes a list as an argument and appends all of the elements. The following example
leaves t2 unmodified, appends t2 elements in t1 list.

>>> t1 = ['a', 'b', 'c']

>>> t2 = ['d', 'e']
>>> t1.extend(t2)
>>> print (t1)
#output: ['a', 'b', 'c', 'd', 'e']

Sort arranges the elements of the list from low to high.

>>> t = ['d', 'c', 'e', 'b', 'a']

>>> t.sort()
>>> print (t)
#output: ['a', 'b', 'c', 'd', 'e']

There are several ways to delete elements from a list. If you know the index of the element
you want, you can use pop. pop modifies the list and returns the element that was removed. If
you don’t provide an index, it deletes and returns the last element.

>>> t = ['a', 'b', 'c']

>>> x = t.pop(1)
>>> print (t)
#output: ['a', 'c']
>>> print (x)
#output: b

If you know the element you want to remove (but not the index), you can use remove. The
return value from remove is None.

>>> t = ['a', 'b', 'c']

>>> t.remove('b')
>>> print (t)
#output: ['a', 'c']
4.1.4 List Loop

The most common way to traverse the elements of a list is with a for loop. The example as
follows

>>> cheeses = ['a', 'b', 'c']

for cheese in cheeses:
print (cheese)
#output: ['a',’b,'c']

The above loop works well if you only need to read the elements of the list. But if you want
to write or update the elements, you need the indices. A common way to do that is to combine
the functions range and len:

>>>numbers=[10,20,30,40]
for i in range(len(numbers)):
numbers[i] = numbers[i] * 2
print (numbers)
#output: [20, 40, 60, 80]

This loop traverses the list and updates each element. len returns the number of elements in
the list. range returns a list of indices from 0 to n-1, where n is the length of the list. Each
time through the loop i get the index of the next element. The assignment statement in the
body uses i to read the old value of the element and to assign the new value. A for loop over
an empty list never executes the body.

>>>for x in []:
print ('This never happens.')

Although a list can contain another list, the nested list still counts as a single element. The
length of this list is four.

>>>xx=['tam', 1, ['fun', 'gun', 'bun'], [1, 2, 3]]

>>>print (len(xx))
#output: 4

4.1.5 List Mutability

Mutable and immutable are English words meaning "can change" and "cannot change"
respectively. Unlike strings, lists are mutable. This means we can change an item in a list by
accessing it directly as part of the assignment statement. Using the indexing operator (square
brackets) on the left side of an assignment, we can update one of the list items.

>>>fruit = ["banana", "apple", "cherry"]

>>>fruit[0] = "pear"
>>>fruit[-1] = "orange"
>>>print(fruit)
#output: ['pear', 'apple', 'orange']
An assignment to an element of a list is called item assignment. Item assignment does not
work for strings. Recall that strings are immutable.

List indices work the same way as string indices:

• Any integer expression can be used as an index.

• If you try to read or write an element that does not exist, you get an IndexError.
• If an index has a negative value, it counts backward from the end of the list.

The in operator also works on lists.

>>> cheeses = ['milk', 'silk', 'click']

>>> 'milk' in cheeses
#output: True
>>> 'freak' in cheeses
#output: False

4.1.6 List Aliasing

Not all variable names refer to different variables. When two identifiers refer to the same
variable (and therefore value), this is known as an alias. An alias identifier to an existing
variable is created using the form <identifier>=<identifier>.For example if a refers to an object and
you assign b = a, then both variables refer to the same object:

>>> a = [1, 2, 3]
>>> b = a
>>> b is a
#output: True

The association of a variable with an object is called a reference. In this example, there are
two references to the same object. An object with more than one reference has more than one
name, so we say that the object is aliased. If the aliased object is mutable, changes made with
one alias affect the other.

4.1.7 Cloning List

If we want to modify a list and also want to keep a copy of the original, we need 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.

The easiest way to clone a list is to use the slice operator. Taking any slice of a creates a new
list. In the following example slice happens to the whole list.

>>>a = [81, 82, 83]
>>>b = a[:]
>>>print(a == b)
#output: True
>>>print(a is b)
#output: False
>>>b[0]=5
>>>print(a)
#output: [81, 82, 83]
>>>print(b)
#output: [5, 82, 83]

Now we are free to make changes to b without worrying about a. Again, we can clearly see in
coding that a and b are entirely different list objects.

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 a list parameter, the caller sees the change. For example, delete_head removes the
first element from a list.

def delete_head(t):
del t[0]

Here’s how it is used.

>>> letters = ['a', 'b', 'c']

>>> delete_head(letters)
>>> print (letters)
#output: ['b', 'c']

The parameter t and the variable letters are aliases for the same object. It is important to
distinguish between operations that modify lists and operations that create new lists. For
example, the append method modifies a list, but the + operator creates a new list.

>>> t1 = [1, 2]

>>> t2 = t1.append(3)

>>> print (t1)

#output: [1, 2, 3]

>>> print (t2)

#output: None

>>> t3 = t1 + [4]

>>> print (t3)

#output: [1, 2, 3, 4]

This difference is important when you write functions that are supposed to modify lists. For
example, this function does not delete the head of a list.
def bad_delete_head(t):
t = t[1:]

The slice operator creates a new list and the assignment makes t refer to it, but none of that
has any effect on the list that was passed as an argument. An alternative is to write a function
that creates and returns a new list. For example, tail returns all but the first element of a list.

def tail(t):
return t[1:]

This function leaves the original list unmodified. Here’s how it is used.

>>> letters = ['a', 'b', 'c']

>>> rest = tail(letters)
>>> print (rest)
#output: ['b', 'c']

4.2 Tuples

A tuple is a sequence of immutable Python objects. Tuples are sequences, just like lists. The
differences between tuples and lists are, the tuples cannot be changed unlike lists and tuples
use parentheses, whereas lists use square brackets.

Creating a tuple is as simple as putting different comma separated values. Optionally you can
put these comma separated values between parentheses also. For example

>>>tup1 = ('physics', 'chemistry', 1997, 2000)

>>>tup2 = (1, 2, 3, 4, 5 )
>>>tup3 = ‘a’, ‘b’, ‘c’, ‘d’

The empty tuple is written as two parentheses containing nothing.

>>>tup1 = ()

To write a tuple containing a single value you have to include a comma, even though there is
only one value.

>>>tup1 = (50,)

Like string indices, tuple indices start at 0, and they can be sliced, concatenated, and so on.

Another way to create a tuple is the built-in function tuple. With no argument, it creates
an empty tuple.

>>> t = tuple()
>>> print (t)
#output: ()

If the argument is a sequence (string, list or tuple), the result is a tuple with the elements of
the sequence:
>>> t = tuple('lupins')
>>> print (t)
#output: ('l', 'u', 'p', 'i', 'n', 's')

Accessing Values in Tuples

To access values in tuple, use the square brackets for slicing along with the index or indices
to obtain value available at that index. For example

>>>tup1 = ('physics', 'chemistry', 1997, 2000)

>>> tup2 = (1, 2, 3, 4, 5, 6, 7 )
>>> print ("tup1[0]: ", tup1[0])
#output: tup1[0]: physics
>>> print ("tup2[1:5]: ", tup2[1:5])
#output: tup2[1:5]: [2, 3, 4, 5]

Updating Tuples

Tuples are immutable which means you cannot update or change the values of tuple
elements. You are able to take portions of existing tuples to create new tuples as the
following example demonstrates.

>>>tup1 = (12, 34.56);

>>>tup2 = ('abc', 'xyz');
# Following action is not valid for tuples
# tup1[0] = 100;
# So let's create a new tuple as follows
>>>tup3 = tup1 + tup2;
>>>print(tup3)

#output:
(12, 34.56, 'abc', 'xyz')

Delete Tuple Elements

Removing individual tuple elements is not possible. There is, of course, nothing wrong with
putting together another tuple with the undesired elements discarded.

To explicitly remove an entire tuple, just use the del statement. For example

>>>tup = ('physics', 'chemistry', 1997, 2000);

>>> print (tup)
>>>del tup;

#output:
('physics', 'chemistry', 1997, 2000)
4.2.1 Tuple Assignment

It is often useful to swap the values of two variables. With conventional assignments, you
have to use a temporary variable. For example, to swap a and b

>>> temp = a
>>> a = b
>>> b = temp

This above solution is usual one but tuple assignment is more elegant and easy

>>> a, b = b, a

The left side is a tuple of variables, the right side is a tuple of expressions. Each value is
assigned to its respective variable. All the expressions on the right side are evaluated before
any of the assignments.

The number of variables on the left and the number of values on the right have to be the
same:

>>> a, b = 1, 2, 3
#output:ValueError: too many values to unpack

More generally, the right side can be any kind of sequence (string, list or tuple). For example,
to split an email address into a user name and a domain, you could write.

>>> addr = 'loky@cahcet.org'

>>> uname, domain = addr.split('@')

The return value from split is a list with two elements; the first element is assigned to uname,
the second to domain.

>>> print (uname)

#output: loky
>>> print (domain)
#output: cahcet.org

4.2.2 Tuple as Return Values

Strictly speaking, a function can only return one value, but if the value is a tuple, the effect is
the same as returning multiple values. For example, if you want to divide two integers and
compute the quotient and remainder, it is inefficient to compute x/y and then x%y. It is better
to compute them both at the same time.

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.

>>> t = divmod(7, 3)
>>> print (t)
#output: (2, 1)

Or use tuple assignment to store the elements separately.

>>> quot, rem = divmod(7, 3)

>>> print (quot)
#output: 2
>>> print (rem)
#output: 1

Here is an example of a function that returns a tuple.

def min_max(t):
return min(t), max(t)

>>>x=(10,20,30,40)

>>>mi,ma=min_max(x)

>>>print ('minimum',mi)
#output: minimum 10

>>>print ('maximum',ma)
#output: maximum 40

max and min are built-in functions that find the largest and smallest elements of a sequence.
min_max computes both and returns a tuple of two values.

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

A dictionary is like a list, but more general. In a list, the indices have to be integers; in a
dictionary they can be (almost) any type. You can think of a dictionary as a mapping between
a set of indices (which are called keys) and a set of values. Each key maps to a value. The
association of a key and a value is called a key-value pair or sometimes an item.

Each key is separated from its value by a colon (:), the items are separated by commas, and
the whole thing is enclosed in curly braces. An empty dictionary without any items is written
with just two curly braces, like this: {}.

Keys are unique within a dictionary while values may not be. The values of a dictionary can
be of any type, but the keys must be of an immutable data type such as strings, numbers, or
tuples.

Accessing Values in Dictionary

To access dictionary elements, you can use the familiar square brackets along with the key to
obtain its value. Following is a simple example

>>>dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}

>>>print ("dict['Name']: ", dict['Name'])
#output: dict['Name']: Zara
>>>print ("dict['Age']: ", dict['Age'])
#output: dict['Age']: 7

Updating Dictionary

You can update a dictionary by adding a new entry or a key-value pair, modifying an existing
entry, or deleting an existing entry as shown below in the simple example

>>>dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}

>>>dict['Age'] = 8; # update existing entry
>>>dict['School'] = "DPS School"; # Add new entry
>>>print "dict['Age']: ", dict['Age']
#output: dict['Age']: 8
>>>print "dict['School']: ", dict['School']
#output: dict['School']: DPS School

Delete Dictionary Elements

You can either remove individual dictionary elements or clear the entire contents of a
dictionary. You can also delete entire dictionary in a single operation.

To explicitly remove an entire dictionary, just use the del statement. Following is a simple
example

>>>dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}

>>>del dict['Name']; # remove entry with key 'Name'

>>>dict.clear(); # remove all entries in dict
>>>del dict ; # delete entire dictionary
4.3.1 Operations on Dictionaries

There are four basic operations which we can perform on dictionaries they are tabulated
below.

Operation Explanation
len(d) returns the number of stored entries, i.e. the number of (key, value) pairs.
del d[k] deletes the key k together with his value
k in d True, if a key k exists in the dictionary d
k not in d True, if a key k doesn't exist in the dictionary d

len(D)

Returns the number of key-value pairs in D.

Example
>>>signals = {0: 'red', 1: 'yellow', 2: 'green'}
>>>print(len(signals))
#output: 3

del D[k]

In Python, del is a statement, not a function. If dictionary D has a key-value pair whose key
equals k, that key-value pair is deleted from D. If there is no matching key-value pair, the
statement will raise a KeyError exception.

Example
>>> rgb = {'red':'#ff0000', 'green':'#00ff00', 'blue':'#0000ff'}
>>> del rgb['red']
>>> rgb
#output: {'blue': '#0000ff', 'green': '#00ff00'}
>>> del rgb['cerise']
#output:
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: 'cerise'

k in D

A predicate that tests whether D has a key equal to k.

Example
>>> roster={1:'Pat', 2:'Ray', 3:'Min'}

>>> 3 in roster

#output: True
>>> 88 in roster
#output: False

k not in D

A predicate that tests whether D does not have a key equal to k.

Example
>>> roster={1:'Pat', 2:'Ray', 3:'Min'}

>>> 3 not in roster

#output: False

>>> 88 not in roster

#output: True

4.3.2 Dictionary Methods

Python has some methods that dictionary objects can call. For example, dict1.clear() method
removes all items from the dictionary dict1.

Method Description
clear() Removes all Items
copy() Returns Shallow Copy of a Dictionary
fromkeys() creates dictionary from given sequence
get() Returns Value of The Key
items() returns view of dictionary's (key, value) pair
keys() Returns View Object of All Keys
popitem() Returns & Removes Element From Dictionary
setdefault( Inserts Key With a Value if Key is not Present
)
pop() removes and returns element having given key
values() returns view of all values in dictionary
update() Updates the Dictionary

How to use dictionary methods? Few Sample examples as follows

D.values()
Returns a list of the values from key-value pairs in dictionary D, in no particular order.
However, if you call both the .items() and .values() methods of a dictionary without changing
that dictionary's contents between those calls, Python guarantees that the ordering of the two
results will be the same.
>>> signals = {0: 'red', 1: 'yellow', 2: 'green'}

>>> signals.values()

#output: ['yellow', 'red', 'green']

>>> signals.keys()
#output: [1, 0, 2]

D.update(D2)

Merge the contents of dictionary D2 into dictionary D. For any key-value pairs that have the
same key in both D and D2, the value for that key in D after this operation will be the value
from D2, not the value from D.

>>> roster={1:'Pat', 2:'Ray', 3:'Min'}

>>> newer={3:'Bev', 4:'Wes'}

>>> roster.update(newer)

>>> roster

#output: {1: 'Pat', 4: 'Wes', 2: 'Ray', 3: 'Bev'}

>>> newer

#output: {3: 'Bev', 4: 'Wes'}

D.popitem()

Returns an arbitrary entry from dictionary D as a (key, value) tuple, and also removes that
entry. If D is empty, raises a KeyError exception.

>>> roster={1:'Pat', 2:'Ray', 3:'Min'}

>>> roster.popitem()

#output: (1, 'Pat')

>>> roster

#output: {2: 'Ray', 3: 'Min'}

D.iterkeys()

Returns an iterator that generates the keys from dictionary D.

>>> roster={1:'Pat', 2:'Ray', 3:'Min'}

>>> nScan = roster.iterkeys()

>>> for n in nScan:

… print (n)

#output: 1 2 3

D.itervalues()
Returns an iterator that generates the values from dictionary D.

>>> roster={1:'Pat', 2:'Ray', 3:'Min'}

>>> nameScan = roster.itervalues()

>>> for name in nameScan:

… print (name)

#output: Pat Ray Min

4.4 List Comprehension

List comprehensions provide a concise way to create lists. Common applications are to make
new lists where each element is the result of some operations applied to each member of
another sequence or iterable, or to create a subsequence of those elements that satisfy a
certain condition.

For example, assume we want to create a list of squares, like:

>>> squares = []
>>> for x in range(10):
... squares.append(x**2)
...
>>> squares
#output: [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

We can obtain the same result with:

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

A list comprehension consists of brackets containing an expression followed by a for clause,

then zero or more for or if clauses. The result will be a new list resulting from evaluating the
expression in the context of the for and if clauses which follow it. For example, this list
comparison combines the elements of two lists if they are not equal:

>>> [(x, y) for x in [1,2,3] for y in [3,1,4] if x != y]

[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

and it’s equivalent to:

>>> combs = []
>>> for x in [1,2,3]:
... for y in [3,1,4]:
... if x != y:
... combs.append((x, y))
...
>>> combs
#output: [(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]
4.5 Illustrative Programs

4.5.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−1 passes to sort n items, since the
final item must be in place after the (n−1)st pass.

The following figure shows the entire sorting process. 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.

Selection Sort 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: [17, 20, 26, 31, 44, 54, 55, 77, 93]

4.5.2 The Insertion Sort

The insertion sort, 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 following figure shows the insertion sorting
process. The shaded items represent the ordered sublists as the algorithm makes each pass.

We begin by assuming that a list with one item (position 0) is already sorted. On each pass,
one for each item 1 through n−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. The below 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 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.

Insertion Sort Code:

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

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.5.3 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.
Figure A shows our familiar example list as it is being split by mergeSort. Figure B shows the
simple lists, now sorted, as they are merged back together.
 Figure A

Figure B

Merge Sort 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)

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: [17, 20, 26, 31, 44, 54, 55, 77, 93]

4.5.4 Histogram

Histograms are relatively simple things to make in python. We will use matplotlib.

>>> import matplotlib.pyplot as plt

The function we will use is plt.hist, which has the following syntax

>>> n,bins,patches = plt.hist(intputarray, bins=100)

This will not only plot the histogram for you, but it will return the number of elements in
each bin (n) and the bins themselves (bins). You can name the three variables holding the
output anything you want, but you need three. Dont worry about what the “patches” are.

Keywords for the hist() function

 bins: number of bins you want to have. Can also be a list of bin edges.
 range: lower and upper range of the bins
 normed: “= True” means you get a probability distribution instead of just raw number
counts
 histtype: ʻbarʼ= traditional stype, ʻstepʼ= a line plot. looks better usually
 Weights: this is an array of values that must have the same size as the number of bins
you have. This will be a factor by which you will multiply the number count of each
bin. In other words, it will make the “number of elements” output be n*weights
instead. This is a good way to normalize your histogram outside of just using the
normed variable.

For example, if you wanted to plot the fraction of objects in each bin, you would set weights
equal to an N sized array (N = number of bins you have) where each element of the array is
equal to 1/(total # of objects).

Sample Histogram Code:

import numpy as np
import matplotlib.mlab as mlab
import matplotlib.pyplot as plt

mu, sigma = 100, 15

x = mu + sigma*np.random.randn(10000)

# the histogram of the data

n, bins, patches = plt.hist(x, 50, normed=1, facecolor='green', alpha=0.75)

# add a 'best fit' line

y = mlab.normpdf( bins, mu, sigma)
l = plt.plot(bins, y, 'r--', linewidth=1)

plt.xlabel('Smarts')
plt.ylabel('Probability')
plt.title(r'$\mathrm{Histogram\ of\ IQ:}\ \mu=100,\ \sigma=15$')
plt.axis([40, 160, 0, 0.03])
plt.grid(True)

plt.show()

#Output: