PH N AẦ: N N T NG LÝ THUY TỀ Ả Ế
1. Mô t ch c năng và yêu c uả ứ ầ
1.1.Khái quát v s p x p:ề ắ ế
Đ thu n ti n và gi m thi u th i gian thao tác mà đ c bi t là đ tìmể ậ ệ ả ể ờ ặ ệ ể
ki m d li u d dàng và nhanh chóng,thong th ng tr c khi thao tác thìế ữ ệ ễ ườ ướ
d li u trên m ng,trên t p tin đã có th t .Do v y thao tác s p x p d li uữ ệ ả ậ ứ ự ậ ắ ế ữ ệ
là m t trong nh ng thao tác c n thi t và th ng g p trong quá trình l uộ ữ ầ ế ườ ặ ư
tr ,qu n lý d li uữ ả ữ ệ
Có r t nhi u cách s p x p d li u,nh ng đây ta ch quan tâm đ n 2ấ ề ắ ế ữ ệ ư ở ỉ ế
thu t toán là s p x p b ng ph ng pháp chèn (Insertion Sort) và s p x pậ ắ ế ằ ươ ắ ế
d a trên s phân ho ch (Quick Sort).Ta s đi phân tích hai thu t toán s pự ự ạ ẽ ậ ắ
x p này đ so sánh và đánh giá đ ph c t p c a chúng.ế ể ộ ứ ạ ủ
1.2.M c tiêu c a bài toán:ụ ủ
Phân tích,đánh giá và so sánh đ ph c t p(trên lý thuy t) và so sánh th iộ ứ ạ ế ờ
gian tính toán(trên th c nghi m) c a 2 gi i thu t.ự ệ ủ ả ậ
2. Đánh giá đ ph c t p c a gi i thu t s p x p b ng ph ng phápộ ứ ạ ủ ả ậ ắ ế ằ ươ
chèn(Insertion Sort)
2.1.Ý t ng thu t toán:ưở ậ
Gi s ta có dãy aả ử 1, a2, …, an trong đó i ph n t đ u tiên aầ ử ầ 1, a2, …, ai đã có
th t . Ý t ng c a thu t toán là tìm v tr thích h p và chèn ph n t aứ ự ưở ủ ậ ị ị ợ ầ ử i+1
vào dãy đã có th t trên đ có đ c m t dãy m i có th t . C th , làmứ ự ể ượ ộ ớ ứ ự ứ ế
đ n cu i dãy ta s đ c m t dãy có th t .ế ố ẽ ượ ộ ứ ự
V i dãy ban đ u aớ ầ 1, a2, …, an ta có th coi đo n ch có m t ph n t aể ạ ỉ ộ ầ ử 1 là
m t đo n đã có th t , sau đó ta chèn ph n t aộ ạ ứ ự ầ ử 2 vào dãy a1 đ có dãy aể1a2
có th t . Ti p đó, ta l i chèn ph n t aứ ự ế ạ ầ ử 3 vào dãy a1a2 đ có dãy aể1a2a3 có
th t . C th , đ n cu i cùng ta chèn ph n t aứ ự ứ ế ế ố ầ ử n vào dãy a1a2…an-1 ta sẽ
đ c dãy aượ 1a2…an có th t .ứ ự
Insertion Sort và Quick Sort Trang 1
2.2.Cài đ t thu t toánặ ậ
void insertionsort(int a[],int n)
{
int pos,x;
for(int i=0;i<n-1;i++)
{
x=a[i+1];pos=i;
while(pos>=0 && a[pos]>x)
{
a[pos+1]=a[pos];
pos--;
}
a[pos+1]=x;
}
}
2.3.Đánh giá đ ph c t p:ộ ứ ạ
Ta th y các phép so sánh x y ra trong vòng l p nh m tìm v trí thích h pấ ả ặ ằ ị ợ
pos đ chèn x. M i l n so sánh mà th y v trí đang xét không thích h p, ta d iể ỗ ầ ấ ị ợ ờ
ph n t a[pos] sang ph i.ầ ử ả
Ta cũng th y s phép gán và s phép so sánh c a thu t toán ph thu c vàoấ ố ố ủ ậ ụ ộ
tình tr ng c a dãy ban đ u. Do đó ta ch có th c l ng nh sau:ạ ủ ầ ỉ ể ướ ượ ư
2.3.1. Tr ng h p t t nh t: ườ ợ ố ấ Dãy ban đ u đã có th t . Ta tìm đ cầ ứ ự ượ
ngay v trí thích h p đ chèn ngay l n so sánh đ u tiên mà khôngị ợ ể ầ ầ
c n ph i vô vòng l p. Nh v y, v i i ch y t 2 đ n n thì s phép soầ ả ặ ư ậ ớ ạ ừ ế ố
sánh t ng c ng s là n-1. Còn v i s phép gán, do thu t toán khôngổ ộ ẽ ớ ố ậ
ch y vào vòng l p nên xét i b t kỳ, ta luôn ch ph i t n 2 phép gán(xạ ặ ấ ỉ ả ố
= a[i] và a[pos] = x). T đây, ta tính đ c s phép gán t ng c ngừ ượ ố ổ ộ
b ng 2(n - 1).ằ
Insertion Sort và Quick Sort Trang 2
2.3.2. Tr ng h p x u nh t:ườ ợ ấ ấ Dãy ban đ u có th t ng c. Ta th yầ ứ ự ượ ấ
ngay v trí thích h p pos luôn là v trí đ u tiên c a dãy đã có th t ,ị ợ ị ầ ủ ứ ự
và do đó, đ tìm ra v trí này ta ph i duy t h t dãy đã có th t . Xétể ị ả ệ ế ứ ự
i b t kỳ, ta có s phép so sánh là i-1, s phép gán là (i - 1) + 2 = i + 1.ấ ố ố
V i i ch y t 2 đ n n, ta tính đ c s phép so sánh t ng c ng b ngớ ạ ừ ế ượ ố ổ ộ ằ
1 + 2 + … + (n - 1) = n(n - 1)/2 và s phép gán b ng 3 + 4 + .. + (n +ố ằ
1) = (n + 4)(n - 1)/2
T ng k t l i, ta có đ ph c t p c a Insertion Sort nh sau:ổ ế ạ ộ ứ ạ ủ ư
•Tr ng h p t t nh t: O(n)ườ ợ ố ấ
•Tr ng h p x u nh t O(nườ ợ ấ ấ 2)
3. Đánh giá đ ph c t p c a gi i thu t s p x p nhanh(Quick Sort)ộ ứ ạ ủ ả ậ ắ ế
3.1. Ý t ng thu t toán:ưở ậ
QuickSort chia m ng thành hai danh sách b ng cách so sánh t ng ph nả ằ ừ ầ
t c a danh sách v i m t ph n t đ c ch n đ c g i là ph n t ch t.ử ủ ớ ộ ầ ử ượ ọ ượ ọ ầ ử ố
Nh ng ph n t nh h n ho c b ng ph n t ch t đ c đ a v phía tr cữ ầ ử ỏ ơ ặ ằ ầ ử ố ượ ư ề ướ
và n m trong danh sách con th nh t, các ph n t l n h n ch t đ c đ aằ ứ ấ ầ ử ớ ơ ố ượ ư
v phía sau và thu c danh sách con th hai. C ti p t c chia nh v y t iề ộ ứ ứ ế ụ ư ậ ớ
khi các danh sách con đ u có đ dài b ng 1.ề ộ ằ
3.2.Cài đ t thu t toán:ặ ậ
void quicksort(int a[],int left,int right)
{
if(left>=right)return;
int x=a[(left+right)/2];
int i=left;
int j=right;
do
{
while(a[i]<x)i++;
while(a[j]>x)j--;
if(i<=j)//chua duyet het
Insertion Sort và Quick Sort Trang 3
{
swap(a[i],a[j]);
i++;
j--;
}
}while(i<j);
quicksort(a,left,j);
quicksort(a,i,right);
}
3.3.Đ ph c t p c a thu t toánộ ứ ạ ủ ậ
Ta nh n th y hi u qu c a thu t toán ph thu c vào vi c ch n giá tr m cậ ấ ệ ả ủ ậ ụ ộ ệ ọ ị ố
(hay ph n t ch t).ầ ử ố
3.3.1. Tr ng h p t t nh t:ườ ợ ố ấ m i l n phân ho ch ta đ u ch n đ cỗ ầ ạ ề ọ ượ
ph n t median (ph n t l n h n hay b ng n a s ph n t và nhầ ử ầ ử ớ ơ ằ ử ố ầ ử ỏ
h n hay b ng n a s ph n t còn l i) làm m c. Khi đó dãy đ cơ ằ ử ố ầ ử ạ ố ượ
phân ho ch thành hai ph n b ng nhau, và ta c n logạ ầ ằ ầ 2(n) l n phânầ
ho ch thì s p x p xong. Ta cũng d nh n th y trong m i l n phânạ ắ ế ễ ậ ấ ỗ ầ
ho ch ta c n duy t qua n ph n t . V y đ ph c t p trong tr ngạ ầ ệ ầ ử ậ ộ ứ ạ ườ
h p t t nh t thu c O(nlogợ ố ấ ộ 2(n)).
3.3.2. Tr ng h p x u nh t:ườ ợ ấ ấ m i l n ph n ho ch ta ch n ph i ph nỗ ầ ầ ạ ọ ả ầ
t có giá tr c c đ i ho c c c ti u làm m c. Khi đó dãy b phânử ị ự ạ ặ ự ể ố ị
ho ch thành hai ph n không đ u: m t ph n ch có m t ph n t ,ạ ầ ề ộ ầ ỉ ộ ầ ử
ph n còn l i có n-1 ph n t . Do đó, ta c n t i n l n phân ho chầ ạ ầ ử ầ ớ ầ ạ
m i s p x p xong. V y đ ph c t p trong tr ng h p x u nh tớ ắ ế ậ ộ ứ ạ ườ ợ ấ ấ
thu c O(nộ2).
T ng k t l i, ta có đ ph c t p c a Quick Sort nh sau:ổ ế ạ ộ ứ ạ ủ ư
•Tr ng h p t t nh t: O(nlogườ ợ ố ấ 2(n))
•Tr ng h p x u nh t: O(nườ ợ ấ ấ 2)
•Tr ng h p trung bình: O(nlogườ ợ 2(n))
Insertion Sort và Quick Sort Trang 4
PH N B : TH C NGHI MẦ Ự Ệ
1. Mô t gi i thu t :ả ả ậ
Gi i thu t đ c cài đ t trên ngôn ng l p trình c/c++. Ý t ng c a vi cả ậ ượ ặ ữ ậ ưở ủ ệ
cài
đ t gi i thu t nh sau: ặ ả ậ ư
Kh i t o ng u nhiên n ph n t , ghi ra 1 file text ở ạ ẫ ầ ử
Đ c các ph n t t file text vào file excel ọ ầ ử ừ
Tính đ ph c t p d a vào αộ ứ ạ ự
2. Cài đ tặ
2.1.InsertionSort:
void insertionsort(int A1[],int num,int &sosanhI,int &hoanviI)
{
int X=0,k=1,j=0;
while(k<num)
{
j=k+1;
X=A1[j];
while(X<A1[j-1])
{
Insertion Sort và Quick Sort Trang 5