Heap Sort for Customer Data in C
Explore the implementation of heap sort in C, a powerful sorting algorithm that efficiently organizes customer records based on loyalty and name. This comprehensive guide will walk you through the intricacies of heap sort, making it a valuable resource for both students seeking help with their C assignment and coding enthusiasts looking to master sorting algorithms. Discover practical insights into sorting and enhance your programming skills while diving into the world of heap sorting. Whether you're tackling complex data sorting tasks or simply expanding your coding knowledge, this guide has you covered.
Block 1: Main Function
```c
int main() {
heapsort("sample.dat");
return 0;
}
```
This block contains the main function. It calls the `heapsort` function, passing the file name "sample.dat" as an argument, and returns 0 to indicate successful program execution.
Block 2: Header File Inclusion
```c
#ifndef _HEAPSORT_H
#define _HEAPSORT_H
int heapsort(const char *filename);
#endif
```
This block defines a C header file named "heapsort.h" and includes a declaration for the `heapsort` function. The `_HEAPSORT_H` preprocessor directive guards against multiple inclusions of this header in a single compilation.
Block 3: Function Definitions and Includes
```c
#include "heapsort.h"
#include "customer.h"
#include < stdio.h >
#include < stdlib.h >
#include < string.h >
```
In this block, various header files are included. "heapsort.h" and "customer.h" are included for function declarations and data structures, while standard library headers are included for I/O and memory operations.
Block 4: Helper Method - `heapify`
```c
void heapify(customer* records, int parentIndex, int lastIndex)
{
int done = 0;
customer orphan = records[parentIndex];
int leftChildIndex = 2 * parentIndex + 1;
while (!done && leftChildIndex <= lastIndex)
{
// Find the more prioritized child that replaces the parent
int priorityChildIndex = leftChildIndex;
int rightChildIndex = leftChildIndex + 1;
if (rightChildIndex <= lastIndex)
{
// The child with the lower loyalty is prioritized
// If, however, both children have the same loyalty, we compare them alphabetically by name.
if (records[rightChildIndex].loyalty > records[priorityChildIndex].loyalty
|| (records[rightChildIndex].loyalty == records[priorityChildIndex].loyalty && strcmp(records[rightChildIndex].name, records[priorityChildIndex].name) > 0))
priorityChildIndex = rightChildIndex;
}
// Swap with the parent if the chosen child has better loyalty or name (if loyalty is equal)
if (records[priorityChildIndex].loyalty > orphan.loyalty
|| (records[priorityChildIndex].loyalty == orphan.loyalty && strcmp(records[priorityChildIndex].name, orphan.name) > 0))
{
records[parentIndex] = records[priorityChildIndex];
parentIndex = priorityChildIndex;
leftChildIndex = 2 * parentIndex + 1;
}
else
{
// If no swaps are done, we assume the rest of the sub-tree is already arranged
done = 1;
}
}
records[parentIndex] = orphan;
}
```
This block defines the `heapify` function, which is a helper method for the heap sort. It arranges the binary heap by moving records to their correct positions. The function takes an array of customer records, a parent index, and the last index as arguments. It uses a while loop to adjust the heap.
Block 5: Helper Method - `swap`
```c
void swap(customer* records, int i, int j)
{
customer record = records[i];
records[i] = records[j];
records[j] = record;
}
```
This block defines the `swap` function, which swaps two customer records at the specified positions in the array. It's used to exchange elements during the heap sort process.
Block 6: Function - `heapsort`
```c
int heapsort(const char *filename) {
FILE* file = fopen(filename, "rb");
// Stop if the file cannot be opened
if (!file)
return 0;
// Find out the total number of records
fseek(file, 0, SEEK_END);
long fileSize = ftell(file);
int numRecords = fileSize / sizeof(customer);
// Prepare a fixed array where to store the customer records
customer* records = (customer *)malloc(sizeof(customer) * numRecords);
if (!records)
return 0;
// Load the customer records into the array
fseek(file, 0, SEEK_SET);
for (int i = 0; i < numRecords; i++)
if(!fread(&records[i], sizeof(customer), 1, file))
return 0;
fclose(file);
// Perform heap sort, first arrange the tree
for (int parentIndex = numRecords / 2 - 1; parentIndex >= 0; parentIndex--)
heapify(records, parentIndex, numRecords - 1);
// Next, bubble up the records by priority
swap(records, 0, numRecords - 1);
for (int lastIndex = numRecords - 2; lastIndex > 0; lastIndex--)
{
heapify(records, 0, lastIndex);
swap(records, 0, lastIndex);
}
// Write the results back to the file
file = fopen(filename, "wb");
for (int i = 0; i < numRecords; i++)
fwrite(&records[i], sizeof(customer), 1, file);
fclose(file);
// Clean up
free(records);
return 1;
}
```
This block contains the `heapsort` function, which is responsible for sorting customer records. The function takes a filename as input, reads records from the file, performs heap sort, and writes the sorted records back to the file. It returns 1 on success and 0 on failure.
Conclusion
In conclusion, this guide has provided a comprehensive breakdown of a C programming example demonstrating heap sort for customer records. We've explored the code in detail, block by block, to help you understand how this algorithm can be used to efficiently sort records based on loyalty and name. Feel free to use this code as a reference for your programming assignments or learning purposes. If you have any questions or need further assistance in your coding journey, don't hesitate to reach out. Exploring algorithms like heap sort can be a valuable step in becoming a more proficient programmer and problem solver.