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 ch liên t c
Ch ng 8: S p th tươ
5
Gi i thu t insertion sort – Danh 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 ướ
1.4. list[position - 1] = current
End Insertion_sort