HDTenEightyP/NetNews huggingface dataset:
From: krsear02@ulkyvx.louisville.edu (Kendall 'Opusii' Sears)
Subject: Re: Advice needed for fastest sort algorthm
Date: Wed, 11 Nov 1992 18:45:06 GMT
Organization: University of Louisville

> As long as we are comparing all of the sorting algorithms, how about
> shell sort?  Robert Sedgewick's "Algorithms in C" calls it "the method of
> choice for many sorting applications" and further states "In short, if you
> a sorting problem, use the above program [shell sort], then determine whether
> the extra effort required to replace it with a sophisticated method will be
> worthwhile."
> 
> I've ran comparisons for bubble sort, insertion sort, merge sort, quicksort,
> selection sort, and shellsort (assuming 8 compares = 4 moves = one function
> call) and Shellsort outperformed all of the other sorting routines on the
> average.  I tried sizes from 50 to 500000 elements, and I varied the
> percentage sorted between 0 and 100 percent.  When the data was really
> scrambled, quicksort was only slightly faster.  When the data was really
> ordered, shellsort was always first. Try it.  You'll love it.  And best
> of all, "no one has been able to analyze the algorithm" [Sedgewick - page 110].

I wholeheartedly agree here.  The shell sort has performed marvelously for me
in just about any use.  The programs I write for the Unit are mostly sorting,
and I have sorted files ranging from 15 to over 2 million lines using multiple
keys and the shell sort has performed admirably, with the added plus of _not_
being a memory hog (not naming any specific sorts here nudge nudge, wink wink)

There have been times though, when memory use was NOT a constraint (HAH!) that
I have used just about every sorting method (with the notable exception of the
radix sort, too much complexity here) but I keep returning to the shell sort.
(how's that for a run on sentence)

The main reasons _I_ use the shell sort are:
  1) relatively fast.
  2) easy/fast to customize for a particular data set
  3) just about any moron* (even those who graduate from UofL) can figure
     out the algorithm.  * insert your favorite word for "bad programmer" here,
                           the main exception being the ones TEACHING the
                           programmers... sheesh!
  4) uses minimal memory -- especially when one works with this in mind.
     It is amazing what one can accomplish in that d*mn 64K data segment
     limit imposed by the 8088 series family when one really tries.

and most important

  5) Coding the thing from scratch won't totally fry one's brain when in a
     hurry ("I need this data analyzed... yesterday")

Kendall.

-- 

   Kendall Sears                   KRSEAR02@ULKYVX.bitnet
   Programmer                             ///
   Child Development Unit                /// Amiga
   Department of Pediatrics          \\\/// Currently running AmigaOS 2.04
   University of Louisville           \XX/ And Supporting Unix Sys V Rev 4.
---------------------------------------------------------------------------
"Numbness is bliss... I can't feel a thing." -me.

Newsgroups: rec.games.programmer
From: morley@camins.camosun.bc.ca
Subject: Re: Buffer-> VGA Video Mem (again!)
Organization: Camosun College
Date: Wed, 11 Nov 1992 00:12:56 GMT

In article <BxInLB.7CA@uxa.ecn.bgu.edu>, mucds@uxa.ecn.bgu.edu (Corey D. Stinson) writes:
>    I have posted this question in several different forms, unfortunely
> my question was rather complicated or unclear as I never got any
> answers which worked.  I posted some code I had written and received
> many helpful replies on a gramattical error I made but everyone seemed
> to overlook the question at hand.  I have two simple problems.
> 
>   I need to assign a pointer to the beginning of VGA (Mode 13h) video
> memory.  Then, I need two know how to correctly increment this
> pointer through the 0 - 64000 offset range of the VGA video buffer.
> I assume that the pointer will have to be of type char since I am
> loading byte-by-byte into video memory.  Please respond via email
> with any suggestions.  Thanx *much* in advance for any help!

A simple clear screen routine in Borland C...

void Clear( int color )
{
   unsigned  i = 64000;
   char far* VidMem = (char far*) 0xa0000000L;

   while( i-- )
      *VidMem++ = color;
}

A simple putpixel routine...

void PutPixel( int x, int y, int color )
{
   char far* VidMem = (char far*) 0xa0000000L;

   *(VidMem + x + y * 320) = color;
}

There... simple, eh?

