Bài giảng Các kỹ thuật lập trình

a phần tử thứ i1 trong tập hai phần tử và 
thực hiện đổi chỗ. 
 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 Lấy tiếp phần tử thứ ik chọn vị trí thích hợp của phần tử thứ ik trong tập hai ik-1 phần 
tử và thực hiện đổi chỗ, dãy sẽ được sắp xếp hoàn toàn sau n-1 lần chèn phần tử vào vị 
trí thích hợp. 
Độ phức tạp bé nhất của thuật toán là: Cmin = ( n-1); 
Độ phức tạp lớn nhất của thuật toán là: n(n-1)/2 = O(n2) 
Độ phức tạp trung bình của thuật toán là: (n2 +n- 2)/4 = O(n2) 
Quá trình sắp xếp theo Insertion Sort được mô tả như sau: 
Lượt 
Khoá 
1 
42 
2 
23 
3 
74 
4 
11 
. . . 
. . . 
8 
36 
9 
99 
10 
87 
1 
2 
3 
4 
5 
42 23 
42 
23 
42 
74 
11 
23 
42 
74 
. . . 
. . . 
. . . 
. . . 
. . . 
11 
23 
42 
58 
65 
11 
23 
36 
42 
58 
11 
23 
36 
42 
58 
PT
IT
 225 
6 
7 
8 
9 
10 
. . . 
. . . 
. . . 
. . . 
. . . 
74 
94 
65 
74 
94 
99 
65 
74 
87 
95 
99 
Thuật toán được cài đặt như sau: 
#include 
#include 
#include 
#include 
#include 
void Insert(int *, int); 
void Init(int *, int); 
void In(int *, int); 
void Init(int *A, int n){ 
 int i; 
 printf("\n Tao lap day so:"); 
 for (i=0; i<n;i++){ 
 A[i]=random(1000); 
 printf("%5d",A[i]); 
 } 
 delay(1000); 
} 
void Insert(int *A, int n){ 
 register i,j,temp; 
 for (i=1;i<n;i++){ 
 temp=A[i]; 
 for(j=i-1;j>=0 && temp<A[j];j--) 
 A[j+1]=A[j]; 
 A[j+1]=temp; 
 printf("\n"); 
 In(A,i+1); 
 } 
} 
void In(int *A, int n){ 
 register int i; 
 for(i=0;i<n;i++) 
 printf("%5d",A[i]); 
 delay(1000); 
PT
IT
 226 
} 
void main(void){ 
 int *A,n;clrscr(); 
 printf("\n Nhap n="); scanf("%d",&n); 
 A=(int *) malloc(n*sizeof(int)); 
 Init(A,n);Insert(A,n); 
 free(A); 
} 
7.4. Giải thuật Bubble Sort 
 Giải thuật Bubble Sort được thực hiện bằng cách đổi chỗ liên tiếp hai phần tử kế 
cận khi chúng ngược thứ tự. Quá trình thực hiện được duyệt từ đáy lên đỉnh. Như vậy, sau 
lần duyệt thứ nhất, phần tử lớn nhất sẽ được xếp đúng ở vị trí thứ n-1, ở lần duyệt thứ k 
thì k phần tử lớn nhất đã được xếp đúng vị trí n-1, n-2, . ., n-k+1. Sau lần duyệt thứ n-1, 
toàn bộ n phần tử sẽ được sắp xếp. Với phương pháp này, các phần tử có giá trị nhỏ được 
nổi dần lên như nước sủi bọt nhờ đó nó có tên gọi “phương pháp sủi bọt”. 
 Độ phức tạp của thuật toán Bubble Sort là: 
Cmin = Cmax = Ctb = n(n-1)/2. 
 Chương trình mô tả thuật toán Bubble Sort được cài đặt như sau: 
