TweetFollow Us on Twitter

Radix Sort
Volume Number:7
Issue Number:5
Column Tag:Developer's Forum

Radix Sort with Prograph

By Robert McIvor, Gainesville, FL

Radix Sort with Prograph®

[Robert McIvor is a retired research chemist. He has been programming the Macintosh since 1984, and has developed programs for teaching and parsing Loglan®. Loglan is a constructed speakable language, capable of expressing the full range of human experience, yet whose sound stream and grammar are completely unambiguous The written language and potentially the spoken also are machine parsible.1]

Introduction

Prograph™ has been briefly described in MacTutor, March 1990. Now that a compiler to produce stand-alone applications is available, I decided to compare the performance with a C implementation. As a first experience, I attempted to convert the radix sort algorithm I described elsewhere2 to Prograph.

The sort time of the C version of the radix algorithm is linear in n, the number of records, in contrast to most currently used sorts, which are proportional to n log n. Unlike other algorithms, the time is also directly proportional to the length of the sort key; i.e. it takes as long to process 1000 10-byte keys, as to process 10000 1-byte keys. The previously published version sorted 20,000 bytes/sec. on an SE-30. An improved version sorts 88,235 bytes/sec. The C code for unbelievers is provided on this month’s source disk, along with Prograph implementations.

The Prograph Language

Prograph is a data-flow, graphical language with object-oriented capability. Development is in an interpreted mode, with excellent debugging facilities completely integrated. It is suited to those who like planning and coding completely before execution, as well as those who would prefer to code a line at a time and immediately see the result. Unlike many object-oriented programs, local variables may be added or removed from an object with instances. All instances are appropriately adjusted. If while executing, a non-existent method or variable is encountered, one is offered the chance to add it on the fly. Run-time errors are well explained. A faulty value may be temporarily fixed, and execution allowed to proceed, or the code may be fixed, in which case the execution is automatically backed up to the point where the code was changed. Current data values can be examined by double clicking on their entry and exit points in the flow diagram, which is the code.

One of the nice features of Prograph is that one does not have to concern oneself with event loops, updating, activating, screen redrawing, Multifinder compatibility, resizing, zooming etc. unless one so wishes. All these things are handled automatically.

The correct number of input and output terminals is provided with the icon for both Prograph internal and Macintosh toolbox routines, and the input is type-checked.

The Algorithm

Let us consider a series of decimal numbers to be sorted. If one sets up 10 bins, passes through the list of numbers placing each in the appropriate bin according to the least significant digit, and then combines the bins in order without changing the order of numbers in the bin, by repeating the process with the next most significant digit until all digits have been used, one will have sorted the numbers. For computer implementation, the bins are linked lists, and only pointers to the data are manipulated. If bit bins are used, only two lists need be manipulated, while for byte bins, up to 256 may be required, depending on the nature of the data. After each pass through the sort key, the lists are joined, and the new list is used for the next pass. For a straightforward implementation, the sort time depends linearly on the number of records to be sorted, and the number of passes, which in turn is related only to the number of “bins” and sort key length.

The Prograph Implementation

Figure 1 shows a window, designed with the Application editor of Prograph. It contains two edit text items, three fixed text, and a button. Each item when drawn is given a name, and the button is assigned a routine dosort to be executed when it is pressed. Note that if no menu is provided to Prograph, a default menu appears which contains the Apple menu (with an ‘About Radix Sort ’ item and the desk accessories) and a File menu with a ‘Quit’ item.

Figure1 - Display window

Figure 2 shows the dosort code. Since it belongs to the Window class, three inputs are automatically provided, viz. the window pointer, the button item, and the event record. I have only used the Window record, as data for two local routines called get-parameters, and set-parameters. Local routines can be used at any time to reduce clutter in a code window. They can be set up before coding, or a set of routines in a window can be enclosed in a marquee or otherwise selected, and converted to a local. If the latter method is used, the icon automatically has the proper input and output terminals.

Figure 2 - Dosort code window

The sort routine was developed and tested independently with fixed inputs, and attached to the window later.

