Click here to Skip to main content
15,441,434 members
Please Sign up or sign in to vote.
1.00/5 (3 votes)
See more:
# Python3 code for implementation of  
# Address Calculation Sorting using Hashing 

  
# Size of the address table (In this case 0-9) 

SIZE = 10

  

class Node(object): 

  

    def __init__(self, data = None): 

        self.data = data 

        self.nextNode = None

  

class LinkedList(object): 

  

    def __init__(self): 

        self.head = None

  

    # Insert values in such a way that the list remains sorted 

    def insert(self, data): 

        newNode = Node(data) 

  

        # If there is no node or new Node's value 

        # is smaller than the first value in the list, 

  

        # Insert new Node in the first place 

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

            newNode.nextNode = self.head 

            self.head = newNode 

  

        else: 

            current = self.head 

              

            # If the next node is null or its value 

            # is greater than the new Node's value, 

   

            # Insert new Node in that place 

            while current.nextNode != None \ 

                    and \ 

                    current.nextNode.data < data: 

                current = current.nextNode 

  

            newNode.nextNode = current.nextNode 

            current.nextNode = newNode 

              
# This function sorts the given list  
# using Address Calculation Sorting using Hashing 

def addressCalculationSort(arr): 

  

    # Declare a list of Linked Lists of given SIZE 

    listOfLinkedLists = [] 

    for i in range(SIZE): 

        listOfLinkedLists.append(LinkedList()) 

  

    # Calculate maximum value in the array 

    maximum = max(arr) 

  

    # Find the address of each value 

    # in the address table  

    # and insert it in that list 

    for val in arr: 

        address = hashFunction(val, maximum) 

        listOfLinkedLists[address].insert(val) 

      

    # Print the address table  

    # after all the values have been inserted 

    for i in range(SIZE): 

        current = listOfLinkedLists[i].head 

        print("ADDRESS " + str(i), end = ": ") 

  

        while current != None: 

            print(current.data, end = " ") 

            current = current.nextNode 

  

        print() 

      

    # Assign the sorted values to the input array 

    index = 0

    for i in range(SIZE): 

        current = listOfLinkedLists[i].head 

  

        while current != None: 

            arr[index] = current.data 

            index += 1

            current = current.nextNode 

              

  
# This function returns the corresponding address 
# of given value in the address table 

def hashFunction(num, maximum): 

  

    # Scale the value such that address is between 0 to 9 

    address = int((num * 1.0 / maximum) * (SIZE-1)) 

    return address 

  
# ------------------------------------------------------- 
# Driver code 

  
# giving the input address as follows 

arr = [29, 23, 14, 5, 15, 10, 3, 18, 1] 

  
# Printing the Input array 

print("\nInput array: " + " ".join([str(x) for x in arr])) 

  
# Performing address calculation sort 
addressCalculationSort(arr) 

  
# printing the result sorted array 

print("\nSorted array: " + " ".join([str(x) for x in arr])) 


What I have tried:

Converting object oriented code to c program is difficult for me
Posted
Updated 10-Jul-21 1:06am
Comments
Richard MacCutchan 17-Nov-19 7:05am    
Unless you are an experienced C programmer you will need to search Google for a tool to help you.

1 solution

Here you are (note the hash function, and hence the output, it is slightly different)
C
#include<stdio.h>
#include <stdlib.h>
#include <assert.h>
#define SIZE	10

typedef struct Node
{
	unsigned data;
	struct Node * next;
} Node;

// release memory
void list_cleanup(Node *pHead )
{
	while ( pHead )
	{
		Node * pNext = pHead->next;
		free( pHead );
		pHead = pNext;
	}
}

// insert values in such a way that the list remains sorted
Node * list_insert(Node * pHead, int data )
{
	Node * pNewNode = (malloc(sizeof (Node)));
	assert(pNewNode);
	pNewNode->data = data;

	if ( ! pHead  || pNewNode->data < pHead->data )
	{
		pNewNode->next = pHead;
		return pNewNode;			
	}
	
	Node * pCurNode = pHead;
	while ( pCurNode->next && pCurNode->next->data < pNewNode->data )
	{
		pCurNode = pCurNode->next;
	}	
	pNewNode->next = pCurNode->next;
	pCurNode->next = pNewNode;
	return pHead;
}

// the has function is slightly different
unsigned hash_function(int n, int max)
{
	unsigned address =  (n * SIZE)/(max+1);
	return address;
}


void address_calculation_sort( unsigned  arr[], unsigned  ArrSize)
{
	assert(arr);
	if ( ArrSize < 1) return;

	Node * pHead[SIZE];
	unsigned n;
	for (n=0; n<SIZE; ++n)
		pHead[n] = NULL;
	
	// find the maximum of the array values
	int max = arr[0];
	for (n=1; n < ArrSize; ++n)
		if ( max < arr[n]) 
			max = arr[n];
	
	for (n=0; n<ArrSize; ++n)
	{
		unsigned v = arr[n];
		unsigned address = hash_function(v, max);
		pHead[address] = list_insert(pHead[address], v);
	}

	
	for (n=0; n<SIZE; ++n)
	{
		printf("ADDRESS %u: ", n );
		Node *pCurNode = pHead[n];
		while ( pCurNode )
		{
			printf("%u ", pCurNode->data);
			pCurNode = pCurNode->next;
		}
		printf("\n");
	}

	unsigned index = 0;
	for (n=0; n<SIZE; ++n)
	{
		Node *pCurNode = pHead[n];
		while ( pCurNode )
		{
			arr[index++] = pCurNode->data;
			pCurNode = pCurNode->next;
		}
	}
	
	for (n=0; n<SIZE; ++n)
		list_cleanup(pHead[n]);

}//<- address_calculation_sort



int main()
{

	unsigned arr [] =  { 29, 23, 14, 5, 15, 10, 3, 18, 1 };
	const unsigned ArrSize = sizeof(arr)/sizeof(arr[0]);
	unsigned n;
	printf("Input array: ");
	for (n=0; n<ArrSize; ++n)
		printf("%u ",arr[n]);
	printf("\n");
	
	address_calculation_sort(arr, ArrSize);
	
	printf("Sorted array: ");
	for (n=0; n<ArrSize; ++n)
		printf("%u ",arr[n]);
	printf("\n");

	return 0;
}

Output:
Input array: 29 23 14 5 15 10 3 18 1 
ADDRESS 0: 1 
ADDRESS 1: 3 5 
ADDRESS 2: 
ADDRESS 3: 10 
ADDRESS 4: 14 
ADDRESS 5: 15 
ADDRESS 6: 18 
ADDRESS 7: 23 
ADDRESS 8: 
ADDRESS 9: 29 
Sorted array: 1 3 5 10 14 15 18 23 29 
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900