#include 
#include 
#include 
#include 
#include 
void Bubble(int *, int); 
void Init(int *, int); 
void In(int *, int); 
void Init(int *A, int n){ 
 int i; 
 printf("\n Tao lap day so:"); 
 for (i=0; i<n;i++){ 
 A[i]=random(1000); 
 printf("%5d",A[i]); 
 } 
 delay(1000); 
} 
void Bubble(int *A, int n){ 
 register i,j,temp; 
PT
IT
 227 
 for (i=1; i<n; i++){ 
 for (j=n-1; j>=i; j--){ 
 if (A[j-1]>A[j]){ 
 temp=A[j-1]; 
 A[j-1]=A[j]; 
 A[j]=temp; 
 } 
 } 
 printf("\n Ket qua lan:%d", i); 
 In(A,n); 
 } 
} 
void In(int *A, int n){ 
 register int i; 
 for(i=0;i<n;i++) 
 printf("%5d",A[i]); 
 delay(1000); 
} 
void main(void){ 
 int *A,n;clrscr(); 
 printf("\n Nhap n="); scanf("%d",&n); 
 A=(int *) malloc(n*sizeof(int)); 
 Init(A,n);Bubble(A,n); 
 free(A); 
} 
7.5. Giải thuật Shaker Sort 
 Thuật toán Shaker Sort là cải tiến của thuật toán Bubble Sort. Trong đó, sau mỗi 
lần duyệt đi để xếp đúng vị trí phần tử lớn nhất, chúng ta thực hiện duyệt lại để sắp đúng 
vị trí phần tử nhỏ nhất. Dãy sẽ được sắp sau [n/2] + 1 lần duyệt. Chương trình mô tả thuật 
toán Shaker Sort được thực hiện như sau: 
#include 
#include 
#include 
#include 
#include 
void Shaker(int *, int); 
void Init(int *, int); 
void In(int *, int); 
void Init(int *A, int n){ 
 int i; 
PT
IT
 228 
 printf("\n Tao lap day so:"); 
 for (i=0; i<n;i++){ 
 A[i]=random(1000); 
 printf("%5d",A[i]); 
 } 
 delay(1000); 
} 
void Shaker(int *A, int n){ 
 register i,j,temp, exchange; 
 do { 
 exchange=0; 
 for (i=n-1; i>0; i--){ 
 if (A[i-1]>A[i]){ 
 temp=A[i-1]; 
 A[i-1]=A[i]; 
 A[i]=temp; 
 exchange=1; 
 } 
 } 
 for(j=1; j<n;j++){ 
 if (A[j-1]>A[j]){ 
 temp=A[j-1]; 
 A[j-1]=A[j]; 
 A[j]=temp; 
 exchange=1; 
 } 
 } 
 printf("\n Ket qua lan:"); 
 In(A,n); 
 }while(exchange); 
} 
void In(int *A, int n){ 
 register int i; 
 for(i=0;i<n;i++) 
 printf("%5d",A[i]); 
 delay(1000); 
} 
void main(void){ 
 int *A,n;clrscr(); 
 printf("\n Nhap n="); scanf("%d",&n); 
 A=(int *) malloc(n*sizeof(int)); 
 Init(A,n);Shaker(A,n); 
 free(A); 
PT
IT
 229 
} 
7.6. Giải thuật Quick Sort 
 Phương pháp sắp xếp kiểu phân đoạn là một cải tiến của phương pháp Selection 
Sort. Đây là một phương pháp tốt do C.A.R. Hoare đưa ra và đặt tên cho nó là giải thuật 
Quick Sort. 
 Nội dung chủ đạo của phương pháp này là chọn ngẫu nhiên một phần tử nào đó 
của dãy làm khoá chốt. Tính từ khoá chốt, các phần tử nhỏ hơn khoá phải được xếp vào 
trước chốt (đầu dãy), mọi phần tử sau chốt được xếp vào sau chốt (cuối dãy). Để làm 
được việc đó, các phần tử trong dãy sẽ được so sánh với khoá chốt và tráo đổi vị trí cho 
nhau, hoặc cho khoá chốt nếu phần tử đó lớn hơn chốt mà lại nằm trước chốt hoặc nhỏ 
hơn chốt nhưng lại nằm sau chốt. Khi việc đổi chỗ lần đầu tiên đã thực hiện xong thì dãy 
hình thành hai đoạn: một đoạn bao gồm các phần tử nhỏ hơn chốt, một đoạn gồm các 
phần tử lớn hơn chốt, còn chốt chính là vị trí của phần tử trong dãy được sắp xếp. 
 áp dụng kỹ thuật như trên cho mỗi đoạn trước chốt và sau chốt cho tới khi các 
