Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Sorting algorithm has a bug that I can't find
#1
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.
Reply
#2
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 Smile and that's why it's so good.
SCUMM (the band) on Myspace!
ComputerEmuzone Games Studio
underBASIC, homegrown musicians
[img]http://www.ojodepez-fanzine.net/almacen/yoghourtslover.png[/i
Reply
#3
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
Reply
#4
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.
Reply
#5
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.
Reply
#6
Quote:I'm not worried about encapsulation,

And that's a bad thing. Seriously.
SCUMM (the band) on Myspace!
ComputerEmuzone Games Studio
underBASIC, homegrown musicians
[img]http://www.ojodepez-fanzine.net/almacen/yoghourtslover.png[/i
Reply
#7
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.
Reply
#8
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.
Reply
#9
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]
Reply
#10
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.
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)