Consider the following data:

Couple of hundred text strings (300 at the very very most, 100 being the norm) where each is maximum length of 20 characters.

Need to sort this list into ascending order.

Easy? Yes. However, here's the stinger:

The sort must be done with as minimum amount of memory as possible (talking bytes here, as in absolute maximum of 100 bytes for RAM, and 300 bytes of write-once-per-sort storage) - the above memory (where the strings are located) may be modified a maximum of the number of items there, but can be read as many times as required. Speed is not an issue.

Only solution found as yet is to simply go through the list looking for all the 'A's and place them into a sequential table. Then do the 'B's followed by the 'C's etc. 2600 reads later we are done. Only one byte write is used per item found. Not a very good sort as it's only sorted on the first letter, but I've not thought of a better method as of yet.

The reason for the limitations is that this is to go into Microcontroller (ie. very limited ram) with a eeprom to hold the text strings, and the eeprom can be read any number of times, but can only be written to a finite number of times.

So, any ideas?

So, is there a limitation on the size of the code that is used? Must it also be in the 100 bytes of RAM?

dELTA

Is there any problem with the following?:

First, define a function to compare two strings cmp_str(str1, str2), normal simple compare function, returns -1, 0, 1.

Then simply go through the list of N strings N times, each time finding the "smallest" string that is left (i.e. the first in the sorted result), by using the function mentioned above. Everytime, copy the found string to the final destination and overwrite it in the source position (e.g. write a zero on the first character if it's null-terminated). This only requires a couple of pointers in the RAM, nothing more.

This will get you a perfect sort (not only first letters), and it will execute in O(N^2) (i.e. quadratic time complexity), only writing each string once in the target memory and overwriting the first character of each string once in the source memory.

Good solution? Or did I misunderstand anything?

dELTA

Well, I can't see anything wrong with that myself. Thanks for that. Code space isn't a problem (Kb's worth it), it's just ram that's at an extreme premium. Think I may add a bitmap (in std ram) to the code as reading from the memory where the strings are stored is very slow (hundreds of clock cycles), and this will tell me the strings I've already stored in the destination. Using 1 bit for each entry shouldn't take up too much space - about 13 bytes for 100 entries. I'll have to see if it'll fit.

Although it'll be ok as it is, any ideas for making it faster? Code space certainly isn't a problem.

Don't forget that the 100 bytes of ram is simple RAM that is fairly quick (few clock cycles) whilst there is also 300 bytes of external ram, but this is a lot slower (hundred of clock cycles) and can only be written a finite number of times.

Sure, there are lots of ways to make it faster, I just concentrated on a simple example, and did not care about speed at all since you said it did not matter.


Good way to make it much faster:

Create a pointer-array in the ram, referencing all the strings (as long as the ram is enough for the number of pointers anyway, otherwise you're screwed). You can optimize the space it will take by not using real pointers, but indexes from the start of the string buffer. This should make it possible to only use 16 bits per string "pointer" most likely. Then use e.g. the quicksort algorithm (or any other fast and non-memory-consuming algorithm) on this array of pointers. Finally use the sorted array to dump all the strings after each other to the target memory, all sorted. This should get you an O(n*log(n)) time complexity (well, quicksort has actually an O(n^2) worst case complexity, but an O(n*log(n)) average complexity, but there are algorithms having a O(n*log(n)) worst case complexity too).

dELTA

Just curious... What microcontroller are we talking about?! PIC? Atmel?

Anyway sorting algo's are easily found on the web.. no point in reinventing the wheel!

As you see in my last post, I did not reinvent the wheel. I just adapted existing algorithms to an implementation limited by the certain premises described. My suggestion in the first post was just a very simple example to see if I had understood the premises correctly, and also it was much easier to describe than e.g. the quicksort algorithm.

dELTA

The microcontroller I'm using is the ST72C314J4. This is a 8-bit 16kb Micro with 512 bytes ram, running at 14.7456Mhz. Some of that ram is used by the stack, and a lot of the rest is used by my program. I have about 120 bytes left to play with and wish to an efficient sort algorithm with it.

The text for the strings is stored in an external eeprom (as it's the only place big enough where I can store them). I talk to this eeprom by standard I2C communications.

Sort algorithm's on the net are numerous and very easily to find. However, they are not suited to this application as I really don't want to do any more writes to the chip than necessary, so the strings must stay where they currently are and not be overwritten.

So, that means I can only use index's for the strings. There will never be more than 255 strings, so a single byte is enough to store this index. This also means a lookup table is easy enough to store.

I've converted dELTA's first suggestion into a lookup table method by searching for the smallest string, and then placing it's index into the lookup table, and continuing until there is no more strings left to search.

I don't think the second suggestion would work, as even with 8-bit indexes, a 250-string table would require 250 bytes of ram, which I don't have.

By using a bitmap array however on the first suggestion reduces the number of searches by approximately half, as each time through the loop another item is removed from it. Using this technique, it will sort 90 strings in just under 20 seconds - which isn't too bad (hence the "executing speed not that important" in my original message). However, any ideas on how to reduce this time further are welcome.

Didn't know that one.. made a disassembler for a ST20 a while back, but guess it has a different instruction set.

Anyway.. it sounds like the external eeprom bandwidth is your biggest concern..

Does your application (more precisely, your strings) lend themselves to compression?!

e.g. very simple.. if all your strings are A->Z (uppercase), you only need 4-bits to store a letter, so you can have 2 chars in 1 byte, doubling your bandwidth to your external storage.

(static) huffman compression probably wouldn't work here, as you don't have the memory for the tables.

Unfortunately, the string table contains A-Z, a-z, 0-9, as well as spaces, underscores, and hyphens. These can not be modified as the strings are written to a display later.