đoạn còn lại hai phần tử thì việc ghi nhớ không còn cần thiết nữa. Dãy sẽ được sắp xếp 
khi tất cả các đoạn được xử lý xong. Ví dụ với dãy : 
42 23 74 11 65 58 94 36 99 87 
Ta chọn chốt đầu tiên là 42. Để phát hiện ra hai khoá cần đổi chỗ cho nhau, ta 
dùng hai biến i, j với giá trị ban đầu i=2, j=10. Nếu ki < 42 thì tiếp tục tăng i và lặp lại cho 
tới khi gặp phần tử thứ ki >42. Duyệt các phần tử thứ kj với 42 nếu kj > 42 thì j giảm đi 
một, cho tới khi gặp phần tử thứ kj <42 thì phần tử thứ ki và kj được đổi chỗ cho nhau. 
Quá trình sẽ được lặp lại với ki và kj cho tới khi i=j chính là vị trí dành cho khoá 42. Cuối 
cùng chúng ta đổi chỗ 42 cho khoá cho kj. 
42 23 74 11 65 58 94 36 99 87 
 42 23 74 11 65 58 94 36 99 87 
42 23 36 11 65 58 94 74 99 87 
42 23 36 11 65 58 94 74 99 87 
42 23 36 11 65 58 94 74 99 87 (i>j) 
11 23 36 42 65 58 94 74 99 87 
PT
IT
 230 
 Như vậy, kết thúc lần thứ nhất, chúng ta được hai đoạn được phân biệt bởi khoá 42 
như sau: 
(11 23 36) [42] (65 58 94 74 99 87) 
 Quá trình được lặp lại tương tự cho từng phân đoạn cho tới khi dãy được sắp xếp 
hoàn toàn. Chúng ta có thể cài đặt giải thuật bằng việc sử dụng stack hoặc đệ qui. 
 Độ phức tạp tính toán của giải thuật Quick Sort: 
 Trường hợp tốt nhất Cmax = Ctb = O (n log2n) 
 Truờng hợp xấu nhất Cmin= k.O(n2) 
Sau đây là chương trình cài đặt giải thuật Quick Sort bằng phương pháp đệ qui. 
#include 
#include 
#include 
#include 
#include 
void qs(int *, int ,int); 
void Quick(int *,int ); 
void Init(int *, int); 
void In(int *, int); 
void Init(int *A, int n){ 
 int i; 
 printf("\n Tao lap day so:"); 
 for (i=0; i<n;i++){ 
 A[i]=random(1000); 
 printf("%5d",A[i]); 
 } 
 delay(1000); 
} 
void Quick(int *A, int n){ 
 qs(A,0,n-1); 
} 
void qs(int *A, int left,int right) { 
 register i,j;int x,y; 
 i=left; j=right; 
 x= A[(left+right)/2]; 
 do { 
 while(A[i]<x && i<right) i++; 
 while(A[j]>x && j>left) j--; 
 if(i<=j){ 
PT
IT
 231 
 y=A[i];A[i]=A[j];A[j]=y; 
 i++;j--; 
 } 
 } while (i<=j); 
 if (left<j) qs(A,left,j); 
 if (i<right) qs(A,i,right); 
} 
void In(int *A, int n){ 
 register int i; 
 for(i=0;i<n;i++) 
 printf("%5d",A[i]); 
 delay(1000); 
} 
void main(void){ 
 int *A,n;clrscr(); 
 printf("\n Nhap n="); scanf("%d",&n); 
 A=(int *)malloc(n*sizeof(int)); 
 Init(A,n);Quick(A,n);printf("\n"); 
 In(A,n);getch(); 
 free(A); 
} 
7.7. Giải thuật Heap Sort 
 Heap là một cây nhị phân được biểu diễn bằng một mảng, mảng đó biểu diễn một 