Figure 3 - Get-parameters code window

Figure 3 shows the get-parameters local. The edit text items are named Sortsize and Sortlist. The built-in universal find-item takes a window pointer and item name/number, and provides as output the item number/name, and the item. The text attribute of the items are read. These are strings. The built-in routine from-string converts the string to a list, integer, or other type depending on its form. Thus Sortsize becomes an integer, and Sortlist becomes a list.

Figure 4 shows the set-parameters routine. In this case the text item Time is found. The sort times and sort list are converted to strings with to-string The time is concatenated with the string “Time in ticks: “ and placed in the text item, and the sorted list in the edit text item.

Figure 4 - Set-parameters code window

Figure 5 - Sort code window

For the sort itself (Figure 5), two persistents were set up. The first, Collation, was the list (A a B b C c D d E e F f G g H h I i J j K k L l M m N n O o P p Q q R r S s T t U u V v W w X x Y y Z z 0 1 2 3 4 5 6 7 8 9) and the second, Empty, was a list of 62 null lists.

The list to be sorted, the Empty persistent and the sort length are passed into the local outer-loop The partially sorted output, and the length (which is internally altered) are recycled into the input using the loop operation. Note how easy timing is with Prograph. Two times are obtained with the Toolbox routine TickCount and subtracted. Synchronization arrows are used to show that the first must be done before outer-loop and the second afterwards. This is easily adapted to timing any operation.

The outer-loop local is shown in Figure 6. A copy is made of the Empty persistent, as the feed-back from sort-one-level changes it if this is not done, and changed persistents persist through subsequent executions. The three inputs are passed to the window routine sort-one-level which is also a loop operation with all three outputs looped back to the input. The final partially sorted output is a list of lists, which is converted to a simple list of strings with the Window routine fix-string. An earlier version had the input accept the list of lists, but as the extraction was recursive, the sort-one-level had to be internal to the extraction routine, and the final output had to be processed. The current version proved to be faster.

Figure 6 - Outer-loop code window

Also the sort-length is checked, and the outer-loop is terminated if the value is zero. After one level is sorted, the count is reduced by one. Synchros are used to ensure the proper execution order.

Figure 7 - Sort-one-level code window

Figure 7 shows the sort-one-level routine. The first step is to detach one string from the sort list and check the remainder for the empty list. If true, the routine terminates at the end of the current pass. One byte is extracted from the detached string at the current sort-key position using the middle function, and passed to the (in) function to determine its position in the persistent list Collation. The output is a numerical position, which is passed to get-nth to locate the sublist (“bin”) for the detached item, which is then attached to the bin list at the right end with attach-r. The modified bin is re-inserted into the initially-empty list of lists with set-nth! and recycling continues until each item has been placed in its “bin”.

Figure 8 - Fix-string code window

Figure 8 shows the Window routine fix-string This passes a null list and the partially-sorted list of lists to a routine ‘simplify’ which loops until complete.

Simplify (Figure 9) checks for and terminates on a null list. Otherwise it removes the first item with detach-l and cycles the residual list. The detached item is sent to the Window routine process (Figure 10) which has 3 cases. The first checks for a null list (empty “bin”) and ignores it if true. The second checks if the detached item was a list. If so, it joins it to the list being built. Initially, this was done by recursion, but it was found stack overflow occurred with only a moderate number of items to be sorted. The third case attaches a simple string to the output list. When outer-loop reaches completion, the output list is the sorted list.

Figure 9 - Simplify code window

Figure 10 - Process code window

Another approach, involving only two bins is also included on the source disk. The outer loop is similar, except that the sort-one-level routine is not looped, and only the count and sort key are input.

Figure 11 - 2-bin Sort-one-level window

