Re: KBH Integer Sort
- From: "KBH" <KBH@xxxxxxxxxxx>
- Date: Thu, 7 Sep 2006 13:09:00 -0400
I propagate a sort and call it the KBH Integer Sort. Of course "integer"
refers to whole numbers and not just to digits.
http://www.kbhscape.com/sort.htm
"Integer" refers to progamming language integer-definition but is not
limited to programming language integer ranges except when computational.
Here is code that just puts random numbers between 0 and 999999 into an
a-array:
lw:= 0;
hg:= 999999;
For ii:= lw To hg Do
Begin
a[ii]:= Random(1000000);
End;
Here is code that puts information about the a-array data into the c-array
such that the c-array contains a sorted logic of the a-array:
For i:= lw To hg Do
Begin
c[a[i]]:= c[a[i]] + 1;
End;
And that c-array code alone is the fundamental sort operation.
Here is code that demonstrates logical use of the finished c-array:
For t:= lw To hg Do
Begin
If (c[t] <> 0) Then
Begin
WriteLn(' [ The first sorted number is: ', t:10, ' ]');
WriteLn(' [ There are ', c[t], ' of these numbers consecutive ]');
Break;
End;
End;
Now suppose the a-array data is wide-spaced and a dynamic c-array
declaration is wanted. Here is code that determines the smallest and
largest values of the a-array and thus the smallest and largest c-array
subscripts that are needed:
Begin
m:= lw;
n:= hg;
hg:= a[0];
lw:= a[0];
For k:= m + 1 To n Do
Begin
If (a[k] > hg) Then hg:= a[k];
If (a[k] < lw) Then lw:= a[k];
End;
End;
Finally, whole number data that is larger than programming language
integers can be scaled and truncated to integer declaration. Small
programming language float numbers can be scaled and truncated to
larger integer declarations with some loss of precision. And large
programming language float numbers can be handled with related sorts of
parts of the float numbers scaled and truncated to integer declarations.
Whole number data that is larger than programming lanaguage integers can be
translated and truncated to integer declaration ranges. Other situations can
involve scaling and truncating.
Basically, a one-pass sort is possible with integer data if there is a
matching memory structure to the data memory structure.
Oh, the NIST calls a pigeonhole sort a two-pass sort. But suppose the second
pass is from (the KBH c-array) memory structure to hard-copy. In that case
all sorts have an additional pass to make a hard copy.
Other sources for pigeonhole sort also advocate the need for a second pass
but some of those sources do show the simple implementation of the sort.
So the premise must be that un-used locations of the memory structure are
not allowed and thus another output to memory structure is required. I leave
the c-array as it is and just require a small amount of logic for its use...
.
- References:
- KBH Integer Sort
- From: KBH
- KBH Integer Sort
- Prev by Date: Re: An uncountable countable set
- Next by Date: Re: Am I a crank?
- Previous by thread: Re: KBH Integer Sort
- Next by thread: request
- Index(es):
Relevant Pages
|
