C Program To Implement Address Calculation Sort Algorithm
Learn how to implement Address Calculation Sort Algorithm in C Programming Language. This code for Address Calculation Sort in C makes use of Linked List.
What is Address Calculation Sort Algorithm?
The Address Calculation Sorting makes use of Hash Function Algorithm for sorting a set of elements. These types of functions are generally known as Order Preserving Hashing Function. This function is applied to all the elements to be sorted. According to the value of the hashing function, every element to be sorted is to be placed in a pre-defined set.
Every set is represented by a linked list. The starting address of each linked list can be maintained by an array of pointers. In every set, the elements have to be inserted in sorted order and, therefore, sorted linked lists needs to be taken.
C Program For Address Calculation Sort Algorithm using Linked List
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | #include<stdio.h> #include<stdlib.h> #define MAX 55 struct node { int data; struct node *link; }; struct node *top[6]; int limit, elements[MAX]; int maximum; void insert(int num, int address); void address_sorting(); int hash_function(int number); int main() { int count; printf("\nEnter Total Number of Elements To Sort:\t"); scanf("%d", &limit); for(count = 0; count < limit; count++) { printf("Enter Element No. %d:\t", count + 1); scanf("%d", &elements[count]); } for(count = 0; count < limit; count++) { if(elements[count] > maximum) { maximum = elements[count]; } } address_sorting(); printf("\nSorted List\n"); for(count = 0; count < limit; count++) { printf("%3d", elements[count]); } printf("\n"); return 0; } void address_sorting() { int count, temp; struct node *p; int address; for(count = 0; count <= 6; count++) { top[count] = NULL; } for(count = 0; count < limit; count++) { address = hash_function(elements[count]); insert(elements[count], address); } printf("\n"); for(count = 0; count <= 6; count++) { printf("top(%d) -> ", count); p = top[count]; while(p != NULL) { printf("%3d", p->data); p = p->link; } printf("\n"); } printf("\n"); count = 0; for(temp = 0; temp <= 6; temp++) { p = top[temp]; while(p != NULL) { elements[count++] = p->data; p = p->link; } } } void insert(int num, int address) { struct node *q, *temp; temp = malloc(sizeof(struct node)); temp->data = num; if(top[address] == NULL || num < top[address]->data) { temp->link = top[address]; top[address] = temp; return; } else { q = top[address]; while(q->link != NULL && q->link->data < num) { q = q->link; } temp->link = q->link; q->link = temp; } } int hash_function(int number) { int address; float temp; temp = (float)number / maximum; address = temp * 6; return(address); } |
Address Calculation Sort Algorithm Analysis
The time is dependent on the insertion time of elements in the sorted linked list. This algorithm is not an in-place sort but it is a stable sort.
The run time depends on how the hash function distributes the elements amongst the lists. If every element is evenly distributed among different lists, then run time will be O(n), else it will be O(n2).
Output
If you have any compilation errors or doubts about Address Calculation Sort in C Programming, let us know about it in the comment section below.
I don’t think anyone uses Address Calculation Sort Algorithm to sort integer arrays.
I will have to first understand hashing algorithm and its concept before this sorting program!
The address calculation sorting algorithm is an advanved version of ther insertion sorting algorithm. It basically used extra memory space for improvement.