The 2-bin sort-one-level (Figure 11) uses the Prograph list processing operation. A single operation produces a list of all the bytes in the current ‘count’ position of the input list items. This list, and the original sort-key list are passed to the routine bitsort, which returns a list sorted by the count byte. The bitsort routine (Figure 12) takes a list input of bit masks (for simple ASCII, the 8th bit is ignored). The byte list and the sort key lists are sorted by each bit in turn by the routine bitloop and the sorted lists are looped back to the input. The bitloop routine (Figure 13) uses the local extract-a-bit to get a list of the appropriate bits of each byte in the byte list, and passes the bit list to two instances of a routine split-by-bit which puts the byte list and the sort key list into one of two lists depending on whether the bit is 0 or non-zero. Each of the list pairs is then joined to produce two single bit-sorted lists which are recycled into the input of bit-loop.

Figure 12 - Bitsort code window

Figure 13 - Bitloop code window

Figure 14 - Extract-a-bit code window

The extract-a-bit local (Figure 14) converts the byte with to-ascii, which gives a one-item list, which must be unpacked to give an integer, which can then be bit-anded with the mask to give either 0 or the mask-value.

The routine split-by-bit (straightforward, not shown) takes the bit-list and the byte or sort-key list, compares each bit-list member to 0 and puts the corresponding member of the other list into one of two output lists depending on the result.

Results

Before programming the first method, I determined by timing that extraction and insertion of the nth item of a list was reasonably independent of n, for lists up to 1000 in length.

The first method (sorting by bytes) is reasonably linear over short intervals, but much less so over long intervals. Some routines, like unpacking the list-of-lists are probably dependent on n. The times to sort the same list vary appreciably, probably because of garbage collection during the sort. Unlike the C routine, it is also somewhat dependent on the original order of the sort keys. It is, however, nearly linear in its dependence on the number of bytes per key.

The second method is much more nearly linear in n.

For comparison of all three methods, I sorted from 1 to 62 members of a 62-membered 5-byte list (with the Prograph programs), and a list of 1000 5-membered Loglan ‘primitives’. The 1000 word sort took .057secs with the C program, about 207 secs with the interpreted byte-sorted version, and 1029 seconds with the bit-sorted version.

A compiler which is available with Prograph produces a double-clickable stand-alone program, which can be listed in assembly language. The byte-sort compiled program sorted the 1000 words in from 64-100 seconds, a 2 to 3-fold speedup, but the bit-sorted compiled version ran in 25 seconds, a 40-fold increase in speed! TGS systems point out that list operations are faster than loop operations, which certainly seems to be the case.

The compilation took about 75 seconds, and the size of the compiled programs were 178 and 173K compared with the interpreted code at 61 and 56K, despite the documentation which claims that compiling saves space. Of course the interpreted code requires the interpreter as well.

Neither method, as such, would be very practical for the radix sort, since the fastest time is still 450 times slower than C. Fortunately, one can have the best of both worlds. One can write XPrims, which can be used in interpreted (or compiled) programs just as the built-in routines provided with Prograph, or XCode, which are external routines which can be linked with Prograph compiled programs. These can be written in Think C or MPW C. One can therefore have the advantage of a very easily produced graphical interface compatible with Macintosh guidelines combined with rapidly executing C routines. As my C compiler is not one of those supported, I leave the writing of a sort X-Prim as an exercise for the reader.

The program as presented does not do any checking of the input. While the interpreted version seems foolproof, the compiled program bombs easily with bad data. The inclusion of checking is also left as an exercise for the reader.

References

1 Further information on Loglan can be obtained from the non-profit Loglan Institute Inc., 1701 N.E. 75th St., Gainesville FL 32601, or from the author.

