PPSX InsertSort

Nội dung: Phương pháp sắp xếp Insertion sort
GVHD: HUỲNH DƯƠNG TRUNG TRỰC








Sóc Trăng 17/05/2010
BÀI BÁO CÁO
Phân tích thuật toán sắp xếp

* Thuật toán : Insertion Sort
Giải thuật
Nó lần lượt lấy các phần tử của danh sách chèn vào vị trí thích hợp trong một danh sách mới đã được sắp.
Bắt chước cách sắp xếp quân bài của những người chơi bài. Muốn sắp một bộ bài theo trật tự người chơi bài rút lần lượt từ quân thứ 2, so với các quân đứng trước nó để chèn vào vị trí thích hợp.
Giả sử có một dãy a1 , a2 ,... ,an trong đó i phần tử đầu tiên a1 , a2 ,... ,ai-1 đã có thứ tự. Ý tưởng chính của giải thuật sắp xếp bằng phương pháp chèn trực tiếp là tìm cách chèn phần tử ai vào vị trí thích hợp của đoạn đã được sắp để có dãy mới a1 , a2 ,... ,ai trở nên có thứ tự. Vị trí này chính là vị trí giữa hai phần tử ak-1 và ak thỏa ak-1 và ak thỏa ak-1Cho dãy ban đầu a1 , a2 ,... ,an, ta có thể xem như đã có đoạn gồm một phần tử a1 đã được sắp, sau đó thêm a2 vào đoạn a1 sẽ có đoạn a1 a2 được sắp; tiếp tục thêm a3 vào đoạn a1 a2 để có đoạn a1 a2 a3 được sắp; tiếp tục cho đến khi thêm xong aN vào đoạn a1 a2 ...aN-1 sẽ có dãy a1 a2.... aN được sắp.
Phân tích thuật toán sắp xếp

* Thuật toán : Insertion Sort
Các bước tiến hành
Bước 1: i = 2; // giả sử có đoạn a[1] đã được sắp
Bước 2: x = a[i]; Tìm vị trí pos thích hợp trong đoạn a[1] đến a[i-1] để chèn a[i] vào
Bước 3: Dời chỗ các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chổ cho a[i]
Bước 4: a[pos] = x;// có đoạn a[1]..a[i] đã được sắp
Bước 5: i = i+1; Nếu i < n : Lặp lại Bước 2.
Ngược lại : Dừng.
Phân tích thuật toán sắp xếp

* Thuật toán : Insertion Sort
I. Phân tích thuật toán sắp xếp

I.1. Thuật toán : Insertion Sort
Minh họa
1 2 3 4 5 6 7 8 9 10
8
6
34
22
40
5
11
23
44
18
1 2 3 4 5 6 7 8 9 10
6
8
34
22
40
5
11
23
44
18
Minh họa
I. Phân tích thuật toán sắp xếp

I.1. Thuật toán : Insertion Sort
1 2 3 4 5 6 7 8 9 10
6
8
34
22
40
5
11
23
44
18
Minh họa
I. Phân tích thuật toán sắp xếp

I.1. Thuật toán : Insertion Sort
1 2 3 4 5 6 7 8 9 10
6
8
34
22
40
5
11
23
44
18
Minh họa
I. Phân tích thuật toán sắp xếp

I.1. Thuật toán : Insertion Sort
1 2 3 4 5 6 7 8 9 10
6
8
22
34
40
5
11
23
44
18
Minh họa
I. Phân tích thuật toán sắp xếp

I.1. Thuật toán : Insertion Sort
1 2 3 4 5 6 7 8 9 10
6
8
22
34
40
5
11
23
44
18
Minh họa
I. Phân tích thuật toán sắp xếp

I.1. Thuật toán : Insertion Sort
1 2 3 4 5 6 7 8 9 10
6
8
22
34
40
5
11
23
44
18
Minh họa
I. Phân tích thuật toán sắp xếp

I.1. Thuật toán : Insertion Sort
1 2 3 4 5 6 7 8 9 10
5
6
8
22
34
40
11
23
44
18
Minh họa
I. Phân tích thuật toán sắp xếp

I.1. Thuật toán : Insertion Sort
1 2 3 4 5 6 7 8 9 10
5
6
8
11
22
34
40
23
44
18
Minh họa
I. Phân tích thuật toán sắp xếp

I.1. Thuật toán : Insertion Sort
1 2 3 4 5 6 7 8 9 10
5
6
8
11
22
34
40
23
44
18
Minh họa
I. Phân tích thuật toán sắp xếp

I.1. Thuật toán : Insertion Sort
1 2 3 4 5 6 7 8 9 10
5
6
8
11
22
23
34
40
44
18
Minh họa
I. Phân tích thuật toán sắp xếp

I.1. Thuật toán : Insertion Sort
1 2 3 4 5 6 7 8 9 10
5
6
8
11
22
23
34
40
44
18
Minh họa
I. Phân tích thuật toán sắp xếp

I.1. Thuật toán : Insertion Sort
1 2 3 4 5 6 7 8 9 10
5
6
8
11
18
22
23
34
40
44
Minh họa
I. Phân tích thuật toán sắp xếp

I.1. Thuật toán : Insertion Sort