gistfile1.txt

import random
 
class Node:
    def __init__(self, key):
        self.key = key
        self.vertical = None
 
def insertItemBetween(first, current, last):
    first.vertical = current
    current.vertical = last
 
def addItemToList(nodes, val, index):
    node = Node(val)
    current = nodes[index]
    while not current.vertical == None:
        if val < current.vertical.key:
            insertItemBetween(current, node, current.vertical)
            #print("Inserted ", val, " in between")
            return
        else:
            current = current.vertical
    current.vertical = node
    #print("Inserted ", val, " at the end")
 
def main():
    maxValue = 100
    length = 10
    array = list()
    for x in range(0, length):
        array.append(random.randint(0,99))
    print("The array to be sorted") 
    print(array)
    nodes = list()
    for x in range(0, length):
        node = Node(0)
        nodes.append(node)  
    for x in range(0, length):
        val = array[x]
        index = (val*length)/maxValue   #hasher
        addItemToList(nodes, val, index)
    newarray = list()
    for x in range (0, length):
        current = nodes[x]
        current = current.vertical
        while not current == None:
            newarray.append(current.key)
            current = current.vertical
    print("The sorted array")
    print(newarray)
         
if __name__ == "__main__":
    main()