winzip icon

Super Fast Bucket / Radix sort for a linked list of records from file

Submitted on: 11/17/2015 4:08:35 PM
By: Prosenjit Bandyopadhyay 
Level: Advanced
User Rating: Unrated
Compatibility: C
Views: 6288
author picture

Implemntation of Bucket sort for a list of faculties

This program employs the Bucket / Radix sort method to sort a list of faculty member records taking their IDs as the key.

Created using Turbo C++ IDE (version 8.0) for Windows system.

It first reads the rerords of faculty members from a text file of predified format and keeps them in a linked list. Then they are sorted by using 10 queues (befause radix of the keys is 10). But to do so each of the quees do not take extra memory to hold the records. Rather it creates only a chain of records in the form of linked list. ie., it extracts the nodes from the linked list of records and merely recreates a chain.

So, the sorting algo has time complexity of T(n) = m * lg(n), where n is number of records and

m = maximum number of digits in each key.

It has a space complexity of only O(n), in spite of taking 10 queues.

This program shows uses following things :

1. Text file handling.

2. Singly linear linked list.

3. Dynamic allocation of memory.

4. Linked list implemented Queue.

5. Radix sorting.

The list of Faculty members are contained in a file (Teachers.txt) as

<ID>|<Subject Code> <Class> <Teacher Name>

The list of Subjects are contained in a file (Subects.txt) as

<Subject Code> <Subject Name>

Run the program with the Teachers and Subjects text files as command line arguments as

followng example :

BucktSrt c:\data\Teachers.txt c:\data\Subjects.txt

If the paths to the text files are not provided, they will be assumed to be in the

current folder of the program.

If the subject file is not found then the subjects are printed as 'null' after issing and error message.

If the faculty member file is not found then the program aborts issuing error message.

Following things can be changed:

1. The number of rows in the output screen (stored the symbolic constant SCRROWS).

2. Maximum number of digits in each ID (stored in the symbolic constant MAXDIGITS). But since

the ID is of type int, it is good to stay with 4.

3. Maximum number of subjects in the Subject table (stored in symbolic constant MAXSUBJECTS).

winzip iconDownload code

Note: Due to the size or complexity of this submission, the author has submitted it as a .zip file to shorten your download time. Afterdownloading it, you will need a program like Winzip to decompress it.Virus note:All files are scanned once-a-day by Planet Source Code for viruses, but new viruses come out every day, so no prevention program can catch 100% of them. For your own safety, please:
  1. Re-scan downloaded files using your personal virus checker before using it.
  2. NEVER, EVER run compiled files (.exe's, .ocx's, .dll's etc.)--only run source code.

If you don't have a virus scanner, you can get one at many places on the net

Report Bad Submission
Use this form to tell us if this entry should be deleted (i.e contains no code, is a virus, etc.).
This submission should be removed because:

Your Vote

What do you think of this code (in the Advanced category)?
(The code with your highest vote will win this month's coding contest!)
Excellent  Good  Average  Below Average  Poor (See voting log ...)

Other User Comments

 There are no comments on this submission.

Add Your Feedback
Your feedback will be posted below and an email sent to the author. Please remember that the author was kind enough to share this with you, so any criticisms must be stated politely, or they will be deleted. (For feedback not related to this particular code, please click here instead.)

To post feedback, first please login.