# Algorithms

In a doubly linked list, each node contains, besides the next-node link, a second link field pointing to the previous node in the sequence. The two links may be called next or previous.

Example

Head -> 12 <-> 15 <-> 6 <-> 11 <- Tail

Code

# /usr/bin/python
# An implementation of doubly linked list

class ListNode:
def __init__(self, data):
self.data = data
self.next = self.previous = None

class List:
def __init__(self):

''' A function to add the first node to the list '''

''' Function to add an element to the tail of the list '''

newNode = ListNode(data)

# Empty list

# Non-empty list
else:
self.tail.next = newNode
newNode.previous = self.tail
self.tail = newNode

self.tail.next = None

''' Function to add an element to the head of the list '''

newNode = ListNode(data)

# Empty list

# Non-empty list
else:

def delFirstNode(self):
''' Funtion to delete the single node '''

self.previous = self.next = self.head = self.tail = None

def delNodeTail(self):
''' Function to delete an element from the list '''

node = self.tail

# Empty list
print "List is empty"
return

# Single node list
self.delFirstNode()
return

# Multiple node list
else:
self.tail = node.previous
self.tail.next = None

''' Function to delete a node from head '''

# Empty list
print "List is empty"
return

# Single node list
self.delFirstNode()
return

# Multi-node list
node = node.next
node.previous = None

def delNode(self, element):
''' Function to delete a user specified node '''

found = False

# Single node and element is present
return

# Checks for the element in the list
while node.next != None:
if node.next.data == element:
found = True
break
else:
node = node.next

# If element was found
if found:
if node.next.next != None:
temp = node.next
node.next = temp.next
node = temp.next.previous

else:
self.delNodeTail()

else:

def display(list):
''' Function to display the linked list '''

print "\n+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+"
while node is not None:
print " %d " % (node.data),
node = node.next
if node is not None:
print "",
print " <- Tail",
print "\n+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n"

if __name__ == "__main__":
''' Main function '''

list = List()
while True:
print "+ 1. Add a node to the tail                           +"
print "+ 3. Remove a node from tail                          +"
print "+ 4. Remove a node from head                          +"
print "+ 5. Remove a node                                    +"
print "+ 6. Exit                                             +"
print "+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+"
s = int(raw_input('Enter your Choice: '))
if s==1:
inp = int(raw_input('Enter the element you want to insert to the tail: '))
display(list)

elif s==2:
inp = int(raw_input('Enter the element you want to insert to the head: '))
display(list)

elif s==3:
list.delNodeTail()
display(list)

elif s==4:
display(list)

elif s==5:
inp = int(raw_input('Enter the element you want to delete from the list: '))
list.delNode(inp)
display(list)

elif s==6:
break;

else:
print "Invalid input"

A linked list is a group of nodes which together represents a sequence. In this blog, I am trying to explain about singly linked list.

Singly linked lists contain nodes which have a data field as well as a next field, which points to the next node in the linked list.

Example

1 -> 5 -> 2 -> 9 -> None

Code

# /usr/bin/python
# An implementation of linked list

class ListNode:
def __init__(self, data):
self.data = data
self.next = None

class List:
def __init__(self):

''' A function to add the first node to the list'''

''' Function to add an element to the tail of the list '''

newNode = ListNode(data)

# Empty list

# Non-empty list
else:
self.tail.next = newNode
self.tail = newNode

self.tail.next = None

'''Function to add an element to the head of the list '''

newNode = ListNode(data)

# Empty list

# Non-empty list
else:

def delFirstNode(self):
''' Function to delete the single node '''

def delNodeTail(self):
''' Function to delete an element from the list '''

# Empty list
print "List is empty"
return

# Single node list
self.delFirstNode()
return

# Multiple node list
else:
while node.next.next != None:
node = node.next
node.next = None
self.tail = node

''' Function to delete a node from head '''

# Empty list
print "List is empty"
return

# Single node list
self.delFirstNode()
return

# Multi-node list
node = node.next
return

def delNode(self, element):
''' Function to delete a user specified given node '''

