Address Calculation Sort in Python using hashing

In this tutorial, we will learn about Address Calculation Sort in Python which is done using ‘hashing’.

Address Calculation Sort

In Address Calculation Sorting algorithm, Hash Function f is used i.e.: if x<=y, f(x)<=f(y) also called Hash Preserving Property. 

Address Calculation Sort uses a list of Linked List to store the values which is also known as ‘address table’. The function ‘f’ is applied to all the elements in the list to find its corresponding address in the address table. Then all the values are compared with the already existing values present at their corresponding addresses in a sorted manner, and after the sorting is done, then the address table is said to be sorted. Therefore, we go through all the addresses sequentially and place the values at that address in the input array.

Code

class Node(object): 

  def __init__(self, data = None): 
    self.data = data 
    self.nextNode = None

class LinkedList(object): 

  def __init__(self): 
    self.head = None

  def insert(self, data): 
    newNode = Node(data) 

    if self.head == None or data < self.head.data: 
      newNode.nextNode = self.head 
      self.head = newNode 

    else: 
      current = self.head 
      
      while current.nextNode != None and current.nextNode.data < data: 
        current = current.nextNode 

      newNode.nextNode = current.nextNode 
      current.nextNode = newNode 

def adCalSort(a): 

  listOfLinkedLists = [] 
  for i in range(n): 
    listOfLinkedLists.append(LinkedList()) 

  maximum = max(a) 
 
  for val in a: 
    address = hashFunction(val, maximum) 
    listOfLinkedLists[address].insert(val) 

  for i in range(n): 
    current = listOfLinkedLists[i].head 
    print("ADDRESS " + str(i), end = ": ") 

    while current != None: 
      print(current.data, end = " ") 
      current = current.nextNode 

    print() 

  index = 0
  for i in range(n): 
    current = listOfLinkedLists[i].head 

    while current != None: 
      a[index] = current.data 
      index += 1
      current = current.nextNode 

def hashFunction(num, maximum): 

  address = int((num * 1.0 / maximum) * (n-1)) 
  return address 
 
a = [] 
n = int(input("\n Enter the size of the array: "))
print("\n Enter the array elements")
for i in range(n):
    a.append(int(input()))
print("\nArray is: " + " ".join([str(x) for x in a])) 
adCalSort(a) 
print("\nSorted array: " + " ".join([str(x) for x in a])) 

Example- For an array of size i.e. n=’9′

Input

9

8

7

6

5

4

3

2

1

Output

Sorted array: 1 2 3 4 5 6 7 8 9