Qbasicnews.com
August 25, 2019, 11:51:51 PM *
Welcome, Guest. Please login or register.

Login with username, password and session length
News: Back to Qbasicnews.com | QB Online Help | FAQ | Chat | All Basic Code | QB Knowledge Base
 
   Home   Help Search Login Register  
Pages: [1]
  Print  
Author Topic: Challenge: Internal (memory) sort  (Read 3765 times)
Moneo
Na_th_an
*****
Posts: 1971


« on: July 19, 2003, 07:11:19 PM »

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!
*****
Logged
Moneo
Na_th_an
*****
Posts: 1971


« Reply #1 on: July 24, 2003, 07:20:00 PM »

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
open "sortin" for input as #1
open "sortout" for output as #2

dim t(0 to 9999)

do while not eof(1)
   line input #1,d$
   v=val(d$)               'Get the value of the key to use as a subscript
   t(v)=t(v)+1             ' Increment corresponding position of array
loop

for v=0 to 9999          'Check all positions of array, ascending
    cntv=t(v)
    do while cntv>0      'Output as many records as the count
       print #2,right$("0000"+ltrim$(str$(v)),4)
       cntv=cntv-1
    loop
next v
system

Simple, no?
*****
Logged
Sterling Christensen
Na_th_an
*****
Posts: 1328


« Reply #2 on: July 24, 2003, 08:28:47 PM »

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.
Logged
Moneo
Na_th_an
*****
Posts: 1971


« Reply #3 on: July 24, 2003, 10:20:19 PM »

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.
*****
Logged
toonski84
__/--\__
*****
Posts: 2567



« Reply #4 on: July 24, 2003, 11:58:56 PM »

You can come up with a creative challenge without it being games.
Logged

i]"I know what you're thinking. Did he fire six shots or only five? Well, to tell you the truth, in all this excitement, I've kinda lost track myself. But being as this is a .44 Magnum ... you've got to ask yourself one question: 'Do I feel lucky?' Well, do ya punk?"[/i] - Dirty Harry
Sterling Christensen
Na_th_an
*****
Posts: 1328


« Reply #5 on: July 25, 2003, 02:04:10 AM »

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.
Logged
Moneo
Na_th_an
*****
Posts: 1971


« Reply #6 on: July 25, 2003, 03:59:55 PM »

Quote from: "toonski84"
You can come up with a creative challenge without it being games.

Toonski, No one said anything to the contrary.
*****
Logged
Meg
Ancient QBer
****
Posts: 483


« Reply #7 on: July 25, 2003, 06:41:15 PM »

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 Smiley  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.
Logged
Moneo
Na_th_an
*****
Posts: 1971


« Reply #8 on: July 25, 2003, 09:56:55 PM »

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.
*****
Logged
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!