Re: [BLACKBOX] Sorting a Dialog.List

From: [at]} <Chris>
Date: Sun, 16 Sep 2012 11:24:52 +0930

----boundary-LibPST-iamunique-1286148116_-_-
Content-type: text/plain

> -----Original Message-----
> From: BlackBox [mailto:BLACKBOX{([at]})nowhere.xy
> Walkden
> Sent: Sunday, 16 September 2012 2:25 AM
> To: BLACKBOX{([at]})nowhere.xy
> Subject: Re: [BLACKBOX] Sorting a Dialog.List
>
> > From: BlackBox [mailto:BLACKBOX{([at]})nowhere.xy
> > Campbell, Robert (SELEX GALILEO, UK)
> > Sent: 14 September 2012 12:02
>
> > \\ Even a bubble sort would be much faster if it could be run
> > inside the Dialog module Just curious - is there any sorting
> > algorithm that
> works effectively with a single linked list structure?
>
> If there is one which reorganises the list itself I'd guess it's
> fiendishly complicated for little if any performance gain over a
> simple copy from the original list into an ordered list. Inserting
> into an ordered list is quite straightforward.
>

I usually use QuickSort for this sort of thing. It is fairly simple to
implement (if you follow an existing source code example) and it has been
more than efficient for any of my applications to date.

Another possible approach to Stephen's application would be to first copy
the Dialog list to a temporary list of *pointers* to strings so that only
the pointers are shuffled during the sort not the entire contents of each
string. Also the Compare function used does not need to access every
character in a pair of strings to do its job. Once they were sorted they
would be copied back to the Dialog list.

Niklaus Wirth devotes 40 pages to the description, Oberon source code
examples and performance analysis of many different sorting methods in his
"Algorithms and Data Structures" book. If there is a different answer to
Robert's question it might be in there somewhere. The book is available as a
PDF download from:

The original 2004 Oberon version:

http://www.ethoberon.ethz.ch/books.html

or the 2012 version with some changes that resulted from the efforts to
translate it into to Russian:

http://www.inr.ac.ru/~info21/ADen/AD2012.pdf

Regards,
Chris

--
Chris Burrows
Astrobe v4.2: Oberon for ARM Cortex-M3 Microcontrollers 
http://www.astrobe.com
----
To unsubscribe, send a message with body "SIGNOFF BLACKBOX" to LISTSERV{([at]})nowhere.xy----boundary-LibPST-iamunique-1286148116_-_-
Content-type: application/rtf
Content-transfer-encoding: base64
Content-Disposition: attachment; filename="rtf-body.rtf"
e1xydGYxXGFuc2lcYW5zaWNwZzEyNTJcZnJvbXRleHQgXGZiaWRpcyBcZGVmZjB7XGZvbnR0YmwN
CntcZjBcZnN3aXNzIEFyaWFsO30NCntcZjFcZm1vZGVybiBDb3VyaWVyIE5ldzt9DQp7XGYyXGZu
aWxcZmNoYXJzZXQyIFN5bWJvbDt9DQp7XGYzXGZtb2Rlcm5cZmNoYXJzZXQwIENvdXJpZXIgTmV3
O319DQp7XGNvbG9ydGJsXHJlZDBcZ3JlZW4wXGJsdWUwO1xyZWQwXGdyZWVuMFxibHVlMjU1O30N
Clx1YzFccGFyZFxwbGFpblxkZWZ0YWIzNjAgXGYwXGZzMjAgPiAtLS0tLU9yaWdpbmFsIE1lc3Nh
Z2UtLS0tLVxwYXINCj4gRnJvbTogQmxhY2tCb3ggW21haWx0bzpCTEFDS0JPWEBMSVNUUy5PQkVS
T04uQ0hdIE9uIEJlaGFsZiBPZiBCb2IgXHBhcg0KPiBXYWxrZGVuXHBhcg0KPiBTZW50OiBTdW5k
YXksIDE2IFNlcHRlbWJlciAyMDEyIDI6MjUgQU1ccGFyDQo+IFRvOiBCTEFDS0JPWEBMSVNUUy5P
QkVST04uQ0hccGFyDQo+IFN1YmplY3Q6IFJlOiBbQkxBQ0tCT1hdIFNvcnRpbmcgYSBEaWFsb2cu
TGlzdFxwYXINCj4gXHBhcg0KPiA+IEZyb206IEJsYWNrQm94IFttYWlsdG86QkxBQ0tCT1hATElT
VFMuT0JFUk9OLkNIXSBPbiBCZWhhbGYgT2YgXHBhcg0KPiA+IENhbXBiZWxsLCBSb2JlcnQgKFNF
TEVYIEdBTElMRU8sIFVLKVxwYXINCj4gPiBTZW50OiAxNCBTZXB0ZW1iZXIgMjAxMiAxMjowMlxw
YXINCj4gXHBhcg0KPiA+ICBcXFxcICBFdmVuIGEgYnViYmxlIHNvcnQgd291bGQgYmUgbXVjaCBm
YXN0ZXIgaWYgaXQgY291bGQgYmUgcnVuIFxwYXINCj4gPiBpbnNpZGUgdGhlIERpYWxvZyBtb2R1
bGUgIEp1c3QgY3VyaW91cyAtIGlzIHRoZXJlIGFueSBzb3J0aW5nIFxwYXINCj4gPiBhbGdvcml0
aG0gdGhhdFxwYXINCj4gd29ya3MgZWZmZWN0aXZlbHkgd2l0aCBhIHNpbmdsZSBsaW5rZWQgbGlz
dCBzdHJ1Y3R1cmU/XHBhcg0KPiBccGFyDQo+IElmIHRoZXJlIGlzIG9uZSB3aGljaCByZW9yZ2Fu
aXNlcyB0aGUgbGlzdCBpdHNlbGYgSSdkIGd1ZXNzIGl0J3MgXHBhcg0KPiBmaWVuZGlzaGx5IGNv
bXBsaWNhdGVkIGZvciBsaXR0bGUgaWYgYW55IHBlcmZvcm1hbmNlIGdhaW4gb3ZlciBhIFxwYXIN
Cj4gc2ltcGxlIGNvcHkgZnJvbSB0aGUgb3JpZ2luYWwgbGlzdCBpbnRvIGFuIG9yZGVyZWQgbGlz
dC4gSW5zZXJ0aW5nIFxwYXINCj4gaW50byBhbiBvcmRlcmVkIGxpc3QgaXMgcXVpdGUgc3RyYWln
aHRmb3J3YXJkLlxwYXINCj4gXHBhcg0KXHBhcg0KSSB1c3VhbGx5IHVzZSBRdWlja1NvcnQgZm9y
IHRoaXMgc29ydCBvZiB0aGluZy4gSXQgaXMgZmFpcmx5IHNpbXBsZSB0b1xwYXINCmltcGxlbWVu
dCAoaWYgeW91IGZvbGxvdyBhbiBleGlzdGluZyBzb3VyY2UgY29kZSBleGFtcGxlKSBhbmQgaXQg
aGFzIGJlZW5ccGFyDQptb3JlIHRoYW4gZWZmaWNpZW50IGZvciBhbnkgb2YgbXkgYXBwbGljYXRp
b25zIHRvIGRhdGUuIFxwYXINClxwYXINCkFub3RoZXIgcG9zc2libGUgYXBwcm9hY2ggdG8gU3Rl
cGhlbidzIGFwcGxpY2F0aW9uIHdvdWxkIGJlIHRvIGZpcnN0IGNvcHlccGFyDQp0aGUgRGlhbG9n
IGxpc3QgdG8gYSB0ZW1wb3JhcnkgbGlzdCBvZiAqcG9pbnRlcnMqIHRvIHN0cmluZ3Mgc28gdGhh
dCBvbmx5XHBhcg0KdGhlIHBvaW50ZXJzIGFyZSBzaHVmZmxlZCBkdXJpbmcgdGhlIHNvcnQgbm90
IHRoZSBlbnRpcmUgY29udGVudHMgb2YgZWFjaFxwYXINCnN0cmluZy4gQWxzbyB0aGUgQ29tcGFy
ZSBmdW5jdGlvbiB1c2VkIGRvZXMgbm90IG5lZWQgdG8gYWNjZXNzIGV2ZXJ5XHBhcg0KY2hhcmFj
dGVyIGluIGEgcGFpciBvZiBzdHJpbmdzIHRvIGRvIGl0cyBqb2IuIE9uY2UgdGhleSB3ZXJlIHNv
cnRlZCB0aGV5XHBhcg0Kd291bGQgYmUgY29waWVkIGJhY2sgdG8gdGhlIERpYWxvZyBsaXN0Llxw
YXINClxwYXINCk5pa2xhdXMgV2lydGggZGV2b3RlcyA0MCBwYWdlcyB0byB0aGUgZGVzY3JpcHRp
b24sIE9iZXJvbiBzb3VyY2UgY29kZVxwYXINCmV4YW1wbGVzIGFuZCBwZXJmb3JtYW5jZSBhbmFs
eXNpcyBvZiBtYW55IGRpZmZlcmVudCBzb3J0aW5nIG1ldGhvZHMgaW4gaGlzXHBhcg0KIkFsZ29y
aXRobXMgYW5kIERhdGEgU3RydWN0dXJlcyIgYm9vay4gSWYgdGhlcmUgaXMgYSBkaWZmZXJlbnQg
YW5zd2VyIHRvXHBhcg0KUm9iZXJ0J3MgcXVlc3Rpb24gaXQgbWlnaHQgYmUgaW4gdGhlcmUgc29t
ZXdoZXJlLiBUaGUgYm9vayBpcyBhdmFpbGFibGUgYXMgYVxwYXINClBERiBkb3dubG9hZCBmcm9t
OlxwYXINClxwYXINClRoZSBvcmlnaW5hbCAyMDA0IE9iZXJvbiB2ZXJzaW9uOlxwYXINClxwYXIN
Cmh0dHA6Ly93d3cuZXRob2Jlcm9uLmV0aHouY2gvYm9va3MuaHRtbFxwYXINClxwYXINCm9yIHRo
ZSAyMDEyIHZlcnNpb24gd2l0aCBzb21lIGNoYW5nZXMgdGhhdCByZXN1bHRlZCBmcm9tIHRoZSBl
ZmZvcnRzIHRvXHBhcg0KdHJhbnNsYXRlIGl0IGludG8gdG8gUnVzc2lhbjpccGFyDQpccGFyDQpo
dHRwOi8vd3d3Lmluci5hYy5ydS9+aW5mbzIxL0FEZW4vQUQyMDEyLnBkZlxwYXINClxwYXINClJl
Z2FyZHMsXHBhcg0KQ2hyaXNccGFyDQpccGFyDQotLVxwYXINCkNocmlzIEJ1cnJvd3NccGFyDQpB
c3Ryb2JlIHY0LjI6IE9iZXJvbiBmb3IgQVJNIENvcnRleC1NMyBNaWNyb2NvbnRyb2xsZXJzIFxw
YXINCmh0dHA6Ly93d3cuYXN0cm9iZS5jb21ccGFyDQpccGFyDQpccGFyDQotLS0tXHBhcg0KVG8g
dW5zdWJzY3JpYmUsIHNlbmQgYSBtZXNzYWdlIHdpdGggYm9keSAiU0lHTk9GRiBCTEFDS0JPWCIg
dG8gTElTVFNFUlZATElTVFMuT0JFUk9OLkNIXH19AEBMSQ==
----boundary-LibPST-iamunique-1286148116_-_---

Received on Sun Sep 16 2012 - 03:54:52 UTC