: N N T NG LÝ THUY T
PH N AẦ
Ả
Ề
Ế
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 ữ ệ ữ ả
đây ta ch quan tâm đ n 2 Có r t nhi u cách s p x p d li u,nh ng ắ ữ ệ ư ề ế ấ ở ế ỉ
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 ứ ạ ế ộ
i thu t. gian tính toán(trên th c nghi m) c a 2 gi ự ủ ệ ả ậ
i thu t s p x p b ng ph ng pháp ộ ứ ạ ủ ả ậ ắ ế ằ ươ
2. Đánh giá đ ph c t p c a gi
chèn(Insertion Sort) 2.1.Ý t ng thu t toán: ậ ưở
1, a2, …, ai đã có
đ u tiên a
a ả ử ứ ự ầ ử ầ ợ ị ậ
1, a2, …, an trong đó i ph n t s ta có dãy a Gi th t . Ý t ủ ưở vào dãy đã có th t ứ ự đ n cu i dãy ta s đ ẽ ượ ế
c m t dãy m i có th t ầ ử i+1 . C th , làm ượ ớ
ng c a thu t toán là tìm v tr thích h p và chèn ph n t ị ộ ứ ự ứ ế . c m t dãy có th t ứ ự trên đ có đ ể ộ ố
ầ 1, a2, …, an ta có th coi đo n ch có m t ph n t ể ỉ ạ
a ầ ử 1 là a ể
ứ ự . Ti p đó, ta l i chèn ph n t a ế ầ ử 3 vào dãy a1a2 đ có dãy a
1a2…an có th t
a ộ 1a2 ầ ử 2 vào dãy a1 đ có dãy a 1a2a3 có ể ầ ử n vào dãy a1a2…an-1 ta sẽ
Insertion Sort và Quick Sort
Trang 1
c dãy a V i dãy ban đ u a ớ m t đo n đã có th t ạ ộ có th t ứ ự th t ứ ự ứ ế ế đ ượ , sau đó ta chèn ph n t ạ . C th , đ n cu i cùng ta chèn ph n t ố .ứ ự
2.2.Cài đ t thu t toán ặ ậ
void insertionsort(int a[],int n)
{
int pos,x;
for(int i=0;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:
ư ng h p t t nh t: . Ta tìm đ ườ ợ ố ấ Dãy ban đ u đã có th t
ầ ứ ự ượ
c ngay v trí thích h p đ chèn ngay l n so sánh đ u tiên mà không ể ầ ầ ợ ị 2 đ n n thì s phép so c n ph i vô vòng l p. Nh v y, v i i ch y t
ầ ư ậ ạ ừ ả ặ ớ ế ố 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 ổ Insertion Sort và Quick Sort Trang 2 b ng 2(n - 1).
ằ ng ườ ng h p x u nh t:
ấ ấ Dãy ban đ u có th t ứ ự ợ ầ ượ ấ
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 2) • Tr ng h p t t nh t: O(n) ườ ợ ố ấ 3. Đánh giá đ ph c t p c a gi ườ ng h p x u nh t O(n
ấ ấ ợ 3.1. Ý t i thu t s p x p nhanh(Quick Sort) ộ ứ ạ ủ ả ậ ắ ế ưở ng thu t toán:
ậ đ ộ ừ
c g i là ph n t
ầ ử ầ ử ượ ọ
c đ a v phía tr ả
ớ
ỏ ơ nh h n ho c b ng ph n t
ặ ầ ử ằ
c ch n đ
ọ
ượ
ch t đ
ầ ử ố ượ ư ề
ầ ử ớ l n h n ch t đ
ơ ứ ằ ứ ế ụ ứ ộ QuickSort chia m ng thành hai danh sách b ng cách so sánh t ng ph n
ầ
c a danh sách v i m t ph n t
ch t.
t
ố
ử ủ
ướ
c
Nh ng ph n t
ằ
ữ
ố ượ ư
và n m trong danh sách con th nh t, các ph n t
c đ a
ấ
ư ậ ớ
i
v phía sau và thu c danh sách con th hai. C ti p t c chia nh v y t
ề
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
{ Insertion Sort và Quick Sort Trang 3 while(a[i] { swap(a[i],a[j]);
i++; j--;
}
}while(i 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
ị ố
ệ
ấ
ậ
ch t).
(hay ph n t
ầ ử ố 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 ầ ử ầ ử ớ ử ố ầ ử ằ ơ ỏ còn l i) làm m c. Khi đó dãy đ h n hay b ng n a s ph n t
ơ ử ố ầ ử ằ ạ ố ượ
c 2(n) l n phân
ầ phân ho ch thành hai ph n b ng nhau, và ta c n log ạ ầ ằ ầ ho ch thì s p x p xong. Ta cũng d nh n th y trong m i l n phân ỗ ầ ế ễ ạ ắ ậ ấ 2(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
ộ ấ 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 ầ 2). 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
ộ i, ta có đ ph c t p c a Quick Sort nh sau: ế ạ ổ ộ ứ ạ ủ ư 2(n)) • Tr T ng k t l
• Tr ng h p t t nh t: O(nlog ườ ợ ố ấ 2) • Tr ng h p x u nh t: O(n ườ ợ ấ ấ 2(n)) Insertion Sort và Quick Sort Trang 4 ng h p trung bình: O(nlog ườ ợ 1. Mô t i thu t : gi
ả ả ậ 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 i thu t nh sau: đ t gi
ặ ả ư ậ 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 { j=k+1; X=A1[j]; while(X Insertion Sort và Quick Sort Trang 5 { sosanhI++; A1[j]=A1[j-1]; hoanviI++; j--; } A1[j]=X; k++; } } 2.2.QuickSort void quicksort(int A2[],int first,int last,int &sosanhQ,int &hoanviQ)
{ if(first>=last)
return;
int mid=(first+last)/2;
int MID=A2[mid];
int F=first,L=last;
while(F<=L)
{ while(A2[F] F++;
sosanhQ++; }
while(A2[L]>MID) L--; if(F<=L)
{ Insertion Sort và Quick Sort Trang 6 doicho(A2[F],A2[L]);
F++;
L--; hoanviQ++; } }
cout.flush();
quicksort(A2,first,L,sosanhQ,hoanviQ);
cout.flush();
quicksort(A2,F,last,sosanhQ,hoanviQ); } 3. K t qu th c nghi m:
ả ự ế ệ Insertion Sort và Quick Sort Trang 7 Insertion Sort và Quick Sort Trang 8 Insertion Sort và Quick Sort Trang 9 Insertion Sort và Quick Sort Trang 10 Insertion Sort và Quick Sort Trang 11 D a vào ph ng trình h i qui tuy n tính c a Phép Hoán v (Gán) ự ươ ủ ế ồ ị InsertionSort và ph ng trình h i qui tuy n tính Phép Hoán v (Gán) ươ ế ồ ị QuickSort ; ph ng trình h i qui tuy n tính c a Phép So sánh InsertionSort và ươ ủ ế ồ ph ươ ủ
ng trình h i qui tuy n tính Phép So Sánh QuickSort,ta th y h s α c a ệ ố ế ấ ồ gi i thu t QuickSort nh h n h s α c a gi i thu t InsertionSort,đi u này ả ỏ ơ ệ ố ủ ậ ả ề ậ i thu t QuickSort ch y nhanh h n gi i thu t InsertSort.Ngoài ch ng t
ứ gi
ỏ ả ậ ạ ơ ả ậ ra,đ th bi u di n các ph ng trình h i qui tuy n tính c a 2 gi ồ ị ể ễ ươ ủ ế ồ ả i thu t cũng
ậ i thu t QuickSort ch y nhanh h n gi i thu t InsertionSort. cho th y r ng gi
ấ ằ ả ậ ạ ơ ả ậ Ph n lý thuy t cũng cho th y đ ph c t p c a gi i thu t InsertionSort ộ ứ ạ ủ ế ầ ấ ả ậ i thu t QuickSort. l n h n ho c b ng đ ph c t p c a gi
ớ ộ ứ ạ ủ ặ ằ ơ ả ậ Nhóm chúng em s c g ng tìm hi u sâu s c h n đ hi u rõ v hai gi
ể ẽ ố ắ ắ ơ ể ể ề ả
i thu t này,trong quá trình làm không tránh kh i thi u xót,kính mong Th y b ế ầ ậ ỏ ỏ qua. Insertion Sort và Quick Sort Trang 12 Xin chân thành c m n. ả ơ2.3.1. Tr
2.3.2. Tr
3.3.1. Tr
3.3.2. Tr
PH N B : TH C NGHI M
Ự
Ầ
Ệ
B ng s li u thu đư c khi chương trình ch y
ố
ợ
ệ
ạ
ả
K T LU N
Ậ
Ế
