Visual Sorting Part 1
Remember the days before the internet?
I have a collection of hundreds of programs that I wrote in the early 1980’s using the DeSmet C compiler. This is way before the internet age. My machine of choice was an IBM PC with 4.77 MHz 16 bit processor and 256K Ram, dual floppy disks, running MS DOS. It was way more advanced than the PDP-8 and PDP-11 computers I had been using the prior decade.
One of the programs I wrote is below: I called it SortQ. It would fill the color graphics adapter of my PC with 25 rows of 80 chars (640 X 200) with random characters. The user could choose from a few sorting algorithms from a few choices and the program would sort the characters while the user could see them. It was always a good demo to others to see how a Shell Sort compares with a QuickSort. You can see the characters flying across the screen. Some of the algorithms worked locally, starting at the top and working down, but some algorithms you could see waves of operations throughout the data.
A summary of the number of comparisons and the number of moves is shown when done.
From the listing below, you can see that the program had direct access to screen row and column coordinates. It treated the array of cells of 1 char as the data to sort.
This was in the days of single threaded programs, with no mouse.
The new version below uses a background thread to do the work and allows multiple length data.
The execution of sorting algorithms consists of multiple operations like retrieving, comparing, replacing values. Because the code below actually updates the display, the updates are hugely more expensive than comparing or reading. This makes the cycle sort seem much faster when comparing with others because it has the fewest updates. In fact, the number of updates is less than or equal to nTotal, the number of items.
Next post is a more advanced version of the code below using Visual Studio.
See also
Thirty years ago, computers were quite different Relaxen und watchen das blinkenlights. What lights? My toys over the years
#define NUM 1920
main()
{
int d,r,c='q',j;
scr_setup();
scr_cursoff();
peeksinit();
while (1)
{
scr_rowcol(24,2);
printf("q=quick s=shell x=super b=bubble i=insertion ");
if ( j=csts() ) c=j;
switch (c)
{
case 'q': printf("Quicksort ");
fill(r++,NUM) ;
qs( 1 , NUM ); break;
case 'x': printf("Supersort ");
fill(r++,NUM) ;
superq(1,NUM); break;
case 'b': printf("Bubble sort ");
fill(r++,NUM/8) ;
bs( 1 , NUM/8 ); break;
case 's': printf("Shellsort ");
fill (r++,NUM) ;
shell(1,NUM); break;
case 'i': printf("Insertion sort");
fill (r++,NUM/4) ;
insert (1,NUM/4); break;
case ' ': scr_rowcol(24,0);
scr_curson();
exit(); break;
}
}
}
qs(l,r)
int l,r;
{
register int i=l,j=r+1,t;
if ( l>=r ) return;
t=p(l);
while ( j > i )
{
while ( p(++i) < t )
;
while ( p(--j) > t )
;
if ( j > i )
exch( i , j );
}
exch( j , l );
qs( l , j-1 );
qs( j+1 , r );
}
p(d)
register int d;
{
return ( peeks( d ) );
}
fill(r,n)
int r,n;
{
register int d;
srand( r );
for ( d=1 ; d<n ; d++ )
pokes( ( rand()& 0x7f) + 33 , d );
pokes ( 0 , 0 );
pokes ( 250 , n );
}
exch(m,n)
register int m,n;
{
int t;
t=p(m);
pokes( p(n) , m );
pokes( t , n );
}
bs(l,r)
int l,r;
{
register int i,j;
for ( i=0 ; i<r ; i++ )
{
for ( j=i ; j<r ; j++)
if ( p(i) > p(j) ) exch(i,j);
}
}
superq(l,r)
int l,r;
{
register int i,j,d[256],k=0;
for ( i=0 ; i<256 ; i++)
d[i]=0;
for ( i=0 ; i<r ; i++ )
d[p(i)]++;
scr_setup();
scr_rowcol(0,0);
for ( i=32 ; i<256 ; i++ )
for ( j=0 ; j<d[i] ; j++ )
pokes( i , k++ );
}
shell(l,n)
int l,n;
{
int g,i,j;
for ( g=n/2 ; g>0 ; g/=2)
for ( i=g ; i<n ; i++)
for ( j=i-g ; j>=0 && p(j)>p(j+g) ; j-=g )
exch(j,j+g);
}
insert(l,n)
int l,n;
{
int i,j,t;
for ( j=1; j<n ; j++)
if ( p(j-1) > p(j) )
{
t=p(j);
for ( i=j ; p(i-1)>t ; i-- )
pokes(p(i-1),i);
pokes(t,i);
}
}