hello everybody my project is based on 8031 microcontroller and using keil development tools . i am storing some 1000 strings(each string has eight letters) on a atmel serial flash.all the strings will arrive to the system via rs232 serial communication.i am storing all the strings serially. but searching for a particular string is very very slow.can somebody tell me which sorting and searching is good and fast.also i have very less on chip RAM . so the sorting should be done outside the system and then downloaded via rs232. thanking you
tell me which sorting and searching is good and fast I don't know what's good, but I know that the fast ones are binary search: http://www.wikipedia.org/wiki/Binary_search and quick sort (as in qsort() function in standard C): http://www.gamedev.net/reference/articles/article1073.asp You defenitely want to store the strings as a sorted array and use binary search. If you'll be sorting the strings in a PC, you probably should go for something more simple than quick sort, since even the slowest sort algorithm in the world will sort 1000 short strings on a PC in no time. - mike
Actually, if I were sorting externally, I'd just go for qsort() because it's already in the standard C libary. Why write your own sort function? No matter how simple to write, it can't be simpler than just using one that already exists. See this thread where David Lin has a very similar problem: http://www.keil.com/forum/docs/thread3350.asp http://www.wikipedia.org/wiki/Search_algorithm If you have a fixed table, sorted outside your system, then I'd second the recommendation for a binary search. It's easy to code, and simple. For reasonably small amounts of data (and small processors!), the complexity of the code matters as well as just the "big-O" asymptotic performance.