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 chứa trong mảng a1.
+ Ba lớp dẫn xuất là: SELECT_SORT, QUICK_SORT và HEAP_SORT. Mỗi lớp đều có
phương thức ảo:
virtual void sapxep(int *a1, long n) ;
để thực hiện hiện việc sắp xếp theo theo một thuật toán cụ thể.

}
} ;
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:
virtual void sapxep(int *a1, long n) ;
} ;
void quick_sort::q_sort(long l, long r)
{
int x;
long i,j;

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);
/* Tao dong */
for (i=n/2 ; i>=1; --i) shift(i,n);
/* Lap */
for (i=n ; i>=2; --i)
{
hoan_vi(1,i);

gettime(&t2);
tg = (t2.ti_sec - t1.ti_sec)*100 + t2.ti_hund - t1.ti_hund ;
sec = tg / 100;
hund = tg % 100;