LinkedListInsertionSort.py

import random
import time

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


class LinkedList:
    def __init__(self):
        self.head = None

    def getHead(self):
        return self.head

    # add item to linked list
    def add(self, item):
        newNode = Node(item)
        newNode.next = self.head
        self.head = newNode

    # display the linked list
    def display(self):
        elements = []
        currentNode = self.head

        while currentNode != None:
            elements.append(currentNode.data)
            currentNode = currentNode.next

        print(elements)

    # add node to sorted linked list
    def addToSorted(self, node):
        previousNode = None
        currentNode = self.head

        while currentNode != None:
            if currentNode.data > node.data:
                break
            else:
                previousNode = currentNode
                currentNode = currentNode.next

        if previousNode == None:
            node.next = currentNode
            self.head = node
        else:
            previousNode.next = node
            node.next = currentNode

    # linked list insertion sort algorith
    # simply it compares the Insertion Pointer data to the next node data
    # if the insertion pointer data is bigger than the next data like: 3 -> 9 -> 4 -> Nonde;
    # here 9 is biger than 4 we simply make the insertion pointer next = the next of the insertion pointer next
    # as 3 -> 9 -> None then we re insert the node with data 4 to the linked list using add to sorted function
    def sort(self):
        start = time.time()
        insertionPointer = self.head
        while insertionPointer.next != None:
            if insertionPointer.data > insertionPointer.next.data:
                tempNode = insertionPointer.next
                insertionPointer.next = insertionPointer.next.next
                self.addToSorted(tempNode)
            else:
                insertionPointer = insertionPointer.next
        
        end = time.time()
        print(end - start)
                
# array insertion sort algorithm
def insertionSort(list):
    start = time.time()
    for index in range(1, len(list)):
        value = list[index] # = 1
        i = index - 1
        while i >= 0:
            if value < list[i]:
                list[i + 1] = list[i]
                list[i] = value
                i -= 1
            else:
                break
    end = time.time()
    print(end - start)

myList = LinkedList()
myArray = []

# Create random ints and adding them to the array and the linked list
for x in range(1, 1000):
    myInt = random.randint(0, 23)
    myList.add(myInt)
    myArray.append(myInt)


myList.sort() #calling insertion sort on the linked list
insertionSort(myArray) # calling insertion sort on the array