cây nhị phân hoàn chỉnh sao cho khóa ở node cha bao giờ cũng lớn hơn khoá của node 
con của nó. 
Sắp xếp kiểu Heap Sort được tiến hành qua hai giai đoạn. Giai đoạn đầu tiên cây 
nhị phân biểu diễn bảng khoá được biến đổi để đưa về một heap. Như vậy, đối với heap, 
nếu j là chỉ số của node con thì [j/2] là chỉ số của node cha. Theo định nghĩa của heap thì 
node con bao giờ cũng nhỏ hơn node cha. Như vậy, node gốc của heap là khóa có giá trị 
lớn nhất trong mọi node. Ví dụ cây ban đầu là cây 7.1a thì heap của nó là 7.1b. 
PT
IT
 232 
 Hình 7.1a 
 Hình 7.1b 
Để chuyển cây nhị phân 7.1a thành cây nhị phân 7.1b là một heap, chúng ta thực 
hiện duyệt từ dưới lên (bottom up). Node lá đương nhiên là một heap. Nếu cây con bên 
trái và cây con bên phải đều là một heap thì toàn bộ cây cũng là một heap. Như vậy, để 
tạo thành heap, chúng ta thực hiện so sánh nội dung node bên trái, nội dung node bên phải 
với node cha của nó, node nào có giá trị lớn hơn sẽ được thay đổi làm nội dung của node 
cha. Quá trình lần ngược lại cho tới khi gặp node gốc, khi đó nội dung node gốc chính là 
khoá có giá trị lớn nhất. 
 Giai đoạn thứ hai của giải thuật là đưa nội dung của node gốc về vị trí cuối cùng và 
nội dung của node cuối cùng được thay vào vị trí node gốc, sau đó coi như node cuối 
cùng như đã bị loại bỏ vì thực tế node cuối cùng là giá trị lớn nhất trong dãy số. 
 Cây mới được tạo ra (không kể phần tử loại bỏ) không phải là một heap, chúng ta 
lại thực hiện vun thành đống và thực hiện tương tự như trên cho tới khi đống còn một 
phần tử là phần tử bé nhất của dãy. 
 Độ phức tạp thuật toán của Heap Sort 
Cmax = Ctb = O (n log2n ) 
 Giải thuật Heap Sort được cài đặt như sau: 
#include 
#include 
#include 
#include 
#include 
void Heap(int *, int ); 
42 
23 74 
11 58 65 94 
36 87 99 
99 
87 94 
36 58 65 74 
23 42 11 
PT
IT
 233 
void Init(int *, int); 
void In(int *, int); 
void Init(int *A, int n){ 
 int i; 
 printf("\n Tao lap day so:"); 
 for (i=0; i<n;i++){ 
 A[i]=random(1000); 
 printf("%5d",A[i]); 
 } 
 delay(1000); 
} 
void Heap(int *A, int n) { 
 int k,x,s,f,ivalue; 
 for(k=1;k<n;k++){ 
 x=A[k]; 
 s=k; f=(s-1)/2; 
 while(s>0 && A[f]<x){ 
 A[s]=A[f]; 
 s=f; f=(s-1)/2; 
 } 
 A[s]=x; 
 } 
 for(k=n-1;k>0;k--){ 
 ivalue=A[k]; 
 A[k]=A[0]; 
 f=0; 
 if(k==1) 
 s=-1; 
 else 
 s=1; 
 if(k>2 && A[2]>A[1]) 
 s=2; 
 while(s>=0 && ivalue<A[s]){ 
 A[f]=A[s]; 
 f=s;s=2*f +1; 
 if (s+1<=k-1 && A[s]<A[s+1]) 
 s=s+1; 
 if (s>k-1) 
 s=-1; 
 } 
 A[f]=ivalue; 
 } 
} 
PT
IT
 234 
void In(int *A, int n){ 
 register int i; 
 for(i=0;i<n;i++) 
 printf("%5d",A[i]); 
 delay(1000); 
} 
void main(void){ 
 int *A,n;clrscr(); 
 printf("\n Nhap n="); scanf("%d",&n); 
 A=(int *) malloc(n*sizeof(int)); 
 Init(A,n);Heap(A,n);printf("\n"); 
 In(A,n);getch(); 
 free(A); 
} 
7.8. Giải thuật Merge Sort 
 Sắp xếp theo Merge Sort là phương pháp sắp xếp bằng cách trộn hai danh sách đã 
