Hello, I am doing a radixSort to determine some Big-O values and I stuck. When I debug the code it runs until the switch statement, with initial value being zero, hits the return statement and then by pass all other code and goes straight to the end of the function. Any thought?
int radixSort(int *dta, int n, int *out)
{
// the dta array contains the data to be sorted.
// n is the number of data items in the array.
// out is the array to put the sorted data
node *bucket[1000]; // declare an array of 1000 linked lists (head pointers)
int index; // where in the bucket do we want to store this data
int count = 0; // use this to count the instructions to graph the big-o
for(int i = 0; i < n; i++)
out[i] = dta[i]; // first copy dta into out for use by the shell. Use out from now on in this function
for ( int pass = 0; pass <= 3; pass++ ) // this is the outer loop
{
for( int j = 0; j < 1000; j++ )// set bucket[] to all //zeroes(NULL) for each pass
bucket[ j ] = NULL;
for( int i = 0; i < 3; i++ ) // inner loop - walk through the out array ( which contains the data to be sorted )
{
switch( i )
{
case 0:
third( 0 );
{
return 0 % 1000;//return last three digits (least significant)
}
break;
case 1:
second( 1 );
{
return ( 1 / 1000 ) % 1000; // return middle three digits
}
break;
case 2:
first( 2 );
{
return 2 / 1000000;// return first 3 digits (most significant)
}
break;
};
if( bucket[ index ] == NULL ) // nothing is stored here so
{
bucket[ index ] = new node( out[ i ], NULL ); // create a new head node and store this data
count++; // count this
}
else
{
while( bucket[ index ] != NULL ) // loop through list
{
bucket[ index ] = new node( out[ i ], NULL );
}
node *ptr = bucket[index];
while ( ptr->next != NULL)
{
ptr = ptr->next; // walk the list
count++; //count this also
}
// make a new node and attach it to the tail
ptr->next = new node(out[i],NULL);
count++; // count this
// now see if there are more nodes in the linked list that starts at bucket[i]. If there are, put their data into out[idx++]
// something is already here so make a new node, store the out[i] in the new node
// walk the linked list from the head (bucket[index] to find the last node (tail).
// make tail point to the new node you just created.
}
int idx = 0; // you need this to load the out array
for( int i = 0; i < 1000; i++ ) // walk through the bucket
{
if(bucket[i] == NULL)continue; //nothing was stored here so skip to the next item
node *ptr1 = bucket[ i ];
while ( ptr1->data != NULL)
{
out[idx++] = bucket[ i ]->data;
out[idx++] = ptr1->data; // walk the list
count++; //count this also
}
// now see if there are more nodes in the linked list that starts at bucket[i]. If there are, put their data into out[idx++]
}// at this point, idx must equal n (use this as a check)
} // end of the inner (i) loop
}// end of the outer loop pass). The output (out) from this pass becomes the input for the next pass
return count;
}
Thanks I fixed that with a couple of functions. Now I get a "Unhandled exception at 0x00489652 in LabShell.exe: 0xC0000005: Access violation writing location 0x00395000." for line 81. Any thoughts?
Something to do with memory addresses. 0x at the beginning indicates that it's a location in a RAM file. Maybe you exceeded the amount of physical RAM that you have installed?
The loop on lines 78-83 will never finish because it depends on a value that never changes. Specifically, you're not changing ptr1 so it traverses the list.
