C U TRÚC D LI U VÀ Ấ Ữ Ệ
GI I THU TẢ Ậ
Ch ng 8: S p th tươ ắ ứ ự
Ch ng 8: S p th tươ ắ ứ ự
2
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ắ ầ
Ch ng 8: S p th tươ ắ ứ ự
3
Insertion sort
Ch ng 8: S p th tươ ắ ứ ự
4
Insertion sort - Danh sách liên t cụ
Ch ng 8: S p th tươ ắ ứ ự
5
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