được sắp xếp thành một danh sách đã được sắp xếp. Phương pháp Merge Sort được tiến 
hành thông qua các bước như sau: 
 Bước 1: Coi danh sách là n danh sách con mỗi danh sách con gồm một phần tử, 
như vậy các danh sách con đã được sắp xếp. Trộn từng cặp hai danh sách con kế cận 
thành một danh sách có hai phần tử đã được sắp xếp, chúng ta nhận được n/2 danh sách 
con đã được sắp xếp. 
 Bước 2: Xem danh sách cần sắp xếp như n/2 danh sách con đã được sắp xếp. Trộn 
cặp hai danh sách kế cận thành từng danh sách có 4 phần tử đã được sắp xếp, chúng ta 
nhận được n/4 danh sách con. 
 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 Bước thứ i: Làm tương tự như bước i- 1. Quá trình được tiếp tục khi chúng ta 
nhận được danh sách có n phần tử đã được sắp xếp. Ví dụ với dãy: 
42 23 74 11 68 58 94 36 
lần 1: [23 42] [11 74] [58 68] [94 36] 
lần 2: [11 23 42 74] [36 58 68 94] 
lần 3: [11 23 42 36 58 68 74 94] 
PT
IT
 235 
 Chương trình cài đặt giải thuật Merge Sort được thực hiện như sau: 
#include 
#include 
#include 
#include 
#include 
#define MAX 10 
void Merge(int *, int ); 
void Init(int *, int); 
void In(int *, int); 
void Init(int *A, int n){ 
 int i; 
 printf("\n Tao lap day so:"); 
 for (i=0; i<n;i++){ 
 A[i]=random(1000); 
 printf("%5d",A[i]); 
 } 
 delay(1000); 
} 
void Merge(int *A, int n) { 
 int i,j,k,low1,up1,low2,up2,size; 
 int *dstam;size=1;dstam=(int *) malloc(n*sizeof(int)); 
 while(size<n){ 
 low1=0;k=0; 
 while(low1 +size <n){ 
 low2=low1+size; up1=low2-1; 
 if (low2+size-1< n) 
 up2=low2+size-1; 
 else 
 up2=n-1; 
 for(i=low1, j=low2; i<=up1 && j<=up2; k++){ 
 if(A[i]<=A[j]) 
 dstam[k]=A[i++]; 
 else 
 dstam[k] =A[j++]; 
 } 
 for(;i<=up1;k++) 
 dstam[k]=A[i++]; 
 for(;j<=up2;k++) 
 dstam[k]=A[j++]; 
 low1=up2+1; 
 } 
 for (i=low1; k<n;i++) 
PT
IT
 236 
 dstam[k++]=A[i]; 
 for(i=0;i<n;i++) 
 A[i]=dstam[i]; 
 size*=2; 
 } 
 printf("\n Ket qua:"); 
 In(A,n);free(dstam); 
} 
void In(int *A, int n){ 
 register int i; 
 for(i=0;i<n;i++) 
 printf("%5d",A[i]); 
 delay(1000); 
} 
void main(void){ 
 int *A,n;clrscr(); 
 printf("\n Nhap n="); scanf("%d",&n); 
 A=(int *) malloc(n*sizeof(int)); 
 Init(A,n);Merge(A,n);printf("\n"); 
 free(A); 
} 
7.9. Tìm kiếm (Searching) 
 Tìm kiếm là công việc quan trọng đối với các hệ thống tin học và có liên quan mật 
thiết với quá trình sắp xếp dữ liệu. Bài toán tìm kiếm tổng quát có thể được phát biểu như 
sau: 
 “ Cho một bảng gồm n bản ghi R1, R2, . ., Rn. Với mỗi bản ghi Ri được tương ứng 
với một khoá ki (trường thứ i trong record). Hãy tìm bản ghi có giá trị của khoá bằng X 
cho trước”. 
 Nếu chúng ta tìm được bản ghi có giá trị khóa là X thì phép tìm kiếm được thoả 
