A
B
C
D
F
G
E
H
K
C U TRÚC D LI U VÀ Ấ Ữ Ệ
C U TRÚC D LI U VÀ Ấ Ữ Ệ
GI I THU T (501040)Ả Ậ
GI I THU T (501040)Ả Ậ
Ch ng 8: S p th tươ ắ ứ ự
Ch ng 8: S p th tươ ắ ứ ự
ĐH Bách Khoa Tp.HCM Ch ng 8. S p th tươ ắ ứ ự 2
Khoa Công ngh Thông tinệ
Khái ni mệ
S p th t :ắ ứ ự
Đ u vào: m t danh sáchầ ộ
Đ u ra: danh sách có th t tăng (ho c gi m) trên ầ ứ ự ặ ả
khóa
Phân lo i:ạ
S p th t ngo i (external sort): t p tinắ ứ ự ạ ậ
S p th t n i (internal sort): b nhắ ứ ự ộ ộ ớ
Gi thi t: ả ế
S p th t n iắ ứ ự ộ
S p tăng d nắ ầ
ĐH Bách Khoa Tp.HCM Ch ng 8. S p th tươ ắ ứ ự 3
Khoa Công ngh Thông tinệ
Insertion sort
ĐH Bách Khoa Tp.HCM Ch ng 8. S p th tươ ắ ứ ự 4
Khoa Công ngh Thông tinệ
Insertion sort - Danh sách liên t cụ
ĐH Bách Khoa Tp.HCM Ch ng 8. S p th tươ ắ ứ ự 5
Khoa Công ngh Thông tinệ
Gi i thu t insertion sort – Danh sách ả ậ
liên t cụ
Algorithm Insertion_sort
Input: danh sách c n s p th tầ ắ ứ ự
Output: danh sách đã đ c s p th tượ ắ ứ ự
1. for first_unsorted = 1 to size
//Tìm v trí h p lý đ chèn giá tr đang có vàoị ợ ể ị
1.1. current = list[first_unsorted]
1.2. position = first_unsorted
1.3. while (position>0 and list[position - 1] > current)
//D i ch các ph n t l n v sauờ ỗ ầ ử ớ ề
1.3.1. list[position] = list[position - 1]
1.3.2. position = position - 1
//Chép ph n t tr c đó vào đúng v trí c a nóầ ử ướ ị ủ
1.4. list[position - 1] = current
End Insertion_sort