Sorting algorithms : Insertion sort and Merge sort,

Insertion sort is the sorting algorithm in which each element is compared with the element adjacent to it and is swapped if the elemt is bigger than it. Again the next element is compared with previous two elements and is position right or left as per the value of those elements. So in a way it maintains a sublist of sorted elements and any new element is pushed according to its value in this sublist. Here is a code for sorting a linked list with insertion sort algorithm.

def insert_sort(a):
    if len(a)== 0:
        print "Please give valid input"
    for i in range(1, len(a)):
        current = 0
        while current < i:
            if a[i] < a[current]:
                a[current], a[i]= a[i] , a[current]
                
            current = current + 1
    return a
  
print insert_sort([12,54,66,43,11,33,34,33,1,45])

will give the output:

[1, 11, 12, 33, 33, 34, 43, 45, 54, 66]

Merge Sort is a sorting algorithm based on divide and conquer technique. With worst-case time complexiy being O(n log n ). Merge sort first divides the array into equal halves and then combines them in a sorted manner.
Here is the code for merge sort.

def merge_sort(list_sort):
	"""splits the list in two parts until each part is left with one member"""
	if len(list_sort) == 1:
	return list_sort
	if len(list_sort)>= 2:
	x= len(list_sort) / 2
	part_a = list_sort[:x]
	part_b = list_sort[x:]
	sorted_part_a = merge_sort(part_a)
	sorted_part_b = merge_sort(part_b)
	return merge(sorted_part_a, sorted_part_b)
	def merge(left , right):
	"""merges the two parts of list after sorting them"""
	sorted_list = []
	i = 0
	while left[:] and right[:] :
	if left [i] > right [i]:
	sorted_list.append(right[i])
	right.remove(right[i])
	else :
	sorted_list.append(left[i])
	left.remove(left[i])
	if left[:]:
	sorted_list.extend(left[:])
	elif right[:] :
	sorted_list.extend(right[:])
	return sorted_list
	details = [1,127,56,2,1,5,7,9,11,65,12,24,76,87,123,65,8,32,86,123,67,1,67,92,72,39,49,12 ,98,52,45,19,37,22,1,66,943,415,21,785,12,698,26,36,18,97,0,63,25,85,24,94,150]
	print "List to be sorted = ", details
	print "Sorted List = ", merge_sort(details)

Mutable Objects : Lists

A list is an ordered sequence of values, where each value is identified by an index. The first index is zero and next is one and further in sequential order. The syntax for expressing literals of type list is [].  The empty list is written as [], and singleton lists are written without comma before the closing bracket like [4].
Difference between tuples and lists:

• Lists are defined using square brackets
• For singleton lists , is not used
• The most important property is lists are mutable whereas tuples and strings are immutable. Objects of mutables type can be modified after they are created.

Basic Operations:
Some basic operations done on the following 2 list are described below:

L1 = [1, 2,3,4 ]
L2 = [5, 6, 7, 8]
Concatenation
print L1 + L2 will give the print:
[1, 2, 3, 4, 5, 6, 7, 8]

Repetition
print L1 * 2 will give the print:
[1, 2, 3, 4, 1, 2, 3, 4]

Find length
print  len(L1) will give the length of list L1:

4

Iteration 
for n in L1: print n
1 2 3 4

Indexing
Any particular element can be reached through indexing
print L1[2]:
will print 3rd element of List L1 as indexing always starts from zero.


Slicing
print L1[1:3]
will slice oth element and print 1st , 2nd element and then again slice.
So output will be
[1, 2 ]


Methods associated with lists:
list.append(a) :  adds object a to the end of list
list.sort()         :  sorts the elements of list in ascending order
list.extend(L1):  adds the items in list L1 to end of list
list.count(e)     :  returns the number of times e occurs in list
list.index(e)     :  returns the index of the first occurrence of e in list.
list.insert(i, e) :  inserts object e at index i
list.pop(i)        :  removes and returns the item at index i in L

List comprehension

This mechanism provides a concise way to apply an operation to the values in a sequence. It creates a new list in which each element is the result o applying a given operation to a value from a sequence(e.g. the elements in another list)
For example,
L =[x**2 for x in range(1,7)]
print L
will print the list :
[1, 4, 6, 9, 16, 25, 36]
The for clause in a list comprehension can be followed by one or more if and for statements that are applied to the values produced by the for clause. These additional clauses modify the sequence of values generated by the first for clause and produce a new sequence of values, to which the operation associated with the comprehension is applied.
For example,
mixed = [1, 2, 'a' , 3, 4.0]
print [x**2 for x in mixed if type(x) == int]
which will give the output
[1, 4, 9]

Scalar Objects

Objects are the core things that Python programs manipulate. every object has a type that defines the kind of things that programs can do with objects of that type. Types can be either scalar i.e indivisible types  or non-scalar i.e divisible types. Scalar objects can be thought of like atoms of the language.

Python has four types of scalar objects:
1. int : it is used to represent integers
2. float : Literals of type float always include a decimal point
3. bool : it is used to represent the Boolean values True and False.
4. None : it is a type with single value .

Operators on type int and float :

