Click here to Skip to main content
14,640,603 members
Rate this:
Please Sign up or sign in to vote.
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 17-Nov-19 4:53am
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

Rate this:
Please Sign up or sign in to vote.

Solution 1

Here you are (note the hash function, and hence the output, it is slightly different)
#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 
   

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




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100