Posts: 357
Threads: 118
Joined: Oct 2004
Code: declare sub radix(digit as integer, a() as integer, outpt() as integer, size as integer)
declare sub radixsort(a() as integer, outpt() as integer, size as integer)
'********Test Radix sort**************
redim testarray(13)
redim outputarray(13)
testarray(0) = 1
testarray(1) = 5
testarray(2) = 55
testarray(3) = 57
testarray(4) = 128
testarray(5) = 157
testarray(6) = 152
testarray(7) = 9
testarray(9) = 25
testarray(10) = 22
testarray(11) = 166
testarray(12) = 167
testarray(13) = 168
radixsort testarray(0), outputarray(0), 13
for i = 0 to 13
print outputarray(i)
next
sleep
end
sub radixsort(a() as integer, outpt() as integer, size as integer)
radix 10, a(0), outpt(0), size
'the longest an integer can be is 10 digits
End Sub
sub radix(digit as integer, a() as integer, outpt() as integer, size as integer)
If digit < 0 or size <= 0 Then exit sub 'base case
DIM temp(9, size) as integer
Dim stacktop(9) as integer
FOR i = 0 TO size
b = (a(i) \ (10 ^ digit)) mod 10 'get the digit-th place
temp(b, stacktop(b)) = a(i)
stacktop(b) = stacktop(b) + 1
Next
FOr i = 0 to 9
radix digit - 1, temp(0, i), temp(0, i), stacktop(i)
next
top = 0
For i = 0 To 9
For j = 0 To size
If temp(i, j) Then
outpt(top) = temp(i,j)
top = top + 1
end if
next
next
End Sub
I can't get this thing to work right. Its supposed to be a radix sort without Linked Lists, but I just can't get it to sort correctly, it also for some reason copies the value 22.[/code]
f you play a Microsoft CD backwards you can hear demonic voices. The scary part is that if you play it forwards it installs Windows.
Posts: 6,419
Threads: 74
Joined: Mar 2002
Not really related to your error, but just personal advice.
If you use encapsulation, you'll have an easier task plus reusable code.
You need a linked list for a radix sort, right? You can't use a "real" linked list for this experiment, you have to use arrays. Well, just create a library which is just an implementation of lists with arrays. Create and export functions to do the basical list tasks such as insert, get, remove and stuff, and use those functions from your radix sort.
The best thing is that, when you're finished, you can replace the implementation of your list whith whatever you want (you can use real linked lists, for example) and you won't have to change your radix sort algorithm.
That's encapsulation and that's why it's so good.
just because i LOVE linked lists AND encapsulation so much...
Code: Sub array_push( ls() As Integer, v As Integer )
Redim Preserve ls( ( UBound( ls ) - LBound( ls ) ) + 1 )
For rshift = UBound( ls ) To 1 Step -1
Swap ls( rshift ), ls( rshift - 1 )
Next
ls( 0 ) = v
End Sub
Function array_pop( ls() As Integer ) As Integer
array_pop = ls( 0 )
For lshift = 0 To UBound( ls ) - 1
Swap ls( lshift ), ls( lshift + 1 )
Next
Redim Preserve ls( UBound( ls ) - 1 )
End Function
Dim As Integer array_list()
array_push( array_list(), 783264 )
array_push( array_list(), 3462 )
array_push( array_list(), 6195 )
array_push( array_list(), 364782 )
? UBound( array_list )
? array_pop( array_list() )
? array_pop( array_list() )
? array_pop( array_list() )
? array_pop( array_list() )
Sleep
Posts: 357
Threads: 118
Joined: Oct 2004
cha0s: I believe that what you created is a stack. The Inferface for a LinkedList has: Append, Prepend, Insert, Remove. There is a stack in my program, I'm pretty sure that that part of it is working, the bug is somewhere else.
I'm not worried about encapsulation, I'm working on a huge container library currently as another project and that has all the linked list and stack functions I will ever need, right now I just need to get this sort working.
f you play a Microsoft CD backwards you can hear demonic voices. The scary part is that if you play it forwards it installs Windows.
yeah, this is for school right? i wouldnt give you th answer anyways.
please, don't take this as offense, i've just seen a lot.
when i hear someone say things like encapsulation, structure don'tmatter for WHATEVER reason, it leads me to believe theyre highly inexperienced, because i'll tell you what, ive been coding a lot lately, and i've really found out what it means to be organized. what i guess im trying to say is that encapsulation and abstraction go hand in hand, and as anyone here knows with a bit of proggin under theirbelts; abstraction will help you find bugs.
Posts: 6,419
Threads: 74
Joined: Mar 2002
Quote:I'm not worried about encapsulation,
And that's a bad thing. Seriously.
Posts: 357
Threads: 118
Joined: Oct 2004
lol
Trust me, I believe in encapulation and use it extensively when seriously programming. The purpose of this assignment was the analysis of the algorithm so I never planned on using it again. I have other sorts that work much better.
f you play a Microsoft CD backwards you can hear demonic voices. The scary part is that if you play it forwards it installs Windows.
Posts: 3,368
Threads: 195
Joined: Jan 2003
Da Progger Doktar is here!
:???:
8)
You probably have a load of bugs in there then, by the symptoms you describe. Probably placed the wrong index value in your array somewhere.. also probably you need to adjust your loop limits to +1 or -1 or something.. just try to rethink each line and see if it makes sense.
Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."
Visit www.neobasic.net to see rubbish in all its finest.
Posts: 320
Threads: 9
Joined: Dec 2004
Out of curiosity, why are you doing it in FreeBASIC? Using a language with a decent set of standard datastructures (C++ or Java) would make your task a lot easier. It's very hard to try and understand what your code is trying to do at the moment. It would be better to use a container such as std::queue for this.
Also, consider using a base-2 radix sort instead... that will simplify the code a lot.
Here's one I just wrote (it's not wonderful, but it works at least):
[syntax="C"]
#include <iostream>
#include <queue>
#include <vector>
#include <iterator>
template< class InIter, class OutIter >
void radixSort( InIter start, InIter end, OutIter res )
{
std::queue< unsigned long > lo; // for elements with 0 at the current position
std::queue< unsigned long > hi; // for elements with 1 at the current position
std::vector< unsigned long > result;
InIter p = start;
// make a local copy of the input array.
std::copy( start, end, std::back_inserter( result ) );
for( unsigned long i = 1; i; i <<= 1 )
{
for( std::vector< unsigned long >::iterator p = result.begin(); p != result.end(); p++ )
{
if( *p & i )
hi.push( *p );
else
lo.push( *p );
}
// read the numbers out into our local vector again.
result.clear();
while( !lo.empty() )
{
result.push_back( lo.front() );
lo.pop();
}
while( !hi.empty() )
{
result.push_back( hi.front() );
hi.pop();
}
}
// copy the results out.
std::copy( result.begin(), result.end(), res );
}
int main( int argc, char** argv )
{
std::vector< unsigned long > nums;
nums.push_back( 5 );
nums.push_back( 10 );
nums.push_back( 7 );
nums.push_back( 1 );
nums.push_back( 25 );
std::cout << "Unsorted array: " << std::endl;
std::copy( nums.begin(), nums.end(), std::ostream_iterator< unsigned long >( std::cout, "\n" ) );
std::vector< unsigned long > result;
radixSort( nums.begin(), nums.end(), std::back_inserter( result ) );
std::cout << std::endl << "Sorted array: " << std::endl;
std::copy( result.begin(), result.end(), std::ostream_iterator< unsigned long >( std::cout, "\n" ) );
return 0;
}
[/syntax]
If you only need to do algorithmic analysis, you should be able to do it directly from the pseudocode (I guess you're trying to find the Big-O expression for the sort?).
img]http://www.cdsoft.co.uk/misc/shiftlynx.png[/img]
Posts: 357
Threads: 118
Joined: Oct 2004
I chose freebasic because besides DevC++ its the only compiler/ide on my computer and there is something wrong with my Dev compiler right now. I did think about using C++, but then i'd have to frequent the computer lab.
f you play a Microsoft CD backwards you can hear demonic voices. The scary part is that if you play it forwards it installs Windows.
|