MARK
morley@camins.camosun.bc.ca
From: jas37876@uxa.cso.uiuc.edu (John A. Slagel)
Newsgroups: rec.games.programmer
Subject: Re: Redefining Characters in Text Mode
Date: 11 Nov 92 15:26:07 GMT
Organization: University of Illinois at Urbana


    I don't have the code typed in, but the book "Programmer's Guide to
    PC & PS/2 Video Systems" by Microsoft Press has examples for doing
    that on EGA and VGA.  You might want to try to find a copy of it.
    (Mine was $27.95)

-- 
------------------------------------------------------------------------
  John A. Slagel, email: jas37876@uxa.cso.uiuc.edu
Newsgroups: rec.games.programmer
From: u519876@csi.UOttawa.CA (U. N. derGrad)
Subject: Card Shuffling
Organization: Dept. of Computer Science, University of Ottawa
Date: Fri, 6 Nov 92 16:30:08 GMT

Hi there,

I'm looking for a quick and simple algorithm for shuffling a normal
deck of cards.  A joker or two could also be added to the deck (I'm 
making a poker game).

Any suggestions?  Programming language is C, on a Unix station.

Much appreciated,

--
Kevin Coughlan
u519876@csi.uottawa.ca
--

Newsgroups: rec.games.programmer
From: fxmlk@acad3.alaska.edu (KIENENBERGER MIKE L)
Subject: Re: Advice needed for fastest sort algorthm
News-Software: VAX/VMS VNEWS 1.41.UAC
Organization: University of Alaska - Fairbanks
Date: Wed, 11 Nov 1992 16:24:00 GMT

In article <6759@news.duke.edu>, kds@phy.duke.edu (Stokes Kevin) writes...
>  I am well along in a new 3D game engine, and I need some advice
>about sorting algorthms.  My past game, Corncob 3D, used a bubble sort
>to sort all the objects from farthest to closest to the observer.
>  This method seemed ok, because in a flight simulator, the objects are
>generally very sparse, and from frame to frame, there should be few changes
>in the order of objects.
>  This new project has objects much closer to the observer, and I fear
>there may be significant changes in the list order between every sort.
>Which sorting algorthm is the most time efficient?
and thus starts the sorting thread.


Sorting depends on the randomness of the data and the size of the data.
Furthermore,  how "good" a sorting algorithm really is depends on the
relative speeds of a compare operation, a move operation, and a function call.

As long as we are comparing all of the sorting algorithms, how about
shell sort?  Robert Sedgewick's "Algorithms in C" calls it "the method of
choice for many sorting applications" and further states "In short, if you
a sorting problem, use the above program [shell sort], then determine whether
the extra effort required to replace it with a sophisticated method will be
worthwhile."

I've ran comparisons for bubble sort, insertion sort, merge sort, quicksort,
selection sort, and shellsort (assuming 8 compares = 4 moves = one function
call) and Shellsort outperformed all of the other sorting routines on the
average.  I tried sizes from 50 to 500000 elements, and I varied the
percentage sorted between 0 and 100 percent.  When the data was really
scrambled, quicksort was only slightly faster.  When the data was really
ordered, shellsort was always first. Try it.  You'll love it.  And best
of all, "no one has been able to analyze the algorithm" [Sedgewick - page 110].

(I used the NeXT computer's "SortingInAction" to run the comparisons.  It's
an excellent program (source provided), and can be found in the
/NeXTDevelopers/Examples directory.  As far as I'm concerned, I've never seen
a better way to experimentally test sorting algorithms, theoretical math be
hanged!)

=============================================================================
-Mike Kienenberger                       FXMLK@ALASKA           (BITNet)
 Academic Computing                      FXMLK@acad3.alaska.edu (Internet)
 University of Alaska-Fairbanks
 "I'm a computer programmer....<link><link><kludge><kludge> say-no-more!"
Newsgroups: rec.games.programmer
From: pfratar@watserv1.uwaterloo.ca (Paul Frattaroli [DCS])
Subject: Re: The Yak is Back...
Organization: University of Waterloo
Date: Thu, 5 Nov 1992 16:29:22 GMT

In article <1992Nov4.214158.17392@mnemosyne.cs.du.edu> vputz@nyx.cs.du.edu (Victor Putz) writes:

[stuff deleted]

>Secondly: I would like some information on name generation for
>role-playing games.  Anyone have references/ideas/algorithms/code?

You might want to try rec.games.frp

I haven't read the group in a long time but I remember a number of
name generators being posted there.