found = False

# If there's only one node and it doesn't contain the given element
return

# If the head node contains the element
return

# To check if the node is in the rest of the list
while node.next != None:
if node.next.data == element:
found = True
break

else:
node = node.next

# If node was found
if found:
if node.next.next != None:
node.next = node.next.next

else:
self.delNodeTail()

else:

def display(list):
''' Function to display the linked list '''

print "\n+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+"
print "List is empty! Fill something in the list in-order to delete"
while node is not None:
print " %d " % (node.data),
node = node.next
if node is not None:
print "->",
print " <- Tail",
print "\n+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n"

if __name__ == "__main__":
''' Main function '''

list = List()
while True:
print "+ 1. Add a node to the tail                           +"
print "+ 3. Remove a node from tail                          +"
print "+ 4. Remove a node from head                          +"
print "+ 5. Remove a node                                    +"
print "+ 6. Exit                                             +"
print "+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+"
s = int(raw_input('Enter your Choice: '))
if s == 1:
inp = int(raw_input('Enter the element you want to insert to the tail: '))
display(list)

elif s==2:
inp = int(raw_input('Enter the element you want to insert to the head: '))
display(list)

elif s==3:
list.delNodeTail()
display(list)

elif s==4:
display(list)

elif s==5:
inp = int(raw_input('Enter the element you want to delete from the list: '))
list.delNode(inp)
display(list)

elif s==6:
break;

else:
print "Invalid input"

# Quick sort

In this post, I will be explaining about the people’s favorite sorting algorithm – Quick sort

Quick sort can be done in two ways.

• Divide and conquer: Algorithms that solve (conquer) problems by dividing them into smaller sub-problems until the problem is so small that it is trivially solved.
• In-place: In place sorting algorithms don’t require additional temporary space to store elements as they sort; they use the space originally occupied by the elements.

The steps are:

• Pick an element, called a pivot, from the list.
• Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
• Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.
The base case of the recursion are lists of size zero or one, which never need to be sorted.

## Example: In-place algorithm

### Code

# /usr/bin/python
# A program to do quick sort using separate list

def quick_sort(inp):
''' Quick sort function '''
lesser = []
greater = []

if len(inp) <= 1:
return inp

for i in inp[1:]:
# 0th element in the list is always the pivot element
if i < inp[0]:
lesser.append(i)
else:
greater.append(i)
return quick_sort(lesser) + inp[0:1] + quick_sort(greater)

if __name__ =="__main__":
'''Main function'''

inp =[]
s = int(raw_input('How many elements would you like to enter: '))
for x in range(s):
inp.append(int(raw_input('Enter element #' + x+1 + ': ')))
quick_sort(inp)

Input list:

9 8 3 7 5
[9, 8, 3, 7, 5]
[8, 3, 7, 5] [9]
[3, 7, 5] [8] [9]
[3] [7, 5] [8] [9]
[3] [5] [7] [8] [9]

Output list:

3  5  7  8  9

## Example: Divide and conquer

### Code

# /usr/bin/python
# A program to do quick sort using inplace algo

def partition(inp, start, end):
''' A function which does partition '''

pivot = inp[end]
bottom = start - 1
top = end

done = 0
while not done:
while not done:
bottom = bottom + 1
if bottom == top:
done = 1
break
if inp[bottom] > pivot:
inp[top] = inp[bottom]
break

while not done:
top = top - 1
if top == bottom:
done = 1
break
if inp[top] < pivot:
inp[bottom] = inp[top]
break
inp[top] = pivot

def quick_sort(inp, start, end):
''' Quick sort function '''
if start < end:
split = partition (inp, start, end)
quick_sort(inp, start, split - 1)
quick_sort(inp, split + 1, end)
else:
return

if __name__ == "__main__":
''' Main function '''

inp = []
s = int(raw_input('How many elements would you like to enter: '))
for x in range(s):
inp.append(int(raw_input('Enter element #' + x+1 + ': ')))
start = 0
end = len(inp) - 1
quick_sort(inp, start, end)
import string
print string.join(map(str, inp))

