Các lớp sắp xếp
Trong tệp C_SORT.H dưới đây sẽ chứa 4 lớp sắp xếp: sort, select_sort,
quick_sort và heap_sort. tổng quát hơn. So với các lớp sắp xếp trong mục
§
7
chương 6 thì các lớp ở đây tổng quát hơn ở chỗ:
+ Các lớp trong mục
§
7 chương 6 chỉ cho phép sắp xếp một dẫy số nguyên theo
thứ tự tăng dần.
+ Các lớp dưới đây cho phép sắp xếp một dẫy phần tử có kiểu bất kỳ (nguyên,
thực, cấu trúc, lớp, ...) và theo một tiêu chuẩn sắp xếp bất kỳ.
1. Lớp sort là lớp cơ sở trừu tượng
+ Các thuộc tính:
protected:
void *a ; // Trỏ tới vùng nhớ chứa dẫy
// phần tử cần sắp xếp
int size ; // Độ lớn tính theo byte của phần tử
int (*nho_hon)(void* pt1, void* pt2); // Con trỏ hàm
// định nghĩa pt1 nhỏ hơn pt2
+ Các phương thức:
protected:
void hoan_vi(int i, int j) ; // Hoán vị các phần tử thứ i và j
void * dia_chi (int m); // Cho địa chỉ của phần tử thứ m
public:
virtual void sapxep(void *a1,int n,int itemsize,
int (*ss_nho_hon)(void* ,void* )) ; // Sắp xếp dẫy
// n phần tử chứa trong vùng nhớ a1, mỗi phần tử
// có độ dài itemsize, thứ tự tăng được quy định
// bởi hàm ss_nho_hon
2. Lớp select_sort dẫn xuất từ lớp sort. Lớp này sẽ thực hiện việc sắp xếp theo

Dưới đây là nội dung tệp C_SORT.H
//C_SORT.H
// Lop co so truu tuong
// Lop sort
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <iomanip.h>
#include <mem.h>
class sort
{
protected:
void *a;
int size;
int (*nho_hon)(void*,void*);
void* dia_chi(int m)
{
return (void*) ((char*)a + size*(m-1));
}
void hoan_vi(int i, int j)
{
538
void *tg, *di, *dj;
di= dia_chi(i);
dj= dia_chi(j);
tg = new char[size];
memcpy(tg,di,size);
memcpy(di,dj,size);
memcpy(dj,tg,size);

class quick_sort : public sort
{
private:
540
void q_sort(int l, int r);
public:
virtual void sapxep(void *a1,int n,int itemsize,
int (*ss_nho_hon)(void*,void*)) ;
} ;
void quick_sort::q_sort(int l, int r)
{
void *x;
int i,j;
x = new char[size];
if(l < r)
{
memcpy(x, dia_chi(l), size);
i = l; j = r+1;
do
{
++i; --j;
while(i<r && nho_hon(dia_chi(i),x)) ++i ;
while(nho_hon(x,dia_chi(j)) ) --j ;
if(i<j) hoan_vi(i,j);
} while (i<j);
hoan_vi(l,j);
q_sort(l,j-1);
q_sort(j+1,r);
}
}

return;
else
{
hoan_vi(i,k);
shift(k,n);
}
}
void heap_sort::sapxep(void *a1,int n,int itemsize,
int (*ss_nho_hon)(void*,void*))
{
long i;
sort::sapxep(a1,n,itemsize,ss_nho_hon);
// Tao dong
for(i=n/2 ; i>=1; --i) shift(i,n);
// Lap
for(i=n ; i>=2; --i)
{
hoan_vi(1,i);
shift(1,i-1);
}
}
542