2 McIvor Robert A., “A General First-Order Sorting Algorithm”, Dr. Dobb’s Journal,M&T Publishing, Inc., Sep 1986, pg. 32

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Mellel 3.5.5 - The word processor for sc...
Mellel is the leading word processor for OS X and has been widely considered the industry standard since its inception. Mellel focuses on writers and scholars for technical writing and multilingual... Read more
Bookends 12.8.3 - Reference management a...
Bookends is a full-featured bibliography/reference and information-management system for students and professionals. Bookends uses the cloud to sync reference libraries on all the Macs you use.... Read more
Carbon Copy Cloner 4.1.18 - Easy-to-use...
Carbon Copy Cloner backups are better than ordinary backups. Suppose the unthinkable happens while you're under deadline to finish a project: your Mac is unresponsive and all you hear is an ominous,... Read more
Hopper Disassembler 4.2.14- - Binary dis...
Hopper Disassembler is a binary disassembler, decompiler, and debugger for 32- and 64-bit executables. It will let you disassemble any binary you want, and provide you all the information about its... Read more
BetterTouchTool 2.291 - Customize Multi-...
BetterTouchTool adds many new, fully customizable gestures to the Magic Mouse, Multi-Touch MacBook trackpad, and Magic Trackpad. These gestures are customizable: Magic Mouse: Pinch in / out (zoom... Read more
Sound Studio 4.8.11 - Robust audio recor...
Sound Studio lets you easily record and professionally edit audio on your Mac. Easily rip vinyls and digitize cassette tapes, or record lectures and voice memos. Prepare for live shows with live... Read more
Sound Studio 4.8.11 - Robust audio recor...
Sound Studio lets you easily record and professionally edit audio on your Mac. Easily rip vinyls and digitize cassette tapes, or record lectures and voice memos. Prepare for live shows with live... Read more
BetterTouchTool 2.291 - Customize Multi-...
BetterTouchTool adds many new, fully customizable gestures to the Magic Mouse, Multi-Touch MacBook trackpad, and Magic Trackpad. These gestures are customizable: Magic Mouse: Pinch in / out (zoom... Read more
Carbon Copy Cloner 4.1.18 - Easy-to-use...
Carbon Copy Cloner backups are better than ordinary backups. Suppose the unthinkable happens while you're under deadline to finish a project: your Mac is unresponsive and all you hear is an ominous,... Read more
Hopper Disassembler 4.2.14- - Binary dis...
Hopper Disassembler is a binary disassembler, decompiler, and debugger for 32- and 64-bit executables. It will let you disassemble any binary you want, and provide you all the information about its... Read more

The best 2v2 card combos in Clash Royale
2v2 is making it's grand return toClash Royalequite soon. 2v2 has quickly become one of the game's most popular gameplay modes, though they still have yet to make it a permanent fixture in the game. 2v2 is exciting and adds some new flavor to... | Read more »
The best games we played this week - Aug...
Another busy week has come to a close. We played a lot of excellent games this week and now it's time to look back and reflect on some our favorites. Here are our picks for the week of August 18. [Read more] | Read more »
War Wings beginner's guide - how to...
War Wings is the newest project from well-established game maker Miniclip. It's a World War II aerial dogfighting game with loads of different airplane models to unlock and battle. The game offers plenty of single player and multiplayer action. We... | Read more »
How to win every 2v2 battle in Clash Roy...
2v2 is coming back to Clash Royale in a big way. Although it's only been available for temporary periods of time, 2v2 has seen a hugely positive fan response, with players clamoring for more team-based gameplay. Soon we'll get yet another taste of... | Read more »
Roll to Win with Game of Dice’s new upda...
Joycity’s hit Game of Dice gets a big new update this week, introducing new maps, mechanics, and even costumes. The update sets players loose on an exciting new map, The Cursed Tower, that allows folks to use special Runes mid-match. If you feel... | Read more »
Bottom of the 9th (Games)
Bottom of the 9th 1.0.1 Device: iOS iPhone Category: Games Price: $4.99, Version: 1.0.1 (iTunes) Description: Play the most exciting moment of baseball in this fast-paced dice and card game! | Read more »
The best apps for viewing the solar ecli...
If you somehow missed the news, many parts of the United States will be witness to a total solar eclipse on August 21 for the first time in over 90 years. It'll be possible to see the eclipse in at least some capacity throughout the continental U... | Read more »
The 5 best mobile survival games
Games like ARK: Survival Evolved and Conan Exiles have taken the world of gaming by storm. The market is now flooded with hardcore survival games that send players off into the game's world with nothing but maybe the clothes on their back. Never... | Read more »
Portal Walk (Games)
Portal Walk 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Portal Walk is adventure and relaxing platform game about Eugene. Eugene stuck between worlds and trying to find way back home.... | Read more »
Technobabylon (Games)
Technobabylon 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: City of Newton, 2087. Genetic engineering is the norm, the addictive Trance has replaced almost any need for human interaction,... | Read more »

Price Scanner via MacPrices.net

15-inch 2.2GHz Retina MacBook Pro, Apple refu...
Apple has Certified Refurbished 2015 15″ 2.2GHz Retina MacBook Pros available for $1699. That’s $300 off MSRP, and it’s the lowest price available for a 15″ MacBook Pro. An Apple one-year warranty is... Read more
Apple refurbished Mac minis available startin...
Apple has Certified Refurbished Mac minis available starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: – 1.4GHz Mac mini: $419 $80 off MSRP – 2.6GHz Mac... Read more
Apple refurbished iPad Pros available startin...
Apple has Certified Refurbished 2016 12″ WiFi iPad Pros available starting at $589. An Apple one-year warranty is included with each model, and shipping is free: – 32GB 12″ iPad Pro WiFi: $589... Read more
Weekend sale: 13-inch MacBook Pros for up to...
Amazon has new 2017 13″ MacBook Pros on sale today for up to $200 off MSRP, each including free shipping: – 13″ 3.1GHz/256GB Space Gray MacBook Pro (MPXV2LL/A): $1599.99 $200 off MSRP – 13″ 3.1GHz/... Read more
Back To School With The Edge Desk All-in-one...
Back to school is just around the corner, and the ergonomically correct Edge Desk all-in-one portable kneeling desk is ideal for students living in dorms and small apartments, Edge Desk features:... Read more
Norton Core Secure Wi-Fi Router Now Available...
First introduced at the 2017 Consumer Electronics Show (CES), Norton Core, a secure, high-performance Wi-Fi router, fundamentally changed the concept of Wi-Fi routers by making security the primary... Read more
ViewSonic Adds New 27-inch 4K UHD Monitor to...
ViewSonic Corp. has introduced the VP2785-4K, a 27-inch 4K UHD (3840×2160) monitor that delivers precise and consistent color representation and performance to ensure incredible image quality. Built... Read more
Apple now offering Certified Refurbished 2017...
Apple is now offering Certified Refurbished 2017 27″ iMacs for up to $350 off original MSRP. Apple’s one-year warranty is standard, and shipping is free. The following models are available: – 27″ 3.... Read more
13-inch 2.3GHz MacBook Pros on sale for $100...
Amazon has the new 2017 13″ 2.3GHz MacBook Pros on sale today for $100 off MSRP, each including free shipping: – 13″ 2.3GHz/128GB Space Gray MacBook Pro (MPXQ2LL/A): $1199.99 $100 off MSRP – 13″ 2.... Read more
Clearance 2016 13-inch MacBook Airs available...
B&H Photo has clearance 2016 13″ MacBook Airs available for up to $200 off original MSRP. Shipping is free, and B&H charges NY & NJ sales tax only: – 13″ 1.6GHz/128GB MacBook Air (MMGF2LL... Read more

Jobs Board

Development Operations and Site Reliability E...
Development Operations and Site Reliability Engineer, Apple Payment Gateway Job Number: 57572631 Santa Clara Valley, California, United States Posted: Jul. 27, 2017 Read more
Frameworks Engineering Manager, *Apple* Wat...
Frameworks Engineering Manager, Apple Watch Job Number: 41632321 Santa Clara Valley, California, United States Posted: Jun. 15, 2017 Weekly Hours: 40.00 Job Summary Read more
Map Quality Analyst Lead, *Apple* Maps Eval...
…a team of subject matter experts measuring the quality of a range of Apple Maps algorithms, such as Map search, recommendations, and routing. Our group works with Read more
Business Development Manager, *Apple* Pay -...
Job Summary Apple Pay is seeking an experienced Business Development professional to join the Apple Pay team to develop partnerships and strategic alliances with Read more
Information Systems Engineer, *Apple* Retai...
Job Summary Do you have a passion for the technology and systems that make Apple amazing? Are you interested in joining IS&T Retail on what they do best? This is an Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.