Algorithms

Doubly linked list


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):
        self.head = self.tail = None

    def addFirstNode(self, newNode):
        ''' A function to add the first node to the list '''

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

    def addNodeTail(self, data):
        ''' Function to add an element to the tail of the list '''

        newNode = ListNode(data)
        
        # Empty list
        if self.head == None:
            self.addFirstNode(newNode)

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

        self.tail.next = None

    def addNodeHead(self, data):
        ''' Function to add an element to the head of the list '''

        newNode = ListNode(data)
        
        # Empty list
        if self.head == None:
            self.addFirstNode(newNode)

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

    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
        if self.head == None:
            print "List is empty"
            return

        # Single node list
        elif self.head == self.tail:
            self.delFirstNode()
            return

        # Multiple node list
        else:
            self.tail = node.previous
            self.tail.next = None
            
    def delNodeHead(self):
        ''' Function to delete a node from head '''
         
        node = self.head

        # Empty list
        if self.head == None:
            print "List is empty"
            return

        # Single node list
        if self.head == self.tail:
            self.delFirstNode()
            return

        # Multi-node list
        if self.head != self.tail:
            node = node.next
            node.previous = None
            self.head = node
     
    def delNode(self, element):
        ''' Function to delete a user specified node '''

        node = self.head
        found = False

        # Single node and element is present
        if self.head == self.tail and self.head.data != element:
            print "Element not found in the list"
            return

        # Head contains element
        if self.head.data == element:
            self.delNodeHead()

        # 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()
         
        # If the element was not found 
        else:
             print "Element was not found in the list"



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

    print "\n+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+"
    node = list.head
    if list.head == None:
        print "Head -> None  ",
        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 "+-+-+-+-+-+-+-+-+-Doubly Linked list+-+-+-+-+-+-+-+-+-+"
        print "+ 1. Add a node to the tail                           +"
        print "+ 2. Add a node to the head                           +"
        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: '))
            list.addNodeTail(inp)
            display(list)

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

        elif s==3:   
            list.delNodeTail()
            display(list)
            
        elif s==4:
            list.delNodeHead()
            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"

Singly linked list


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):
        self.head = self.tail = None

    def addFirstNode(self, newNode):
        ''' A function to add the first node to the list'''

        self.head = self.tail = newNode

    def addNodeTail(self,  data):
        ''' Function to add an element to the tail of the list '''

        newNode = ListNode(data)

        # Empty list
        if self.head == None:
            self.addFirstNode(newNode)
    
        # Non-empty list
        else:
            self.tail.next = newNode
            self.tail = newNode

        self.tail.next = None

    def addNodeHead(self, data): 
        '''Function to add an element to the head of the list '''

        newNode = ListNode(data)
        
        # Empty list
        if self.head == None:
            self.addFirstNode(newNode)
        
        # Non-empty list
        else:
            temp = self.head
            self.head = newNode
            self.head.next = temp
    

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

        self.head = self.tail = None

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

        node = self.head

        # Empty list
        if self.head == None:
            print "List is empty"
            return 

        # Single node list
        elif self.head == self.tail:
            self.delFirstNode()
            return 

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

    def delNodeHead(self):
        ''' Function to delete a node from head '''

        node = self.head

        # Empty list
        if self.head == None:
            print "List is empty"
            return

        # Single node list
        if self.head == self.tail:
            self.delFirstNode()
            return    
        
        # Multi-node list
        if self.head != self.tail:
            node = node.next
            self.head = node
            return


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

        node = self.head
        found = False
    
        # If there's only one node and it doesn't contain the given element
        if self.head == self.tail and self.head.data != element:
            print "Element not found in the list"
            return
        
        # If the head node contains the element
        if self.head.data == element:
            self.delNodeHead()
            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()

        # If the element was not found in the list
        else:
            print "Element not found in the list"
      
def display(list):
    ''' Function to display the linked list '''

    print "\n+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+"
    node = list.head
    if list.head == None:
        print "List is empty! Fill something in the list in-order to delete"
        print "Head -> None  ",
        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 "+-+-+-+-+-+-+-+-+-Singly Linked list+-+-+-+-+-+-+-+-+-+"
        print "+ 1. Add a node to the tail                           +"
        print "+ 2. Add a node to the head                           +"
        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: '))
            list.addNodeTail(inp)
            display(list)

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

        elif s==3:   
            list.delNodeTail()
            display(list)
            
        elif s==4:
            list.delNodeHead()
            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
    return top

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:

[87, 5, 4, 3, 2, 1]
[7, 85, 4, 3, 2, 1]
[7, 5, 84, 3, 2, 1]
[7, 5, 4, 83, 2, 1]
[7, 5, 4, 38, 2, 1]
[7, 5, 4, 3, 2, 81]
[75, 4, 3, 2, 1] [8]
[5, 74, 3, 2, 1] [8]
[5, 4, 73, 2, 1] [8]
[5, 4, 3, 72, 1] [8]
[5, 4, 3, 2, 71[8]
[54, 3, 2, 1] [7][8]
[4, 53, 2, 1] [7][8]
[4, 3, 52, 1] [7][8]
[4, 3, 2, 51[7][8]
[43, 2, 1] [5][7][8]
[3, 42, 1] [5][7][8]
[3, 2, 41[5][7][8]
[32, 1] [4][5][7][8]
[2, 3, 1] [4][5][7][8]
[21] [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)