(successful). Nếu không có giá trị khóa nào là X, thì quá trình tìm kiếm là không thoả 
(unsuccessful). Sau quá trình tìm kiếm, có thể xuất hiện yêu cầu bổ xung thêm bản ghi 
mới có giá trị khóa là X thì giải thuật được gọi là giải thuật tìm kiếm bổ sung. 
7.9.1. Tìm kiếm tuần tự (Sequential Searching) 
 Tìm kiếm tuần tự là kỹ thuật tìm kiếm cổ điển trên một danh sách chưa được sắp 
xếp. Nội dung cơ bản của phương pháp tìm kiếm tuần tự là duyệt từ bản ghi thứ nhất cho 
tới bản ghi cuối cùng, và so sánh lần lượt giá trị của khoá với giá trị X cần tìm. Trong quá 
PT
IT
 237 
trình duyệt, nếu có bản ghi trùng với giá trị X thì chúng ta đưa ra vị trí của bản ghi trong 
dãy, nếu duyệt tới cuối dãy mà không có bản ghi nào có giá trị của khoá trùng với X thì 
quá trình tìm kiếm trả lại giá trị -1 (-1 được hiểu là giá trị khoá X không thuộc dãy). 
Chương trình cài đặt phương pháp tìm kiếm tuần tự được thực hiện như sau: 
#include 
#include 
#include 
#include 
#include 
int Sequential(int *, int, int); 
void Init(int *, int); 
void Init(int *A, int n){ 
 int i; 
 printf("\n Tao lap day so:"); 
 for (i=0; i<n;i++){ 
 A[i]=random(1000); 
 printf("%5d",A[i]); 
 } 
 delay(1000); 
} 
int Bubble(int *A, int x, int n){ 
 register i,temp; 
 for (i=0; i<n ; i ++){ 
 if (A[i] == X) 
 return(i); 
 } 
 return(-1); 
} 
void main(void){ 
 int *A,n, x, k;clrscr(); 
 printf("\n Nhap n="); scanf("%d",&n); 
 printf(“\n Số x cần tìm:”); scanf(“%d”, &x); 
 A=(int *) malloc(n*sizeof(int)); 
 k= Sequential(A,x,n); 
 if ( k>=0) 
 printf(“\n %d ở vị trí %d”, x,k); 
 else 
 printf(“\n %d không thuộc dãy”); 
 free(A); getch(); 
} 
7.9.2. Tìm kiếm nhị phân (Binary Searching) 
PT
IT
 238 
 Tìm kiếm nhị phân là phương pháp tìm kiếm phổ biến được thực hiện trên một dãy 
đã được sắp thứ tự. Nội dung của giải thuật được thực hiện như sau: lấy khóa cần tìm 
kiếm X so sánh với nội dung của khóa của phần tử ở giữa, vị trí của phần tử ở giữa là mid 
= (low + hight )/ 2, trong đó cận dưới low =0, cận trên hight = n-1. Vì dãy đã được sắp 
xếp nên nếu nội dung của khóa tại vị trí giữa lớn hơn X thì phần tử cần tìm thuộc khoảng 
[mid+1, hight], nếu nội dung của khóa tại vị trí giữa nhỏ hơn X thì phần tử cần tìm thuộc 
khoảng [low, mid-1], nếu nội dung của khóa tại vị trí giữa trùng với X thì đó chính là 
phần tử cần tìm. ở bước tiếp theo, nếu nội dung của khóa tại vị trí giữa lớn hơn X thì ta 
dịch chuyển cận dưới low lên vị trí mid+ 1, nếu nội dung của khóa tại vị trí giữa nhỏ hơn 
X thì ta dịch chuyển cận trên về vị trí mid- 1. Quá trình được lặp lại cho tới khi gặp khóa 
có nội dung trùng với X hoặc cận dưới vượt quá cận trên hay X không thuộc dãy. Thuật 
toán tìm kiếm nhị phân được minh họa như sau: 
int Binary_Search( int *A, int X, int n){ 
 int mid, low=0, hight = n-1; 
 while ( low<=hight ){ // lặp nếu cận dưới vẫn nhỏ hơn cận trên 
 mid = (low + hight) /2; // xác định vị trí phần tử ở giữa 
 if (X > A[mid] ) low = mid +1; // X thuộc [mid+1, hight] 
 else if (X < A[mid] ) hight = mid- 1; // X thuộc [low, mid-1] 
 else return(mid); 
 } 
 return(-1); // X không thuộc dãy 
} 
 Chương trình cụ thể được cài đặt như sau: 