>-->Vputz
>

....Paul

-- 
         Paul "vi joe" Frattaroli - Department of Computing Services
          University of Waterloo  Waterloo, Ontario Canada  N2L-3G1
     < pfratar@fpg.UWaterloo.CA >       < pfratar@watserv1.UWaterloo.CA >
Newsgroups: rec.games.programmer
From: woodam@aix.rpi.edu (Matthew G. Woodard)
Subject: Bit mapping or other graphics info wanted....
Organization: Rensselaer Polytechnic Institute, Troy, NY
Date: Thu, 12 Nov 1992 21:00:33 GMT

Hello out there!  I've just begun to program games, and I have a few
ideas of where I want to start, but first I'd like some information.

Unfortunately, I don't have a extremely strong background in graphics
programming, but I am already well versed in most other aspects of using
a computer for creating applications.  My main language options will be
C and C++, as well a little assembly language programming.

The information I'm after is how to write to VGA (13h mode) memory, and 
possibly how to read/write bitmapped (or other formats) images to disk
and memory.  Even if the information is a pointer to someplace where I
can find some useful info, I'll be happy.  (I am no stranger to
plodding through a text on computers.  If you have any good books
you'd like to recommend, I'm all ears.)

					Thanks,
				Matt Woodard (woodam@aix.rpi.edu)
From: warwick@cs.uq.oz.au (Warwick Allison)
Newsgroups: rec.games.programmer
Subject: Re: Advice needed for fastest sort algorthm
Date: 11 Nov 92 00:31:18 GMT
Reply-To: warwick@cs.uq.oz.au

dstampe@psych.toronto.edu (Dave Stampe) writes:

>If you are sorting 6 or less items, I'd still use something like an
>insert or bubble sort, because the overhead is less (no recursion).

Groan.  Recursion costs insignificantly more than iteration for most
applications, more for some, less for others.  Will ASM hackers ever
know anything?  I suppose you'll inline the comparison too?  Write the
whole thing as a macro perhaps?  Come one!  The time taken to draw
up your sorted objects will TOTALLY DWARF you sorting time.


--
Warwick
--
  _-_|\      warwick@cs.uq.oz.au            /Disclaimer:
 /     * <-- Computer Science Department,  /  
 \_.-._/     University of Queensland,    /   C references are NULL && void*
      v      Brisbane, Australia.        /  
Newsgroups: rec.games.programmer
From: morley@camins.camosun.bc.ca
Subject: Number of unique tiles in a game?
Organization: Camosun College
Date: Thu, 12 Nov 1992 18:28:07 GMT

I'm kinda playing around with a tile-based game and I gotta question for
you people...  How many unique tiles are used in a given game?  For example,
in the Ultima series, does anyone know how many unique graphic tiles were
used in each game in the series?  How about other games?  If I use a single
byte to index a tile then I can have a maximum of 256 tiles.  Is this
enough or should I use a 16 bit word (which is way more than enough)?
Obviously I'm concerned about saving as much disk space and memory as
possible for the other elements of the game.  

Also, it seems to me that 16x16 pixel tiles are just right for this kind
of game.  What other common sizes are used?

Thanks!

MARK
morley@camins.camosun.bc.ca

Newsgroups: rec.games.programmer
From: scd@cs.brown.edu (Steven C. Dollins)
Subject: Re: Advice needed for fastest sort algorthm
Organization: Dept. of Computer Science, Brown University
	<1992Nov8.012628.23338@menudo.uh.edu>
Date: Sun, 8 Nov 1992 03:37:29 GMT

