| |
|
|
|
Submitted on: 5/1/2007 5:36:54 PM
By: Mike Morrow
Level: Beginner
User Rating:
By 2 Users
Compatibility:VB 6.0
Users have accessed this code 6331 times.
| (About the author) |
| | | To illustrate the high efficiency of comb sort, a very wrongly overlooked sort method. Sorts 809K records (40 bytes each) in 48 seconds on a 2GHz Athlon. It runs faster than some Quicksort implementation and does not do any recursion. Quicksort performs poorly in a heavily paged environment. Sorting a large file can create such an environment causing its own longer than needed execution times. Comb Sort does not recurse and, therefore, runs with lowered system demands. Recursion causes additional system memory utilization contending with the data to be sorted. This program illustrates the increased efficiency of sorting in segments then merging the sorted groups into the output dataset. Merging the segments takes a tiny amount more code but it still linear, not recursive.
Input is any file of data. The data (in this implementation) must be fixed length. This is a general purpose routine but can be very easily modified if required for other sorting tasks.
Primary effect is a sorted file. Side effect is possible paging system usage if the data file is very large.
This program easily handles file of 10 million records which, in my case, is about 340 MB of data. It reads in the entire file, sorts it in stages, in memory, then merges the sorted groups to the output dataset. It is odd how many people think that Quicksort it the best general purpose method for sorting and leave it at that. Quicksort has some very high penalties (nearly sorted files for one) and is best when not run to completion but handed over to another type of sort to finish up the busywork such as bubble sort. What a mess, two sort routines to accomplish ONE SORT! Yes, BUBBLESORT can be quite efficient in certain cases such as a backend for Quicksort. CombSort is better than all of that, is a single routine and does not have the high overhead of recursion for millions of levels. It is a simple routine without any recursion at all. A paging environment is hostile to Quicksort but far kinder to comb sort.
Updated on 12/19/04 for better variable record length performance.
Some folks said that I must have been using a horrible quicksort implementation. Turns out that I was using one that someone had not optomized. With complex optimizations, quicksort CAN run faster than combsort but can also run SLOWER than combsort. Depends on the data. Combsort is much more predictable and "stable" in that it runs in about the same amount of time every time and that is a short amount of time, every time. Look on the web for the origins and operational theory of combsort. It is my favorite now. I recommend it for all situations.
Be sure to NOT change the gaps table. It is optimized already. Changing it can double of triple run times.
Enjoy.
| |
 | | | |
 Download 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.
3)Scan the source code with Minnow's Project Scanner
If you don't have a virus scanner, you can get one at many places on the net including:McAfee.com
|
Terms of Agreement:
By using this code, you agree to the following terms...
1) You may use
this code in your own programs (and may compile it into a program and distribute it in compiled format for languages that allow it) freely and with no charge.
2) You MAY NOT redistribute this code (for example to a web site) without written permission from the original author. Failure to do so is a violation of copyright laws.
3) You may link to this code from another website, but ONLY if it is not wrapped in a frame.
4) You will abide by any additional copyright restrictions which the author may have placed in the code or code's description.
| |
|
Other 23 submission(s) by this author
| | | |
 Report Bad Submission | | | | | Your Vote! | |
See Voting Log | | | | Other User Comments |  2/4/2005 1:40:27 PM: Mike Morrow
This code has been updated to sort any length records. However, the sort fields must add up to the total length of the record or data will be lost. If that is the intent, then good, you can sort and reformat (extract data) from files. This working EXAMPLE sorts in descending order. Some day, I hope to add a selection of order direction and not have to use the entire record as the "key". Don't hold your breath!
(If this comment was disrespectful, please report it.)
| | |
Add Your Feedback! | Note:Not only will your feedback be posted, but an email will be sent to the code's author from the email account you registered on the site, so you can correspond directly.
NOTICE: The author of this code has been kind enough to share it with you. If you have a criticism, please state it politely or it will be deleted.
For feedback not related to this particular code, please click here.
|
To post feedback, first please login.
| |
