Challenge: Internal (memory) sort - Printable Version +- Qbasicnews.com (http://qbasicnews.com/newforum) +-- Forum: QbasicNews.Com (http://qbasicnews.com/newforum/forum-3.html) +--- Forum: Challenges (http://qbasicnews.com/newforum/forum-10.html) +--- Thread: Challenge: Internal (memory) sort (/thread-1547.html) |
Challenge: Internal (memory) sort - Moneo - 07-20-2003 INTERNAL (MEMORY) SORT PROGRAM: PURPOSE: Write a program which reads a file into memory, performs an internal sort of the records, and writes the sorted records to an output file. GIVEN: * The input file will be called SORTIN, and is an ASCII text file. * Each input record contains 4 numeric bytes, which is the key. * The keys are always 4 bytes, strictly numeric, unsigned with leading zeros. * There may be records with duplicate keys. * The keys can have values from 0000 to 9999. * The keys of the input record are in random order. * We will establish a maximum of 100 records on the input file so that you can safely store them all in memory. * The program should work even if there is only 1 record on the input file. * An input file with no records is an error. * For the internal sort logic, you may chose any technique of your liking: bubble, cascade, tournament, sift, quicksort, direct address, etc. However, invoking a sort function from a library, or shelling out to a file sort program, is not allowed. * The sort must be ascending. * The sorted output file will be called SORTOUT. Heré's a chance to get your favorite sorting methods out of the closet. Note: Speed is not a consideration. Simplicity is encouraged. Have fun! ***** Challenge: Internal (memory) sort - Moneo - 07-25-2003 Hey guys, I was really surprised that nobody submitted a solution to this challenge. I can't believe that none of you have a sort routine or two stashed away. The famous bubble sort can be implemented in 9 lines of code, and a selection sort can be done in 6. That's not a lot of code to ask. I'm going to post my solution. It isn't exactly a sort, but takes unsorted records in and produces sorted records out. The trick is that the input records are stored in an array using the record key as a subscript. Actually they're not stored, the corresponding subscript position of the array is incremented by one. This enables the progrm to know when there are multiple records with the same key. I know you can't always use this method of "sorting", but when you can it runs about as fast as a quicksort, and much simpler. It is however, memory intensive. Here's the code to satisfy this chjallenge: Code: defint a-z ***** Challenge: Internal (memory) sort - Sterling Christensen - 07-25-2003 Quote:Hey guys, I was really surprised that nobody submitted a solution to this challenge. I can't believe that none of you have a sort routine or two stashed away.It has too many constraints and not enough room for creativity. I mean, sure it's a good programming exercise, but it's not very interesting. Challenge: Internal (memory) sort - Moneo - 07-25-2003 Sterling, I really appreciate your feedback, but I disagree. The "constraints", as you say, are in precise definition of the input and output, in order that everyone gets to play by the same rules. However, the internal sort algorithm that you chose is entirely open to your own creativity. Look at the solution which I posted. It is totally my own idea and creation. I respect you rights of not finding sorts interesting. Lot's of people in the forum are really into games. I personally don't find them interesting, although I recognize that they can be challenging. To each his own. ***** Challenge: Internal (memory) sort - toonski84 - 07-25-2003 You can come up with a creative challenge without it being games. Challenge: Internal (memory) sort - Sterling Christensen - 07-25-2003 Sorry, I don't mean to be a spoil-sport. And yeah, I guess a little variety is good - games and graphics demo can get old. Challenge: Internal (memory) sort - Moneo - 07-25-2003 Quote:You can come up with a creative challenge without it being games.Toonski, No one said anything to the contrary. ***** my 2 cents - Meg - 07-26-2003 I think it's wonderful that Moneo is posting challenges. I didn't happen to find this one particularly rivetting, but some of the other ones he's posted have been fun So far my favorite challenge has been the flood filler challenge, because it left a lot of room for creativity, but still had very specific things it had to do. *peace* Meg. Challenge: Internal (memory) sort - Moneo - 07-26-2003 Meg, Thanks for your vote of confidence. All my posts are based on programming experiences that I've had, and I'm quickly running out of things that could be converted to an interesting challenge. Challenges can suffer a sudden death by the following: 1) Someone posts a very good solution, and everyone else is scared off, for some reason. 2) Someone starts an unrelated discussion in the thread of a challenge, and the challenge dies of contamination. Assuming you get responses/solutions to your challenge, it becomes a time-consuming task of compiling and testing the submitted solutions. I've tried religiously to do this and offer good feedback. ***** |