title: Radix Sort implemented in C++
body: <p>I am trying to improve my C++ by creating a program that will take a large amount of numbers between 1 and 10^6. The buckets that will store the numbers in each pass is an array of nodes (where node is a struct I created containing a value and a next node attribute). </p>
  
  <p>After sorting the numbers into buckets according to the least significant value, I have the end of one bucket point to the beginning of another bucket (so that I can quickly get the numbers being stored without disrupting the order). My code has no errors (either compile or runtime), but I've hit a wall regarding how I am going to solve the remaining 6 iterations (since I know the range of numbers). </p>
  
  <p>The problem that I'm having is that initially the numbers were supplied to the radixSort function in the form of a int array. After the first iteration of the sorting, the numbers are now stored in the array of structs. Is there any way that I could rework my code so that I have just one for loop for the 7 iterations, or will I need one for loop that will run once, and another loop below it that will run 6 times before returning the completely sorted list?</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;math.h&gt;
  using namespace std;
  
  struct node
  {
      int value;
      node *next; 
  };
  
  //The 10 buckets to store the intermediary results of every sort
  node *bucket[10];
  //This serves as the array of pointers to the front of every linked list
  node *ptr[10];
  //This serves as the array of pointer to the end of every linked list
  node *end[10];
  node *linkedpointer;
  node *item;
  node *temp;
  
  void append(int value, int n)
  {
      node *temp; 
      item=new node;
      item-&gt;value=value;
      item-&gt;next=NULL;
      end[n]=item;
      if(bucket[n]-&gt;next==NULL)
      {
          cout &lt;&lt; "Bucket " &lt;&lt; n &lt;&lt; " is empty" &lt;&lt;endl;
          bucket[n]-&gt;next=item;
          ptr[n]=item;
      }
      else
      {
          cout &lt;&lt; "Bucket " &lt;&lt; n &lt;&lt; " is not empty" &lt;&lt;endl;
          temp=bucket[n];
          while(temp-&gt;next!=NULL){
              temp=temp-&gt;next;
          }
          temp-&gt;next=item;
      }
  }
  
  bool isBucketEmpty(int n){
      if(bucket[n]-&gt;next!=NULL)
          return false;
      else
          return true;
  }
  //print the contents of all buckets in order
  void printBucket(){
      temp=bucket[0]-&gt;next;
      int i=0;
      while(i&lt;10){
          if(temp==NULL){
              i++;
              temp=bucket[i]-&gt;next;                       
          }
          else break;
  
      }
      linkedpointer=temp;
      while(temp!=NULL){
          cout &lt;&lt; temp-&gt;value &lt;&lt;endl;
          temp=temp-&gt;next;
      }
  }
  
  void radixSort(int *list, int length){
      int i,j,k,l;
      int x;
      for(i=0;i&lt;10;i++){
          bucket[i]=new node;
          ptr[i]=new node;
          ptr[i]-&gt;next=NULL;
          end[i]=new node;
      }
      linkedpointer=new node;
  
      //Perform radix sort
      for(i=0;i&lt;1;i++){
          for(j=0;j&lt;length;j++){          
              x=(int)(*(list+j)/pow(10,i))%10;            
              append(*(list+j),x);
              printBucket(x); 
          }//End of insertion loop
          k=0,l=1;
  
          //Linking loop: Link end of one linked list to the front of another
          for(j=0;j&lt;9;j++){
              if(isBucketEmpty(k))
                  k++;
              if(isBucketEmpty(l) &amp;&amp; l!=9)
                  l++;
              if(!isBucketEmpty(k) &amp;&amp; !isBucketEmpty(l)){
                  end[k]-&gt;next=ptr[l];
                  k++;
                  if(l!=9) l++;   
              }
  
          }//End of linking for loop
  
          cout &lt;&lt; "Print results" &lt;&lt;endl;
          printBucket();
  
          for(j=0;j&lt;10;j++)
              bucket[i]-&gt;next=NULL;                       
          cout &lt;&lt; "End of iteration" &lt;&lt;endl;
      }//End of radix sort loop
  }
  
  int main(){
      int testcases,i,input;
      cin &gt;&gt; testcases;
      int list[testcases];
      int *ptr=&amp;list[0];
      for(i=0;i&lt;testcases;i++){
          cin&gt;&gt;list[i];
      }
  
      radixSort(ptr,testcases);
      return 0;
  }
  </code></pre>