Input list:

 9 8 3 7 5
[9, 8, 3, 7, 5]  Pivot = 9
[5, 8, 3, 7, [9] Pivot = 5
[3, 8, 5, 7] [9] Pivot = 5
[3] [5] [8, 7] [9] Pivot = 3
[3] [5] [8, 7] [9] Pivot = 8
[3] [5] [7] [8] [9] Pivot = 7 

Sorted list:

3 5 7 8 9

The partition routine examines every item in the array at most once, so it is clearly O(n)
Usually, the partition routine will divide the problem into two roughly equal sized partitions. We know that we can divide n items in half logn times. This makes quicksort a O(nlogn) algorithm.
In worst case, i.e when the list is already sorted, it becomes O(n^2)

# Bubble sort

In this tutorial I will be explaining about the worst sorting algorithm mentioned by the great computer scientists in the world during the ACM AM Turing centenary ceremony celebration.

Bubble sort works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. It only uses comparisons to operate on elements, it is a comparison sort.

Lets see an example here:

Input list:

[8, 7, 5, 4, 3, 2, 1]

While sorting:

[8, 7, 5, 4, 3, 2, 1]
[7, 8, 5, 4, 3, 2, 1]
[7, 5, 8, 4, 3, 2, 1]
[7, 5, 4, 8, 3, 2, 1]
[7, 5, 4, 3, 8, 2, 1]
[7, 5, 4, 3, 2, 8, 1]
[7, 5, 4, 3, 2, 1] [8]
[5, 7, 4, 3, 2, 1] [8]
[5, 4, 7, 3, 2, 1] [8]
[5, 4, 3, 7, 2, 1] [8]
[5, 4, 3, 2, 7, 1] [8]
[5, 4, 3, 2, 1] [7][8]
[4, 5, 3, 2, 1] [7][8]
[4, 3, 5, 2, 1] [7][8]
[4, 3, 2, 5, 1] [7][8]
[4, 3, 2, 1] [5][7][8]
[3, 4, 2, 1] [5][7][8]
[3, 2, 4, 1] [5][7][8]
[3, 2, 1] [4][5][7][8]
[2, 3, 1] [4][5][7][8]
[2, 1] [3][4][5][7][8]
[1] [2][3][4][5][7][8]

Sorted list:

[1][2][3][4][5][7][8]

Python code:

# /usr/bin/python
# A program to do bubble sort

def bubble_sort(inp_list):
'''Bubble sort function'''
j = len(inp_list)-1   # C * 1
while j != 0:         # C * n
for k in range(j):      # C * (n-1) * (\latex{\sum\limits_{k=0}^j k})
if inp_list[k] > inp_list[k+1]: # C * (n-1) * (\latex{\sum\limits_{k=0}^j k})
temp = inp_list[k]             # C * (n-1) * (\latex{\sum\limits_{k=0}^j k})
inp_list[k] = inp_list[k+1]    # C * (n-1) * (\latex{\sum\limits_{k=0}^j k})
inp_list[k+1] = temp           # C * (n-1) * (\latex{\sum\limits_{k=0}^j k})
j = j - 1    # C * (n-1)
return inp_list  # C * 1

def main():
'''Main function'''
inp =[]
s = int(raw_input('How many elements would you like to enter: '))
for x in range(s):
inp.append(int(raw_input('Enter element #' + x+1 + ': ')))
print "Initial list: ", inp
output_list = bubble_sort(inp)
print "Sorted list: ", output_list

if __name__ == "__main__":
main()

Best case (if the list is already sorted): O(n)
Worst case (if the list is sorted in descending order): C*n*\latex{\sum\limits_{k=0}^n k} = O(n^2)

# Selection sort

In this tutorial I am planning to explain about the selection sort.

The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

Lets look into an example:

input list:

[8, 7, 6, 5, 4, 3, 2, 1]

While sorting:

[8, 7, 6, 5, 4, 3, 2, 1]

[ 1, 7, 6, 5, 4, 3, 2, 8]

[ 1, 2, 6, 5, 4, 3, 7, 8]

[ 1, 2, 3, 5, 4, 6, 7, 8]

[ 1, 2, 3, 4, 5, 6, 7, 8]

[ 1, 2, 3, 4, 5, 6, 7, 8]

[ 1, 2, 3, 4, 5, 6, 7, 8]

[ 1, 2, 3, 4, 5, 6, 7, 8]

Sorted list:

[ 1, 2, 3, 4, 5, 6, 7, 8]

This the corresponding python code:

# /usr/bin/python
# A program to do selection sort

def selection_sort(inp_list):
'''The selection sort function'''

for i in range (len(inp_list)): # C*(n+1), where n is the length of the input list
iMin = i                    # C*n
for j in range(i+1, len(inp_list)): # C*n*\latex{\sum\limits_{j=i+1}^n j}
if inp_list[j] < inp_list[iMin]: # C*n*\latex{\sum\limits_{j=i+1}^n j}
iMin = j                     # C*n*\latex{\sum\limits_{j=i+1}^n j}

if iMin != i:                        # C*n
temp = inp_list[i]               # C*n
inp_list[i] = inp_list[iMin]     # C*n
inp_list[iMin] = temp            # C*n
return inp_list                          # C*1

def main():
'''Main function'''

inp =[]
s = int(raw_input('How many elements would you like to enter: '))
for x in range(s):
inp.append(int(raw_input('Enter element #' + x+1 + ': ')))
print "Input list: ", inp
output_list = selection_sort(inp)
print "Sorted list: ", output_list

if __name__ == "__main__":
main()

Best case (if the list is already sorted): O(n)
Worst case (if the list is sorted in descending order): C*n*\latex{\sum\limits_{j=0}^n j} = O(n^2)

# Insertion sort

I have enrolled for advanced computer algorithm course in winter fall 2013. As a part of required reading, we were asked to understand how the insertion sort works. In the write-up, I will be explaining how does the algorithm works and will provide you a python code of the same.

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Lets see an example:

Input list:

5 6 3 1 8 7 2 4

While processing:

5 6 3 1 8 7 2 4
5 6 3 1 8 7 2 4

3 5 6 1 8 7 2 4

1 3 5 6 8 7 2 4

1 3 5 6 8 7 2 4

1 3 5 6 7 8 2 4

1 2 3 5 6 7 8 4

1 2 3 4 5 6 7 8

So the sorted list looks like this:

1 2 3 4 5 6 7 8
# /usr/bin/python
# A program to do insertion sort

def insertion_sort(inp_list):
'''Insertion sort function'''

for i in range(1, len(inp_list)): # => C*n operations, given n is the no of elements in the list
valueToInsert=inp_list[i]     # => C*(n-1) operations
holePos=i                     # => C*(n-1) operations
'''The current index is cached in-order to look if the valueToInsert is less
than the elements in the sorted list.'''
while holePos > 0 and valueToInsert  C *(n-1)*\latex{\sum\limits_{i=0}^holePos i} operations
''' i time(s) is checked whether the valueToInsert is less than the elements
in the sorted list.'''
inp_list[holePos] = inp_list[holePos - 1]  # => C*(n-1)*\latex{\sum\limits_{i=0}^holePos i} operations
holePos = holePos -1                       # => C*(n-1)*\latex{\sum\limits_{i=0}^holePos i} operations
inp_list[holePos] = valueToInsert              # => C*(n-1) operations
return inp_list

def main():
'''Main function'''

inp =[]
s = int(raw_input('How many elements would you like to enter: '))
for x in range(s):
inp.append(int(raw_input('Enter element #' + x+1 + ': ')))
output_list = insertion_sort(inp)
print "Sorted list: ", output_list

if __name__ == "__main__":
main()

Best case (If the list is already sorted complexity becomes): O(n)
Worst case (If the list is sorted in the descending order): O(C *(n-1)*\latex{\sum\limits_{i=0}^n i}) = O(n^2)