Xử lý các thuật toán khác nhau
Có thể sử dụng tương ứng bội để tổ chức thực hiện các thuật toán
khác nhau trên cùng một bài toán như sau:
+ Lớp cơ sở trừu tượng sẽ chứa dữ liệu bài toán và một phương
thức ảo.
+ Mỗi lớp dẫn xuất ứng với một thuật toán cụ thể. Phương thức ảo
của lớp dẫn xuất sẽ thực hiện một thuật toán cụ thể.
+ Sử dụng một mảng con trỏ của lớp cơ sở và gán cho mỗi phần tử
mảng địa chỉ của một đối tượng của lớp dẫn xuất. Sau đó dùng các
phần tử mảng con trỏ để gọi tới các phương thức ảo. Bằng cách đó sẽ
thực hiện cùng một bài toán theo các thuật toán khác nhau và dễ dàng
so sánh hiêụ quả của các thuật toán.
Ví dụ sau minh hoạ việc thực hiện bài toán sắp xếp dẫy số nguyên
theo thứ tự tăng bằng cách dùng đồng thời 3 thuật toán: Thuật toán
lựa chọn (Select_Sort), thuật toán sắp xếp nhanh (Quick_Sort) và
thuật toán vun đống (Heap_Sort). Chương trình gồm 4 lớp:
+ Lớp cơ sở trừu tượng:
class sort
{
protected:
int *a;
void hoan_vi(long i, long j) ;
public:
virtual void sapxep(int *a1, long n) ;
} ;
Lớp này gồm:
- Một thành phần dữ liệu là con trỏ a trỏ tới một vùng nhớ chứa
dẫy số nguyên cần sắp xếp.
- Phương thức hoan_vi(i,j) dùng để hoán vị các phần tử a[i] và a[j].
Phương thức này được dùng trong 3 lớp dẫn xuất bên dưới.
- Phương thức ảo sapxep(a1,n) dùng để sắp xếp dẫy n số nguyên

a[j] = tg;
}
public:
virtual void sapxep(int *a1, long n)
{
a = a1;
}
} ;
class select_sort : public sort
{
public:
virtual void sapxep(int *a1, long n) ;
} ;
void select_sort::sapxep(int *a1, long n)
{
long i,j,r;
sort::sapxep(a1,n);
for (i=1; i<n; ++i)
{
r=i;
for (j=i+1; j<=n; ++j)
if(a[j] < a[r]) r = j;
if(r!=i) hoan_vi(i,r);
}
}
class quick_sort : public sort
{
private:
void q_sort(long l, long r);
public:

void shift(long i, long n);
public:
virtual void sapxep(int *a1, long n) ;
} ;
void heap_sort::shift(long i, long n)
{
long l,r,k;
l = 2*i; r = l+1;
if (l>n) return;
if (l==n)
{
if (a[i]<a[l]) hoan_vi(i,l);
return;
}
if (a[l] > a[r])
k = l;
else
k = r;
if (a[i]>=a[k])
return;
else
{
hoan_vi(i,k);
shift(k,n);
}
}
void heap_sort::sapxep(int *a1, long n)
{
long i;
sort::sapxep(a1,n);

{
srand(5000);
for (i=1;i<=n;++i)
a[i]=rand();
gettime(&t1);
s[k]->sapxep(a,n);
gettime(&t2);
tg = (t2.ti_sec - t1.ti_sec)*100 + t2.ti_hund - t1.ti_hund ;
sec = tg / 100;
hund = tg % 100;
printf("\n Sap xep %d %d %d %d %d",k+1,
t2.ti_sec,t2.ti_hund,t1.ti_sec,t1.ti_hund);
printf("\n Sap xep %d Thoi gian %d sec %d hund",
k+1,sec,hund);
}
getch();
}
363