In this section we talk about building implementation, interfaces, and client programs for sorting algorithms. Specifically, we consider interfaces for :
Sort driver for arrays
#inlcude <stdlib.h>
#include "Item.h"
#include "exch.h"
#include "Array.h"
main(int argc , char *argv[]){
int N = atoi(argv[1]), sw = atoi(argv[2]);
Item *a = new Item[N];
if(sw) rand(a,N); else scan(a,N);
sort(a,0,N-1);
show(a,0,N-1);
}
This driver uses 3 explicit interfaces :
exch
and compexch
for sort implementationInterface for array data type
//Array.h interface defines high level functions for abstract items
template <class Item>
void rand(Item a[],int N);
template <class Item>
void scan(Item a[], int &N);
template <class Item>
void show(Item a[], int l ,int r);
template <class Item>
void sort(Item a[], int l, int r);
Implementation of array data type
#include <iostream.h>
#include <stdlib.h>
#include "Array.h"
template <class Item>
void rand(Item a[],int N)
{ for(int i= 0 ; i < N; i++) rand(a[i]); }
template <class Item>
void scan(Item a[],int &N){
for(int i = 0 ; i< N ; i++)
if(!scan(a[i])) break;
N=i;
}
template <class Item>
void show(Item a[], int l ,int r){
for(int i = l; i <= r ; i++)
show(a[i]);
cout<<endl;
}
In similar manner we can define Item interfaces
Interface for item data type
typedef struct record { int key; float info ;} Item;
int operator<(const Item&, const Item&);
int scan(Item&);
void rand(Item&);
void show(const Item&);
Implementation for item data type
#include <iostream.h>
#include <stdlib.h>
#include "Item.h"
int operator<(const Item& A, const Item& B)
{ return A.key < B.key; }
int scan(Item& x)
{ return (cin>>x.key>>x.info)!= 0;}
void rand(Item$ x)
{ x.key = 1000*(1.0 *rand() / RAND_MAX);
x.info = 1.0*rand()/RAND_MAX; }
void show(const Item& x)
{ cout<<x.key<<" "<<x.info<<endl;}