In article <1992Nov8.012628.23338@menudo.uh.edu> libh@Jane.UH.EDU writes:

     The bubble sort takes N! (# factorial) steps, rather than N*N
   steps.  A BIG difference.  But as pointed out, the quicksort is the
   easiest to implement since it is in C libraries.  Why reinvent the
   wheel.  If that isn't quick enough then I would check out Knuth's 'Art
   of Programming' Vol. 3 since it is pretty much only about sorting.

   [Obnoxiously wide .sig deleted]

The bubble sort takes, in the asymptotic limit, 1/2 N^2 time, which is
nowhere NEAR N!.  Where on earth did you get that idea?

Quick sort is O(n log n) on average, O(n^2) in the worst case.  With a
good randomized quick sort, the worst case will be extremely unlikely.

					- Steven Dollins
Brown Computer Graphics Group		scd@cs.brown.edu
--

"This could only be USENET.  Nowhere else in the known universe
would you find such a mind-boggling ratio of ill-informed
conjecture to actual fact."
				-- parghi@cs.uiuc.edu (Amit Parghi)
From: HeroSoftware@cup.portal.com (Bits of Magic)
Newsgroups: rec.games.programmer
Subject: Re: Card Shuffling
Date: Mon,  9 Nov 92 23:42:51 PST
Organization: The Portal System (TM)

A quick and dirty way is:

	Card	deck[DECKSIZE];

	for (i=0;i<DECKSIZE;i++)
		deck[i] = i;

	for (i=0;i<SWAPS;i++) {
		firstcard = random(DECKSIZE);
		secondcard = random(DECKSIZE);
		temp = deck[firstcard];
		deck[firstcard] = deck[secondcard];
		deck[secondcard] = temp;
	}

where your Card values run from 0 to DECKSIZE (say 52 or 54), random(N)
returns a random integer in the range 0 to N-1 (inclusive), and SWAPS
is (as I recall from a project many years ago) at least about 100.

Basically it's just:
	swap two randomly selected cards in the deck
	repeat as needed

hope it helps,
	evan
From: roberts@angelo.amd.com (Dave Roberts)
Newsgroups: rec.games.programmer
Subject: Re: Advice needed for fastest sort algorthm
Date: 10 Nov 92 18:55:27 GMT
Article-I.D.: amd.1992Nov10.185527.3584
Organization: Advanced Micro Devices, Santa Clara, CA

In article <1992Nov8.012628.23338@menudo.uh.edu> libh@Jane.UH.EDU writes:
>In article <BxD5pt.DyI@news.cso.uiuc.edu>, jas37876@uxa.cso.uiuc.edu (John A. Slagel) writes:
>>   Definately the quick sort.  Its even built into ANSI C specs, so it
>>   should be easy to implement.  Look up quicksort in your C manual. If
>>   I remember right, bubble sort works in O(n*n) and quicksort works in
>>   O(n*log n).
>>
>>   In other words, if you're sorting n objects, QuickSort takes "on the Order
>>   of" n*log n steps, while bubble sort takes "on the order of" n*n steps.
>>
>  The bubble sort takes N! (# factorial) steps, rather than N*N steps.  A BIG
>difference.  But as pointed out, the quicksort is the easiest to implement
>since it is in C libraries.  Why reinvent the wheel.  If that isn't quick
>enough then I would check out Knuth's 'Art of Programming' Vol. 3 since it is
>pretty much only about sorting.

Ack!!! People, remember that bubble sort has a *worst* case time of
n!.  It can be quite fast if most things are sorted.

Also, remember that all this n! vs. n*log n stuff if the asymtotic
behavior of the algorithm.  Meaning, this is the way the time vs. n
curve "looks".  There are also constants that are associated with
these curves which may make a "poorer" algorithm (with respect to its
O-notation) much faster than a "better" algorithm, ON YOUR DATA SET.

For instance, size has a lot to do with things.  If n is small, it may
be better to use another algorithm.  An example of this is that many
quick sorts end up using an insertion or other sort in the depths of
the sort when they have divided the data set down to a sufficiently
small number of elements.

Another example.  There is an algorithm for multiplying large integers
together that is O(n^1.xxx) where xxx is something I can't remember.
The naive algorithm is O(n^2).  For any integer size less than
something like 256 bits, it's usually better to use the naive approach
because the "better" approach has a huge constant in front of it that
isn't shown in the O-notation.  At small values of n, the naive
approach is better, but crosses over at larger n as the n^2
characteristic swamps whatever constant the better algorithm has.

So, in summary, it's never a clear case of O(n*log n) is always better
than something O(n*n) or O(n!).  It really depends on what n is and
what sort of constants aren't shown in the O-notation for the "better"
algorithms.  It also depends on your data set.  Some things that are
O(n!) in the worst case degenerate down to something O(n) if you know
something about the data that is being operated on.

Dave Roberts
Advanced Micro Devices, Inc.
Network Products Division
david.roberts@amd.com
Newsgroups: rec.games.programmer
From: asu@panther4.panther.mot.com (Russ Trotter)
Subject: Re: Advice needed for fastest sort algorthm
Organization: Motorola Panther Project, Chandler, AZ
Date: Wed, 11 Nov 1992 16:10:52 GMT

I hate to jump on this seemingly runaway train but.... 

In one of my classes, I remember the teacher saying that it
had been proven that O(n log n) was the best one could do
for _comparison_ based sorting...  Is this a more correct assertion?

I don't know much (at all :) ) about Radix sort  (only how to spell it :) )
so I can't be sure if it disproves the statement above.


I've seen posts flying back and forth about this and quite frankly
I'm getting a bit confused...

Russ
asu@panther.mot.com
Newsgroups: rec.games.programmer
From: ematias@csri.toronto.edu (Ummm... me!)
Subject: Re: Software Pinball Machine
Organization: CSRI, University of Toronto
Date: 7 Nov 92 00:53:09 GMT

In article <6NOV199208134420@acad3.alaska.edu> fxmlk@acad3.alaska.edu (KIENENBERGER MIKE L) writes:
>
>Yep. This was the "Pinball Construction Set" by (as you said) Bill Budge.
>
>The other really awe-inspiring Apple II pinball game was "Night Mission
>Pinball."  This game had a set playing field, but it offered zillions of
>configuration options.  Truely amazing.
>
>Taking a look at both of these games is definitely a step in the right
>direction for the design of a Software Pinball Machine. 

   All this talk of good pinball machines brings to mind the recent release
of a *superb* game by Amtex called "Tristan Pinball".  It was originally
done on the Macintosh, but has since been ported over to the IBM market.
It runs in 640x480x256 SVGA (in fact it looks like they used the exact same
artwork as for the Mac version), and all of the sounds are digitized
samples.  It requires at least a 386, but that's probably due more to the
graphics-intensive stuff than to the physical calculations involved.
   As for the realism of the action, it is *very* good!  The ball's motion
seems to take almost everything into account, and it bounces off of
boundaries very cleanly.

-Mark-
Organization: Junior, Math/Computer Science, Carnegie Mellon, Pittsburgh, PA
Newsgroups: rec.games.programmer
Date: Tue, 10 Nov 1992 05:36:52 -0500 
From: Court Demas <court+@CMU.EDU>
Subject: Re: Advice needed for fastest sort algorthm


Well, quicksort is generally the fastest general algorithm on large data sets.
But, if you are dealing with only a small number of items, or especially a list
which is almost sorted already, something like an insertion sort might be
better.  Most O(nlogn) algorithms have a bit too much overhead on small lists,
and insertion sort is one of the simplest and fastest O(n^2) sorts.

-court
Newsgroups: rec.games.programmer
From: wyman@rtsg.mot.com (Mark S. Wyman)
Subject: Re: Fast compression
Organization: Motorola Inc., Cellular Infrastructure Group
Distribution: na
Date: Thu, 12 Nov 1992 15:44:07 GMT

gardabr@unix1 (Gard Eggesbo Abrahamsen) writes:

>Chris (cbusch@ub.d.umn.edu) wrote:
>: Hello
>: 	What is the fastest compression technique?

>The fastest compression techique is probably coding in this form:
>if bit 7 is cleared, the following n bytes are to be read directly.
>if bit 7 is set, the copy the next byte n times.
>This is FAST but a really crappy packing, and you REALLY shouldn't use it.

>: Chris Busch   CBUSCH@ub.d.umn.edu

Look at the latest C Users Journal mag.  It has a compression algo that is
combination run length encoding and pattern searching.  Seems quite fast.

Mark Wyman
Newsgroups: rec.games.programmer
From: zklf0b@gs144.uucp (Fergason)
Newsgroups: rec.games.programmer
Subject: Re: Fast compression
Keywords: n
Date: 10 Nov 92 14:37:50 GMT
Organization: Amoco Production


In article <1992Nov10.122535.27889@ugle.unit.no> gardabr@unix1 (Gard Eggesbo Abrahamsen) writes:
>Chris (cbusch@ub.d.umn.edu) wrote:
>: Hello
>: 	What is the fastest compression technique?
>
>The fastest compression techique is probably coding in this form:
>if bit 7 is cleared, the following n bytes are to be read directly.
>if bit 7 is set, the copy the next byte n times.
>This is FAST but a really crappy packing, and you REALLY shouldn't use it.
>

this sounds like a run-length compression technique.  it is usually pretty 
good with large graphic images that have lots of dead space.  using 16bit
ints, a 64K blank image could compress to 3 words.  of course, that is best
case.  and it is fast.

Kelly