help

[Nidaa87]

radix sort:
an example :

Original, unsorted list:
170, 45, 75, 90, 2, 24, 802, 66

Sorting by least significant digit (1s place) gives:
170, 90, 2, 802, 24, 45, 75, 66

Notice that we keep 2 before 802, because 2 occurred before 802 in the original list, and similarly for 170 and 90.

Sorting by next digit (10s place) gives:
2, 802, 24, 45, 66, 170, 75, 90

Sorting by most significant digit (100s place) gives:
2, 24, 45, 66, 75, 90, 170, 802

your program should do the following:
1.write a function which implements the LCD radix sort
2.generate 1000 random numbers and store it in a arry, the numbers should be consist from 4 digits at least
3.choose any other sorting algorithm and implement it
4.compute the number of swapping which made by radix sort and compute the number of swapping made by the selected algorithm
5.compute the time of radix sort and compare it with the time of the selected algorithm
6.the two algorithms should be applied on the same data which mean that the original array cannot be changed
7.your program must have a menu

[Ancient Dragon]

Which part of that assignment do you need help on? What don't you understand ? Have you even tried yet ?

[Nidaa87]

I wrote this code and there is not a mistake, I want code calculation time radix sort, compare with the time of the selection algorithm

#define NUMELTS 100
# include<stdio.h>
#include<iostream>
#include<conio.h>
#include<math.h>
using namespace std;
void radixsort(int a[],int);
void main()
{
   int n,a[20],i;
   //clrscr();

   cout<<"enter the number :";
   scanf("%d",&n);
   cout<<("ENTER THE DATA");
   for(i=0;i<n;i++)
    {
      cout<<("%d.  ",i+1);
      scanf("%d",&a[i]);
    }
    radixsort(a,n);
   getch();
 }
void radixsort(int a[],int n)
{
 int rear[10],front[10],first,p,q,exp,k,i,y,j;
 struct
 {
  int info;
  int next;
 }node[NUMELTS];
 for(i=0;i<n-1;i++)
 {
  node[i].info=a[i];
  node[i].next=i+1;
 }
 node[n-1].info=a[n-1];
 node[n-1].next=-1;
 first=0;

  for(k=1;k<=2;k++)      //consider only 2 digit number
  {
   for(i=0;i<10;i++)
     {
      front[i]=-1;
      rear[i]=-1;
     }

    while(first!=-1)
      {
       p=first;
       first=node[first].next;
       y=node[p].info;
       exp=pow(10,k-1);
       j=(y/exp)%10;
       q=rear[j];
       if(q==-1)
	 front[j]=p;
       else
	 node[q].next=p;
       rear[j]=p;
      }
    for(j=0;j<10&&front[j]==-1;j++)
     ;
    first=front[j];
    while(j<=9)
     {
      for(i=j+1;i<10&&front[i]==-1;i++)
       ;
      if(i<=9)
      {
	p=i;
	node[rear[j]].next=front[i];
      }
      j=i;
    }
    node[rear[p]].next=-1;
}
//copy into original array
for(i=0;i<n;i++)
{
  a[i]=node[first].info;
  first=node[first].next;

}
//clrscr();
//textcolor(YELLOW);
cout<<"\nDATA AFTER SORTING:\n";
for(i=0;i<n;i++)
 cout<<i+1<<"\t\t\t"<<a[i]<<"\n";
}

[Nidaa87]

I would be grateful to you in your assistance in resolving this program

[vmanes]

to do any realistic comparisons of sorts functions, you'll need to use a larger data array. Even then, on a modern PC, the time to sort will be so quick, you may have to run the sorts many times in succession to see a difference.

Access the system time before starting a run of one sort, run it, then get system time again. Subtract. Note that C++ does not natively give you any resolution better than 1 second increments.

Also be sure to account for the overhead time of just calling the functions repeatedly, and of resetting your array back to its initial state.

[Nidaa87]

Dr. demanded resolution of this question to the data structure
Please clarify what

[ithelp]

Use time to measure number of miliseconds passed in radixsort for huge arrays.

[Nidaa87]

The expense and time radixsort comparable another type of the sort