•  i+j  :  is the sum of i and j. If both are int than the result is also int else the result is float
• i-j    :  is i minus j. If both are int than the result is int else the result is float. 
• i*j   :  is the product of i and j. It gives an int output if both i and j are int else the output is float. 
• i//j  :   is integer division means the answer is always the quotient and remainder is ignored.
• i/j   :   is normal division where the result is int if both are integers else the result is float.
• i%j:   is the remainder when the int i is divided by int j.
• i**j: is i raised to power of j. If i and j are both of type int, the result is an int. if either of them is a float, the result is a float.
• The comparison operators are ==(equal), != (not equal), > (greater), >- (at least), < (less) and <=  (at most). 

Example :

Question: Create a simple function that given 3 inputs - number 1, number 2 and operator calculates the result. def calculate(x , y , op): if op == '+' : z = x + y elif op == '-' : z = x - y elif op == '*' : z = x * y elif op == '//' : if y!=0: z = x // y else: raise ZeroDivisionError return z print calculate(9 , 9 , '+') print calculate(9 , 9 , '-') print calculate(9 , 9 , '*') print calculate(9 , 9 , '//') print calculate(11 , 0 , '//') OUTPUT WILL BE : 18 0 81 1 ZeroDivisionError

 

Operators on type bool are : 

• a and b is True if both a and b are True and False otherwise
• a or b is True if atleast one of a or b is true and False otherwise
• not a is True if a is False and False is a is True.

Non Mutable Objects : String and Tuples

The scalar types objects are the one without accessible internal structure like int and float. The non-scalar objects are called structured types as one can use indexing to extract individual characters from it an also slice it into sub string. There are basically 4 structured type objects :

string      
tuples     
list
dict

The literals of type string and tuples are classified as non-mutable type objects as the objects once created cannot be modified while literals of type list and dict are called mutable types. Here we will discuss how to define these immutable type objects and some basic functions related to them.

Strings
Objects of type str are used to represent string of characters using single or double quotes. e.g. 'xyz' or "xyz". When defined within inverted commans liters of numeric type also become string. So '1234' is a string.
Operations on string :
Concatenation: adding two strings
>>>a1= '1234'
>>>a2='123'
>>>print a1+a2
will give output:
>>>1234123
Indedxing : accessing particular element of string
>>>a1[1]
will give output:
>>>2
Slicing : breaking strings in parts
>>>a1[1:3]
will give output:
>>>234

Tuples
Like strings, tuples are ordered sequences of elements except that the elements need not be characters. The individual elements can be of any type and need not be of the same type as each other. Tuples are defined with comma-seperated values within parentheses.
For e.g

t1 = (1,4)
t2 = (1,'')

While writing a singleton tuple also the comma is denoted after value like this (1,).

Operations on Tuples : 

Concatenation : adding two tuples
>>>t1 = (1, 4)
>>>t2 = (1, 'two', 3)
>>> print (t1+t2)
will give the output:
>>>(1, 4, 1, 'two', 3)


Slicing : slicing a tuple in two parts
>>> print (t1+t2)[0:2]
will give the output:
>>>(1, 4, )

Indexing : reaching any particular element
 >>>print (t1+t2)[3]
will give the output:
>>>('two')

Abstract Data types : Stack & Queue

A stack is abasic data structure whose physical representation can be compared to stack or pile of books or files which can be accessed only from the top. If we want to add a a file that will be to the top of stack and if we want to remove a file that will also be from the top.The insertion operation is called ' push' and to remove a file we say 'pop'. This basic implementation is called LIFO(Last In First Out) to demonstrate the way it accesses data.

There  are five basic types of operations that can be performed on stacks

1. stack()   creates an empty stack
2. push()    item. inserting an item to the top of stack (push)
3. pop()      removes the item from top of stack
4. peek()    returns the top item from the stack without removing it.
5. size()    returns the number of items in stack.

.

Here's the code depicting implementation  of stack:

class Stack():
	def __init__(self):
	self.item = []
	def size(self):
	return len(self.item)
	def top(self):
	if len(self.item) >= 1:
	print self.item[len(self.item) -1]
	else :
	print "Empty list"
	def pop(self):
	if len(self.item) >= 1:
	self.item.pop()
	else:
	raise IndexError
	def push(self,item):
	self.item.append(item)
	print self.item

.............

Queue

A queue is a data structure similar to stack whose physical representation is similar to that of queue or a group of people standing in a line to collect tickets from movie theatre. Any person would join the queue at last (enqueue) and the person in front would collect the ticket and move out (dequeue) .  This basic implementation is called FIFO(First In FIrst Out)to demonstrate the way it accesses data.

There  operations that are performed using queue can be:

1. queue()   creates an empty stack

2. add()     inserting an item to the last of queue 

3. top()    returns the top item from queue without removing it.

4. size()    returns the number of items in queue. 

Example Code:

class Queue:
	def __init__(self):
	"""initialise a Queue class"""
	self.items = []
	def top(self):
	"""returns the current element at front of queue"""
	if self.items:
	return self.items[0]
	else:
	raise Exception("Empty Queue")
	def pop(self):
	"""takes out an element from front of queue"""
	if self.items:
	self.items.pop(0)
	else :
	raise Exception("Empty Queue")
	def add(self , item):
	"""adds a new element at the end of queue"""
	self.items.append(item)