BBS: Inland Empire Archive Date: 10-24-92 (07:14) Number: 373 From: JERRY ALDRICH Refer#: NONE To: RYAN WELLMAN Recvd: NO Subj: Re: Fast Sorting Algorith Conf: (2) Quik_Bas

(* On or about 22 Oct 92 14:36:00, in a message to All, *) (* Ryan Wellman blurted out the following: *) RW> Hello, RW> This is a sort routine that I just wrote. It is extremely fast. RW> It will sort an array with 16,383 random entries in 7.5 seconds on a RW> 386/40. I would like to see your comments/modifications, and I would RW> like to see if this routine is currently the fastest one in existance. RW> I warn you, if it is I'll be gloating. It's also fully comented so that RW> you won't have many problemes figuring out what I'm doing. Well, I though I had you beat :) The test I ran was on a 386SX/16 using PDS 7.1 and the QBX environment. The only modification I made to your routine was to strip out the comment lines. Here are the results when running in the environment: FastSort: .0585 MySort: .0605 based on 64 entries. FastSort: .1699 MySort: .2207 based on 128 entries. FastSort: .5996 MySort: .5507 based on 256 entries. FastSort: 1.269 MySort: 1.208 based on 512 entries. FastSort: 3.900 MySort: 3.679 based on 1024 entries. FastSort: 8.679 MySort: 8.191 based on 2048 entries. FastSort: 21.58 MySort: 20.11 based on 4096 entries. FastSort: 74.31 MySort: 67.83 based on 8192 entries. FastSort: 168.4 MySort: 153.4 based on 16384 entries. At this point, I was pretty pleased with myself. However, just for fairness, I decided to compile the thing and try it again. Here are the results when compiled: FastSort: 00000 MySort: 00000 based on 64 entries. FastSort: .0488 MySort: .0605 based on 128 entries. FastSort: .0605 MySort: .0507 based on 256 entries. FastSort: .1093 MySort: .1699 based on 512 entries. FastSort: .4902 MySort: .6093 based on 1024 entries. FastSort: 1.160 MySort: 1.259 based on 2048 entries. FastSort: 2.800 MySort: 3.240 based on 4096 entries. FastSort: 9.781 MySort: 11.15 based on 8192 entries. FastSort: 22.12 MySort: 25.32 based on 16384 entries. It a WHOPPING improvement for both routines in speed, but that's to be expected. Much to my dismay, your routine was faster <Sigh>. Now, explain why there is a difference! Here's the routine I used:DEFINTA-ZSUBMySort (InArray()ASINTEGER, Lower AS INTEGER, Upper AS INTEGER) Span = Upper \ 2DOWHILE(Span > 0)FORI = SpanTOUpper - 1FORj = (I - Span + 1)TO1STEP-SpanIFInArray(j) <= InArray(j + Span)THENEXITFORSWAPInArray(j), InArray(j + Span)NEXTjNEXTI Span = Span \ 2LOOPENDSUBAlthough yours seems to be faster, my simpler and smaller :) Later! Jerry --- Renegade v8-27 Beta * Origin: The Bumpkinland BBS - "Home of BLand Software" (1:296/3)

Echo Basic Postings

**Books at Amazon:**

Back to BASIC: The History, Corruption, and Future of the Language

Hackers: Heroes of the Computer Revolution (including Tiny BASIC)

Go to: The Story of the Math Majors, Bridge Players, Engineers, Chess Wizards, Scientists and Iconoclasts who were the Hero Programmers of the Software Revolution

The Advent of the Algorithm: The Idea that Rules the World

Moths in the Machine: The Power and Perils of Programming

Mastering Visual Basic .NET