#include 
#include 
#include 
#include 
#include 
int Binary_Search( int *, int, int); 
void Bubble(int *, int); 
void Init(int *, int); 
int Binary_Search( int *A, int X, int n) { 
 int mid, low = 0, hight = n-1; 
 while (low<=hight){ 
 mid = (low +hight)/2; 
PT
IT
 239 
 if (X >A[mid] ) low = mid +1; 
 else if (X<A[mid] ) hight = mid -1; 
 else return (mid); 
 } 
 return(-1); 
} 
void Init(int *A, int n){ 
 int i; 
 printf("\n Tao lap day so:"); 
 for (i=0; i<n;i++){ 
 A[i]=random(1000); 
 printf("%5d",A[i]); 
 } 
 delay(1000); 
} 
void Bubble(int *A, int n){ 
 register i,j,temp; 
 for (i=1; i<n; i++){ 
 for (j=n-1; j>=i;j--){ 
 if (A[j-1]>A[j]){ 
 temp=A[j-1]; 
 A[j-1]=A[j]; 
 A[j]=temp; 
 } 
 } 
 printf("\n Ket qua lan:%d", i); 
 In(A,n); 
 } 
} 
void In(int *A, int n){ 
 register int i; 
 for(i=0;i<n;i++) 
 printf("%5d",A[i]); 
 delay(1000); 
} 
void main(void){ 
 int *A,n, X, k;clrscr(); 
 printf("\n Nhap n="); scanf("%d",&n); 
 printf(“\n Số cần tìm X=”); scanf(“%d”,&X); 
 A=(int *) malloc(n*sizeof(int)); 
 Init(A,n);Bubble(A,n); k= Binary_Search(A, X, n); 
 if ( k>0) 
 printf (“\n %d ở vị trí số %d”, X, k); 
PT
IT
 240 
 else 
 printf(“\n %d không thuộc dãy”); 
 getch(); 
 free(A); 
} 
PT
IT
 241 
BÀI TẬP CHƯƠNG 7 
7.1. Cài đặt chương trình theo thuật toán Quick Sort không dùng phương pháp đệ qui 
mà dùng cấu trúc stack. 
7.2. Tìm hiểu về giải thuật Shell-Sort là phương pháp cải tiến của Insertion Sort. 
7.3. Cài đặt lại giải thuật Bubble Sort sao cho các node nhỏ được đẩy dần về phía 
trước. 
7.4. Một Ternary Heap là cây tam phân gần đầy được cài đặt bằng mảng một chiều, 
mỗi node có ba node con. Nội dung của node cha bao giờ cũng lớn hơn hoặc bằng 
nội dung của node con, các node được đánh số từ 0 đến n-1, node i có 3 con là 
3i+1, 3i+2, 3i+3. Hãy cài đặt giải thuật Ternary Heap. 
7.5. Cài đặt giải thuật Bubble Sort trên file. 
7.6. Cài đặt giải thuật Insertion Sort trên file. 
7.7. Cài đặt giải thuật Quick Sort trên file. 
7.8. Cài đặt các giải thuật sắp xếp theo nhiều khoá khác nhau. 
7.9. Nghiên cứu và cài đặt thuật toán tìm kiếm tam phân. 
7.10. Nghiên cứu và cài đặt thuật toán sắp xếp kiểu hoà nhập thực hiện trên file. 
7.11. Viết chương trình chuyển đổi một file dữ liệu được tổ chức theo khuôn dạng 
*.DBF thành file kiểu text. Ngược lại, chuyển đổi file dữ liệu kiểu text thành một 
file dữ liệu theo khuôn dạng DBF. 
7.12. Tìm hiểu cách sắp xếp và tìm kiếm theo kiểu index của các hệ quản trị cơ sở dữ 
liệu như foxprol hoặc access. 
PT
IT