C++ Sorts

```// C++ LSD Radix Sort example, queue implementation

#include <iostream.h>
#include <cstdlib.h>
#include <ctime.h>

using std::cout; // Remove this line for older C++ compilers

typedef struct slist_ {
int val;
struct slist_ *next;
} slist;

{
int i, j, d, m=1;

// Process t digits
for (j=1; j<=t; j++)
{
// Initialize the queues, 0 to 9
for (i=0; i<=9; i++)
{
tail[i] = NULL;
}

// Process the list L
while ( L != NULL )
{
// Get the decimal digit with place value m
d = static_cast<int>(L->val/m)%10;

// Make temp point to the current list item
temp = L;

// Make L point to the next list item
L = L->next;

// Disconnect the current list item, making it self-contained
temp->next = NULL;

{   // The queue for digit d is not empty

// Add the list item to the end of the queue for digit d
tail[d]->next = temp;

// Make tail[d] point to the new tail item of queue d
tail[d] = temp;
}
else
{   // The queue for digit d is empty
tail[d] = temp;  // Point to the new tail
}
} // while

// Find the index, d, of the first non-empty queue
d=0;
d++;

// Point to the first item of the first non-empty queue

// Point to the last item of the first non-empty queue
temp = tail[d];

// Append the items of the remaining non-empty queues
// to the tail of list L.
d++;
while (d<10)
{
{
// Append the items of non-empty queue d to list L

// Point to the new tail of list L
temp = tail[d];
}

d++;
} // while

// Prepare to process the next more significant digit
m = m*10;
} // for

return L;
}

int main()
{
// Initialize the random number seed with the time
srand( static_cast<unsigned int>(time(NULL)) );

const int size = 20;
int n[size];
int i, max=-1, t=0;

// Generate some random numbers
slist *start=NULL,*end=NULL,*temp;
for (i=0; i<size; i++)
{
n[i] = rand();
}

// Find the largest value and create a linked list of the random values
for (i=0; i<size; i++)
{
// Find the largest value
if (n[i] > max)
max = n[i];

// Create a new node
temp = new slist;

// Fill the node with a random value
temp->val = n[i];

// Seal the node
temp->next = NULL;

if (start != NULL)
{   // Append the new node to the linked list
end->next = temp;
end = temp;
}
else
start = temp;
end = temp;
}
}

// Find the number of decimal digits in the largest random value
while (max>0)
{
t=t+1;
max=max/10;
}

// Display the results
temp = start;
for (i=0; i<size; i++)
{
cout << temp->val << "\n";
temp = temp->next;
}

// Return a zero to the calling script, batch file, or command shell
// to indicate successful completion.
return 0;
} // main
```

SOURCE

Subscribe now to receive more great content like this!