Bài giảng Cấu trúc dữ liệu: Chương 2 - Các giải thuật tìm kiếm và sắp thứ tự

Chương 2

Các giải thuật tìm kiếm Các giải thuật tìm kiếm và sắp thứ tự và sắp thứ tự

2.1. Giới thiệu chung

• Trong hầu hết các hệ lưu trữ, quản lý dữ liệu, thao Trong hầu hết các hệ lưu trữ, quản lý dữ liệu, thao tác tìm kiếm thường được thực hiện nhất để khai thác thông tin.

g

y

g

• Do các hệ thống thông tin thường phải lưu trữ một khối lượng dữ liệu đáng kể, nên việc xây dựng các g giải thuật cho phép tìm kiếm nhanh sẽ có ý nghĩa rất lớn.

• Nếu dữ liệu trong hệ thống đã được tổ chức theo một trật tự nào đó, thì việc tìm kiếm sẽ tiến hành nhanh chóng và hiệu quả hơn.

09/11/2008

Cấu trúc dữ liệu 1

2

2.1. Giới thiệu chung

• Có nhiều giải thuật tìm kiếm và sắp xếp • Có nhiều giải thuật tìm kiếm và sắp xếp

• Mức độ hiệu quả của từng giải thuật phụ thuộc vào tính chất của cấu trúc dữ liệu cụ thể mà nó tác động tính chất của cấu trúc dữ liệu cụ thể mà nó tác động đến.

• Dữ liệu được lưu trữ chủ yếu trong bộ nhớ chính và • Dữ liệu được lưu trữ chủ yếu trong bộ nhớ chính và trên bộ nhớ phụ, do đặc điểm khác nhau của thiết bị lưu trữ, các thuật toán tìm kiếm và sắp xếp được xây lưu trữ, các thuật toán tìm kiếm và sắp xếp được xây dựng cho các cấu trúc lưu trữ trên bộ nhớ chính hoặc phụ cũng có những đặc thù khác nhau.

09/11/2008

Cấu trúc dữ liệu 1

3

2.2. Các giải thuật tìm kiếm

Bài toán:

Tìm vị trí xuất hiện của phần tử có giá trị x

trên danh sách đặc a. Input:

- Một dãy số nguyên a0, a1, ... ,an-1

int a[n-1]; i t [ 1]

- Khoá cần tìm là x

int int

x; x;

ết uậ có p ầ tử ào có

óa à

ay

Output: ô g - Kết luận có phần tử nào có khóa là x hay không - Vị trí của phần tử có khóa x (nếu có)

09/11/2008

Cấu trúc dữ liệu 1

4

2.2. Các giải thuật tìm kiếm

2.2.1. Tìm kiếm tuyến tính 2 2 1 Tìm kiếm tuyến tính

Ý tưởng:

Lần lượt so sánh x với các phần tử của mảng, bắt đầu Lần lượt so sánh x với các phần tử của mảng bắt đầu

từ a[0]… a[n-1]. Nếu “gặp” thì kết thúc, nếu không

thì kiểm tra cho đến khi hết mảng.

09/11/2008

Cấu trúc dữ liệu 1

5

2.2. Các giải thuật tìm kiếm

2.2.1. Tìm kiếm tuyến tính 2 2 1 Tìm kiếm tuyến tính

Thuật toán: Thuật toán: Bước 1: Cho biến i giá trị khởi đầu là 0

a[i] thì sang bước 3, nếu Bước 2: So sánh x với a[i] nếu x = a[i] thì sang bước 3 nếu Bước 2: So sánh x với a[i], nếu x

không sang bước 4.

Bước 3: Kết luận “Tìm thấy”. Kết thúc. B ớ 3 Kết l ậ “Tì thấ ” Kết thú

Bước 4: Tăng giá trị i thêm một đơn vị

Bước 5: Kiểm tra i, nếu i ≥ n thì sang bước 6, không thì quay

lại bước 2

Bước 6: Kết luận “Không tìm thấy”. Kết thúc.

09/11/2008

Cấu trúc dữ liệu 1

6

2.2. Các giải thuật tìm kiếm

2.2.1. Tìm kiếm tuyến tính 2 2 1 Tìm kiếm tuyến tính

Ví dụ: Ví dụ: Cho dãy số a 2 12

8

5

1

6

4

15

Giá trị cần tìm: 8

i = 0

09/11/2008

Cấu trúc dữ liệu 1

7

2.2. Các giải thuật tìm kiếm

2.2.1. Tìm kiếm tuyến tính 2 2 1 Tìm kiếm tuyến tính

• i = 1 1 i

• i = 2 2 i

09/11/2008

Cấu trúc dữ liệu 1

8

2.2. Các giải thuật tìm kiếm

2.2.1. Tìm kiếm tuyến tính 2 2 1 Tìm kiếm tuyến tính

Cài đặt: Cài đặt: int LinearSearch(int a[],int n,int x) {

int i=0; int i=0; while(i

ầ

if (a[i]==x) return i; // a[i] là phần tử có khóa x i++;

// tìm hết mảng nhưng không có x }} return -1;

}

09/11/2008

Cấu trúc dữ liệu 1

9

2.2. Các giải thuật tìm kiếm

2.2.1. Tìm kiếm tuyến tính 2 2 1 Tìm kiếm tuyến tính

ầ

Nhận xét: Nhận xét: Thuật toán trên có 1 điểm hạn chế: phải kiểm tra 2 lần trong mỗi vòng lặp. lần trong mỗi vòng lặp ⇒ Khắc phục: Sử dụng kỹ thuật phần tử “lính canh”, nghĩa là ta cho thêm 1 phần tử a[n]=x, như vậy, bảo đảm luôn tìm thấy x trong mảng.

ấ

09/11/2008

Cấu trúc dữ liệu 1

10

2.2. Các giải thuật tìm kiếm

2.2.1. Tìm kiếm tuyến tính 2 2 1 Tìm kiếm tuyến tính

Cài đặt: Cài đặt: int LinearSearch(int a[],int n,int x) {

int i=0; int i=0; a[n]=x; while(x!=a[i])

i++; if (i==n)

// tìm hết mảng nhưng không có x // tìm hết mảng nhưng không có x return -1; etu ;

else

// tìm thấy x tại vị trí i return i;

} }

09/11/2008

Cấu trúc dữ liệu 1

11

2.2. Các giải thuật tìm kiếm

2.2.1. Tìm kiếm tuyến tính 2 2 1 Tìm kiếm tuyến tính

Đánh giá: Đánh giá:

Vậy giải thuật tìm kiếm tuyến tính có độ phức tạp tính toán cấp n: T(n) = O(n)

09/11/2008

Cấu trúc dữ liệu 1

12

2.2. Các giải thuật tìm kiếm

2.2.1. Tìm kiếm tuyến tính 2 2 1 Tìm kiếm tuyến tính

Nhận xét: Nhận xét:

á

d h á h d

ậ đâ

tử t

hầ

• Giải thuật tìm tuyến tính không phụ thuộc vào thứ tự của các phần tử trong danh sách, do vậy đây là tự ủ là phương pháp tổng quát nhất để tìm kiếm trên một danh sách bất kỳ. danh sách bất kỳ

• Đối với mảng có thứ tự thuật toán này sẽ không tối ưu vì không tận dụng được tính chất có thứ tự của các ưu vì không tận dụng được tính chất có thứ tự của các phần tử trong mảng.

09/11/2008

Cấu trúc dữ liệu 1

13

2.2. Các giải thuật tìm kiếm

2.2.2. Tìm kiếm nhị phân 2 2 2 Tìm kiếm nhị phân

h

d

hầ

[ i+1

n 1]

Đối với những dãy đã có thứ tự (giả sử thứ tự tăng), các phần tử trong dãy có quan hệ ai -1 ≤ ) ai ≤ ai+1 Nếu x > ai thì x chỉ có thể xuất hiện trong y đoạn [ai+1 ,an-1] của dãy. Nếu x < ai thì x chỉ có thể xuất hiện trong đoạn [a0 ,ai-1] của dãy. đoạn [a0 ai 1] của dãy

09/11/2008

Cấu trúc dữ liệu 1

14

2.2. Các giải thuật tìm kiếm

2.2.2. Tìm kiếm nhị phân 2 2 2 Tìm kiếm nhị phân

Ý tưởng:

So sánh x với phần tử giữa mảng, “bằng” thì kết

thúc, nếu không thì tùy giá trị của x mà ta sẽ thu hẹp thúc nếu không thì tùy giá trị của x mà ta sẽ thu hẹp

không gian tìm kiếm và lặp lại bước trên cho đến khi

tìm thấy, hoặc không gian tìm rỗng.

09/11/2008

Cấu trúc dữ liệu 1

15

2.2. Các giải thuật tìm kiếm

2.2.2. Tìm kiếm nhị phân 2 2 2 Tìm kiếm nhị phân

Thuật toán: Thuật toán:

Bước 1: Khởi tạo left = 0, right = n - 1

Bước 2: Xác định phần tử ở giữa: mid = (left + right)/2

a[mid] thì sang Bước 3: So sánh x với a[mid]. Nếu x = a[mid] thì sang Bước 3: So sánh x với a[mid]. Nếu x

bước 4, nếu không sang bước 5.

Bước 4: Kết luận “Tìm thấy”. Kết thúc.

ế h

ế l

hấ

Bước 5: Nếu x < a[mid] thì sang bước 6, nếu không sang

bước 7.

09/11/2008

Cấu trúc dữ liệu 1

16

2.2. Các giải thuật tìm kiếm

2.2.2. Tìm kiếm nhị phân 2 2 2 Tìm kiếm nhị phân

Thuật toán: Thuật toán:

Bước 6: Giới hạn không gian tìm kiếm: right = mid -1,

sang bước 8.

1, Bước 7: Giới hạn không gian tìm kiếm: left = mid + 1, Bước 7: Giới hạn không gian tìm kiếm: left mid

sang bước 8

Bước 8: Nếu left > right sang bước 9, không thì quay lại l i

ế l f

i h

kh

b

h

bước 2.

Bước 9: Kết luận “Không tìm thấy”. Kết thúc.

09/11/2008

Cấu trúc dữ liệu 1

17

2.2. Các giải thuật tìm kiếm

2.2.2. Tìm kiếm nhị phân 2 2 2 Tìm kiếm nhị phân

Ví dụ: Ví dụ:

Cho dãy số a gồm 8 phần tử:

1

2

4

5

6

8

12

15

Giá trị cần tìm là 8 ầ

09/11/2008

Cấu trúc dữ liệu 1

18

2.2. Các giải thuật tìm kiếm

2.2.2. Tìm kiếm nhị phân 2 2 2 Tìm kiếm nhị phân

left = 0, right = 7, mid = 3

09/11/2008

Cấu trúc dữ liệu 1

19

2.2. Các giải thuật tìm kiếm

2.2.2. Tìm kiếm nhị phân 2 2 2 Tìm kiếm nhị phân

left = 4, right = 7, mid = 5

09/11/2008

Cấu trúc dữ liệu 1

20

2.2. Các giải thuật tìm kiếm

h(i t [] i t S

2.2.2. Tìm kiếm nhị phân 2 2 2 Tìm kiếm nhị phân Cài đặt: int BinarySearch(int a[],int n,int x) i t ) i t Bi {

int left = 0, right = n-1, mid; dodo {

[

ấ mid = (left + right)/2; ]) if (x == a[mid]) ( return mid; //Tìm thấy x tại mid

if (x

right = mid -1;

lelse

left = mid +1;

// trong dãy không có x // trong dãy không có x } while (left <= right); return 1; return -1;

}

09/11/2008

Cấu trúc dữ liệu 1

21

2.2. Các giải thuật tìm kiếm

2.2.2. Tìm kiếm nhị phân 2 2 2 Tìm kiếm nhị phân

Đánh giá: Đánh giá:

Vậy giải thuật tìm kiếm nhị phân có độ phức tạp tính toán cấp n: T(n) = O(log2n)

09/11/2008

Cấu trúc dữ liệu 1

22

2.2. Các giải thuật tìm kiếm

2.2.2. Tìm kiếm nhị phân 2 2 2 Tìm kiếm nhị phân

Nhận xét: Nhận xét:

ả

để đị h hướ

ê khô

iệ

ắ

ế

• Giải thuật này dựa vào thứ tự các phần tử trong mảng để định hướng việc sắp xếp nên không thể áp thể á dụng cho mọi trường hợp, chỉ áp dụng được cho những dãy đã có thứ tự. những dãy đã có thứ tự

• Giải thuật tìm nhị phân tiết kiệm thời gian hơn rất nhiều so với giải thuật tìm tuyến tính vì nhiều so với giải thuật tìm tuyến tính vì

Tnhị phân (n) = O(log 2 n) < Ttuần tự (n) = O(n)

09/11/2008

Cấu trúc dữ liệu 1

23

2.2. Các giải thuật tìm kiếm

2.2.2. Tìm kiếm nhị phân 2 2 2 Tìm kiếm nhị phân

Nhận xét: Nhận xét:

i

thời

ắ

• Khi muốn áp dụng giải thuật tìm nhị phân cần phải xét đến thời gian sắp xếp dãy số để thỏa điều kiện ố để thỏ điề kiệ ế dã ét đế dãy số có thứ tự. Thời gian này không nhỏ, và khi dãy số biến động cần phải tiến hành sắp xếp lại ⇒ dãy số biến động cần phải tiến hành sắp xếp lại ⇒ khuyết điểm chính cho giải thuật tìm nhị phân.

• Cần cân nhắc nhu cầu thực tế để chọn một trong hai Cần cân nhắc nhu cầu thực tế để chọn một trong hai giải thuật tìm kiếm trên sao cho có lợi nhất.

09/11/2008

Cấu trúc dữ liệu 1

24

2.3. Các giải thuật sắp xếp nội 2.3.1. Định nghĩa bài toán sắp xếp 2 3 1 Định nghĩa bài toán sắp xếp

ự

ộ

ộ

g

Sắp xếp là quá trình xử lý một danh sách các phần tử Sắp xếp là quá trình xử lý một danh sách các phần tử (hoặc các mẫu tin) để đặt chúng theo một thứ tự thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thông g tin lưu giữ tại mỗi phần tử.

Lưu ý: Thứ tự được đề cập ở đây là một thứ tự tổng Lưu ý: Thứ tự được đề cập ở đây là một thứ tự tổng quát.

Ví dụ: Hãy định nghĩa một thứ tự để dãy số sau là Ví dụ: Hãy định nghĩa một thứ tự để dãy số sau là dãy tăng theo thứ tự này.

1 1

3 3

5 5

7 7

22 22

20 20

10 10

6 6

09/11/2008

Cấu trúc dữ liệu 1

25

2.3. Các giải thuật sắp xếp nội 2.3.1. Định nghĩa bài toán sắp xếp 2 3 1 Định nghĩa bài toán sắp xếp

Khái niệm “NGHỊCH THẾ” Xét một mảng các số a0, a1, … an. Xét một mảng các số a0 a1 a Nếu có i aj, thì ta gọi đó là một nghịch thế. Mảng chưa sắp xếp sẽ có nghịch thế. Mả hị h hế ế

ẽ ó

h

ắ

Mảng đã có thứ tự sẽ không chứa nghịch thế.

a0 ≤ a1 ≤ … ≤ an

09/11/2008

Cấu trúc dữ liệu 1

26

2.3. Các giải thuật sắp xếp nội

2.3.2. Các phương pháp sắp xếp thông dụng 2 3 2 Các phương pháp sắp xếp thông dụng

h

Phức tạp hơn Phứ t Hiệu quả cao

l

Lớp thuật toán Lớp thuật toán khác

• Selection sort i • Insertion sort • • Interchange sort Interchange sort • Bubble sort • Shaker sort Shaker sort • Binary Insertion sort • Shell sort • Heap sort • Quick sort Q i k • Merge sort • Radix sort • Radix sort • …

Đơn giản, Chi phí cao

09/11/2008

Cấu trúc dữ liệu 1

27

2.3. Các giải thuật sắp xếp nội

2.3.3. Phương pháp chọn trực tiếp – 2 3 3 Phương pháp chọn trực tiếp

Selection sort

Ý tưởng:

- Chọn phần tử nhỏ nhất đặt vào vị trí đầu tiên.

- Chọn phần tử nhỏ nhất trong số n - 1 phần tử còn 1 hầ tử ò

hầ tử hỏ hất t

Ch

ố

lại đặt vào vị trí thứ 2.

- Lặp lại quá trình trên cho đến khi mảng chỉ còn 1

phần tử. phần tử

09/11/2008

Cấu trúc dữ liệu 1

28

2.3. Các giải thuật sắp xếp nội

2.3.3. Phương pháp chọn trực tiếp – 2 3 3 Phương pháp chọn trực tiếp

Selection sort

Thuật toán:

Bước 1: Khởi tạo i = 0

Bước 2: Khởi đầu min = i, j = i + 1

Bước 3: Nếu a[j] < a[min] thì min = j, nếu không thì

sang bước 4 sang bước 4

Bước 4: Tăng j thêm 1 đơn vị

09/11/2008

Cấu trúc dữ liệu 1

29

2.3. Các giải thuật sắp xếp nội

2.3.3. Phương pháp chọn trực tiếp – 2 3 3 Phương pháp chọn trực tiếp

Selection sort

Thuật toán:

Bước 5: Nếu j < n thì quay lại bước 3, nếu không thì

ế

ế

sang bước 6

Bước 6: Đổi chỗ a[min] và a [i], tăng i lên 1 đơn vị

Bước 7: Nếu i < n – 1 thì quay lại bước 2, nếu không thì Bước 7: Nếu i < n 1 thì quay lại bước 2 nếu không thì

kết thúc.

09/11/2008

Cấu trúc dữ liệu 1

30

2.3. Các giải thuật sắp xếp nội

2.3.3. Phương pháp chọn trực tiếp – 2 3 3 Phương pháp chọn trực tiếp

Selection sort

Find MinPos(0, 7) Swap(ai, amin)

1 2 3 4 5 6 7 min 0

2

8

5

1

6

4

15

12

i

09/11/2008

Cấu trúc dữ liệu 1

31

2.3. Các giải thuật sắp xếp nội

2.3.3. Phương pháp chọn trực tiếp – 2 3 3 Phương pháp chọn trực tiếp

Selection sort

Find MinPos(2, 7) Swap(ai, amin)

min 2 3 4 5 6 7 0 1

8 8

5

12 12

6 6

4 4

15 1

1 1

2 2

i

09/11/2008

Cấu trúc dữ liệu 1

32

2.3. Các giải thuật sắp xếp nội

2.3.3. Phương pháp chọn trực tiếp – 2 3 3 Phương pháp chọn trực tiếp

Selection sort

Find MinPos(3, 7) Swap(ai, amin)

0 1 min 3 4 5 6 7 2

1 1

2 2

5 5

12 12

6 6

8 8

15 15

4 4

i

09/11/2008

Cấu trúc dữ liệu 1

33

2.3. Các giải thuật sắp xếp nội

2.3.3. Phương pháp chọn trực tiếp – 2 3 3 Phương pháp chọn trực tiếp

Selection sort

Find MinPos(4, 7) Swap(ai, amin)

0 1 2 min 4 5 6 7 3

1

2

4

12

6

8

15

5

i

09/11/2008

Cấu trúc dữ liệu 1

34

2.3. Các giải thuật sắp xếp nội

2.3.3. Phương pháp chọn trực tiếp – 2 3 3 Phương pháp chọn trực tiếp

Selection sort

Find MinPos(5, 7) Swap(ai, amin)

0 1 2 3 min 5 6 7 4

1

2

4

5

12

8

15

6

i

09/11/2008

Cấu trúc dữ liệu 1

35

2.3. Các giải thuật sắp xếp nội

2.3.3. Phương pháp chọn trực tiếp – 2 3 3 Phương pháp chọn trực tiếp

Selection sort

Find MinPos(6, 7) Swap(ai, amin)

0 1 2 3 4 min 6 7 5

1

2

4

5

6

12 12

8

15 15

i

09/11/2008

Cấu trúc dữ liệu 1

36

2.3. Các giải thuật sắp xếp nội

2.3.3. Phương pháp chọn trực tiếp – 2 3 3 Phương pháp chọn trực tiếp

Selection sort

Cài đặt:

void SelectionSort(int a[],int n) { {

i=0; i

int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành for (int {{

min = i; for(int j = i+1; j < n ; j++)

if (a[j] < a[min]) if (a[j] < a[min])

min = j; // ghi nhận vị trí phần tử nhỏ nhất

if (min != i)

swap(a[min], a[i]); swap(a[min] a[i]);

}

}

09/11/2008

Cấu trúc dữ liệu 1

37

2.3. Các giải thuật sắp xếp nội

2.3.3. Phương pháp chọn trực tiếp – 2 3 3 Phương pháp chọn trực tiếp

Selection sort

Đánh giá:

Số lần hoán vị (một hoán vị bằng 3 phép gán) phụ thuộc vào tình trạng ban đầu của dãy số ố h

ì h

đầ

b

d

à

09/11/2008

Cấu trúc dữ liệu 1

38

2.3. Các giải thuật sắp xếp nội

2.3.3. Phương pháp chọn trực tiếp – 2 3 3 Phương pháp chọn trực tiếp

Selection sort

Đánh giá:

h

hấ hi

Ở lượt thứ i, cần (n-i) lần so sánh để xác định phần tử nhỏ nhất hiện hành. hà h Số lượng phép so sánh không phụ thuộc vào tình trạng của dãy số ban đầu. của dãy số ban đầu Trong mọi trường hợp, số lần so sánh là:

1n− 1n −

1) 1)

i)

=−∑ (n

n(n ( − 2

1i =

09/11/2008

Cấu trúc dữ liệu 1

39

2.3. Các giải thuật sắp xếp nội

2.3.4. Phương pháp chèn trực tiếp – 2 3 4 Phương pháp chèn trực tiếp

Insertion sort

Ý ởÝ tưởng:

-Tại bước thứ i thì các phần tử từ a[0] đến a[i-1] đều có thứ

tự tăng dần.

( [ ]

g

p) - Đầu tiên ta bắt đầu với i = 1 (a[0] không cần sắp)

- Tìm vị trí thích hợp để chèn a[1] vào đoạn a[0]…a[1]

- Kế tiếp, tìm vị trí thích hợp để chèn a[2] vào đoạn

ị t í thí h h

để hè

Kế tiế

[2]

tì

đ

à

a[0]…a[2]

- Làm tiếp tục cho đến khi sắp được phần tử cuối cùng.

09/11/2008

Cấu trúc dữ liệu 1

40

2.3. Các giải thuật sắp xếp nội

2.3.4. Phương pháp chèn trực tiếp – 2 3 4 Phương pháp chèn trực tiếp

Insertion sort á

Thuật toán: Th ậ

- Bước 1: Khởi tạo i =1

- Bước 2: pos = i -1, x = a[i]

[p ]

g

g

g - Bước 3: Nếu x < a[pos] thì sang bước 4 không thì sang

bước 6

- Bước 4: Dời a[pos] sang phải: a[pos+1] = a[pos], giảm

B ớ 4 Dời

+1]

hải

iả

[

[

[

]

]

pos 1 đơn vị

09/11/2008

Cấu trúc dữ liệu 1

41

2.3. Các giải thuật sắp xếp nội

2.3.4. Phương pháp chèn trực tiếp – 2 3 4 Phương pháp chèn trực tiếp

Insertion sort á

Thuật toán: Th ậ

- Bước 5: Nếu pos ≥ 0 thì quay lại bước 3, nếu không sang

bước 6

[p

g

,

ị - Bước 6: Gán a[pos+1] = x, tăng i thêm 1 đơn vị ]

- Bước 7: Nếu i < n thì quay lại bước 2, không thì kết thúc.

09/11/2008

Cấu trúc dữ liệu 1

42

2.3. Các giải thuật sắp xếp nội

2.3.4. Phương pháp chèn trực tiếp – 2 3 4 Phương pháp chèn trực tiếp

Insertion sort

Ví dụ:

0 1 2 3 4 5 6 7

12

2

8

5

1

6

4

15

09/11/2008

Cấu trúc dữ liệu 1

43

2.3. Các giải thuật sắp xếp nội

2.3.4. Phương pháp chèn trực tiếp – 2 3 4 Phương pháp chèn trực tiếp

Insertion sort

Insert a1 into (0, 1)

0 2 3 4 5 6 7 pos 1

122 12 2

8 8

5 5

1 1

6 6

4 4

15 15

2 2

i

x

09/11/2008

Cấu trúc dữ liệu 1

44

2.3. Các giải thuật sắp xếp nội

2.3.4. Phương pháp chèn trực tiếp – 2 3 4 Phương pháp chèn trực tiếp

Insertion sort

Insert a2 into (0, 2)

0 1 pos 2 3 4 5 6 7

2

8 812

8

5

1

6

4

15

i

x

09/11/2008

Cấu trúc dữ liệu 1

45

2.3. Các giải thuật sắp xếp nội

2.3.4. Phương pháp chèn trực tiếp – 2 3 4 Phương pháp chèn trực tiếp

Insertion sort

Insert a3 into (0, 3)

0 1 4 5 6 7 2 pos 3

2 2

1 1

6 6

4 4

15 15

12 12

5 5

8 8 5

i

x x

09/11/2008

Cấu trúc dữ liệu 1

46

2.3. Các giải thuật sắp xếp nội

2.3.4. Phương pháp chèn trực tiếp – 2 3 4 Phương pháp chèn trực tiếp

Insertion sort

Insert a4 into (0, 4)

0 1 2 pos 4 5 6 7 3

5 5

8 8

1 1

6 6

4 4

15 15

12 12

21 2 1

i

x

09/11/2008

Cấu trúc dữ liệu 1

47

2.3. Các giải thuật sắp xếp nội

2.3.4. Phương pháp chèn trực tiếp – 2 3 4 Phương pháp chèn trực tiếp

Insertion sort

Insert a5 into (0, 5)

0 1 2 3 pos 5 6 7 4

1 1

2 2

5 5

6 8 8 6

6 6

4 4

15 15

12 12

i

x

09/11/2008

Cấu trúc dữ liệu 1

48

2.3. Các giải thuật sắp xếp nội

2.3.4. Phương pháp chèn trực tiếp – 2 3 4 Phương pháp chèn trực tiếp

Insertion sort

Insert a6 into (0, 6)

0 1 2 3 4 pos 6 7 5

1

2

4 5

6

8

4

15

12

i

x

09/11/2008

Cấu trúc dữ liệu 1

49

2.3. Các giải thuật sắp xếp nội

2.3.4. Phương pháp chèn trực tiếp – 2 3 4 Phương pháp chèn trực tiếp

Insertion sort

Insert a7 into (0, 7)

0 1 2 3 4 5 pos 7 6

1

2

4

5

6

8

15 15

12

i

x

09/11/2008

Cấu trúc dữ liệu 1

50

2.3. Các giải thuật sắp xếp nội

2.3.4. Phương pháp chèn trực tiếp – 2 3 4 Phương pháp chèn trực tiếp

Insertion sort

0 1 2 3 5 6 7 pos 4

1

2

4

5

8

12

15

6

09/11/2008

Cấu trúc dữ liệu 1

51

2.3. Các giải thuật sắp xếp nội

2.3.4. Phương pháp chèn trực tiếp – 2 3 4 Phương pháp chèn trực tiếp

Insertion sort

Cài đặt: Cài đặ

void InsertionSort(int a[],int n) {{

//lưu trữ a[i] tránh bị ghi đè khi dời chỗ các phần tử.

int pos; int x ; for(int i=1;i

x = a[i]; for(pos=i;(pos>0)&&(a[pos-1]>x);pos--) a[pos] = a[pos-1]; a[pos] = x; // chèn x vào dãy

}

} 09/11/2008

Cấu trúc dữ liệu 1

52

2.3. Các giải thuật sắp xếp nội

2.3.4. Phương pháp chèn trực tiếp – 2 3 4 Phương pháp chèn trực tiếp

Insertion sort

Nhận xét: Nhậ

é

- Khi tìm vị trí thích hợp để chèn a[i] vào đoạn a[0] đến a[i- 1], do đoạn đã được sắp (cid:206) có thể sử dụng giải thuật tìm 1] do đoạn đã được sắp (cid:206) có thể sử dụng giải thuật tìm nhị phân để thực hiện việc tìm vị trí pos (cid:206) giải thuật sắp xếp chèn nhị phân Binary Insertion Sort

Lưu ý: Chèn nhị phân chỉ làm giảm số lần so sánh,

không làm giảm số lần dời chỗ.

- Ngoài ra, có thể cải tiến giải thuật chèn trực tiếp với phần tử cầm canh để giảm điều kiện kiểm tra khi xác định vị trí pos.

09/11/2008

Cấu trúc dữ liệu 1

53

2.3. Các giải thuật sắp xếp nội

2.3.4. Phương pháp chèn trực tiếp – 2 3 4 Phương pháp chèn trực tiếp

Insertion sort

Cài đặt Binary Insertion Sort: Cài đặt Binary Insertion Sort:

BInsertionSort(int a[],int n)

void { int l,r,m,i; //lưu trữ giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử. //l hầ tử

t ữ iá t ị [i] t á h bị hi đè khi dời hỗ á

i t int x; for(int i=1;i

// tìm vị trí chèn x // tìm vị trí chèn x // tìm vị trí thích hợp m

x = a[i]; l = 0; r = i-1; while(l<=r) while(l<=r) { m = (l+r)/2;

if(x < a[m]) r = m-1; else l = m+1;

} for(int j = i ; j >l ; j--)

a[j] = a[j-1];

// dời chỗ các phần tử sẽ đứng sau x // chèn x vào dãy

a[l] = x;

}

}

09/11/2008

Cấu trúc dữ liệu 1

54

2.3. Các giải thuật sắp xếp nội

2.3.4. Phương pháp chèn trực tiếp – 2 3 4 Phương pháp chèn trực tiếp

Insertion sort

Đánh giá: Đánh giá:

- Các phép so sánh xảy ra trong mỗi vòng lặp tìm vị trí thích hợp pos. Mỗi lần xác định vị trí pos đang xét không thích hợp (cid:206) dời chỗ phần tử a[pos-1] đến vị trí pos. ầ ế

á h à dời hỗ à à tì h t h th ộ ủ dã

- Giải thuật thực hiện tất cả n-1 vòng lặp tìm pos, do số lượng hé phép so sánh và dời chỗ này phụ thuộc vào tình trạng của dãy số ố ban đầu, nên chỉ có thể ước lược trong từng trường hợp như sau:

09/11/2008

Cấu trúc dữ liệu 1

55

2.3. Các giải thuật sắp xếp nội

2.3.5. Phương pháp đổi chỗ trực tiếp – 2 3 5 Phương pháp đổi chỗ trực tiếp

Interchange sort

ộ dãy số, a có

ể é các g ịc

Nhận xét: Để sắp xếp một dãy số, ta có thể xét các nghịch thế có ế có ể sắp ếp trong dãy và làm triệt tiêu dần chúng đi. Ý tưởng: Ý tưởng:

- Xuất phát từ đầu dãy, tìm tất cả nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chỗ phần tử này tử này triệt tiêu chúng bằng cách đổi chỗ phần tử này với phần tử tương ứng trong cặp nghịch thế.

- Lặp lại xử lý trên với các phần tử tiếp theo trong dãy. Lặp lại xử lý trên với các phần tử tiếp theo trong dãy

09/11/2008

Cấu trúc dữ liệu 1

56

2.3. Các giải thuật sắp xếp nội

2.3.5. Phương pháp đổi chỗ trực tiếp – 2 3 5 Phương pháp đổi chỗ trực tiếp

Interchange sort

Thuật toán: Th ậ

á

- Bước 1: Khởi tạo i = 0 // bắt đầu từ đầu dãy

- Bước 2: j = i+1; //tìm các cặp phần tử a[j] < a[i], j>i

ự

g

j

ệ - Bước 3: Trong khi j < n thực hiện

• Nếu a[j]

- Bước 4: i = i+1;

• Nếu i < n-1: Lặp lại Bước 2. • Ngược lại: Dừng.

09/11/2008

Cấu trúc dữ liệu 1

57

2.3. Các giải thuật sắp xếp nội

2.3.5. Phương pháp đổi chỗ trực tiếp – 2 3 5 Phương pháp đổi chỗ trực tiếp

Interchange sort

Ví dụ:

j j 1 0 2 3 4 5 6 7

2 2

1 1 12 12

8 8

5 5

1 1

6 6

4 4

15 15

i i

09/11/2008

Cấu trúc dữ liệu 1

58

2.3. Các giải thuật sắp xếp nội

2.3.5. Phương pháp đổi chỗ trực tiếp – 2 3 5 Phương pháp đổi chỗ trực tiếp

Interchange sort

1 j j 2 3 4 5 6 7 0

2 212 12

8 8

5 5

2 2

6 6

4 4

15 15

1 1

i i

09/11/2008

Cấu trúc dữ liệu 1

59

2.3. Các giải thuật sắp xếp nội

2.3.5. Phương pháp đổi chỗ trực tiếp – 2 3 5 Phương pháp đổi chỗ trực tiếp

Interchange sort

2 j j 3 4 5 6 7 0 1

4 4 12 12

8 8

5 5

6 6

4 4

15 15

1 1

2 2

i i

09/11/2008

Cấu trúc dữ liệu 1

60

2.3. Các giải thuật sắp xếp nội

2.3.5. Phương pháp đổi chỗ trực tiếp – 2 3 5 Phương pháp đổi chỗ trực tiếp

Interchange sort

0 1 3 j j 4 5 6 7 2

1 1

2 2

5 5 12 12

8 8

6 6

5 5

15 15

4 4

i i

09/11/2008

Cấu trúc dữ liệu 1

61

2.3. Các giải thuật sắp xếp nội

2.3.5. Phương pháp đổi chỗ trực tiếp – 2 3 5 Phương pháp đổi chỗ trực tiếp

Interchange sort

0 1 2 3 4 5 6 7

1 1

2 2

4 4

5 5

6 6

8 8

12 12

15 15

09/11/2008

Cấu trúc dữ liệu 1

62

2.3. Các giải thuật sắp xếp nội

2.3.5. Phương pháp đổi chỗ trực tiếp – 2 3 5 Phương pháp đổi chỗ trực tiếp

Interchange sort

Cài đặt: Cài đặ

void InterchangeSort(int a[], int n) {{

int i, j; for (i = 0 ; i

for (j i+1; j < n ; j++) for (j =i+1; j < n ; j++)

if(a[j]< a[i]) //nếu có nghịch thế thì đổi chỗ

Swap(a[i],a[j]);

}

09/11/2008

Cấu trúc dữ liệu 1

63

2.3. Các giải thuật sắp xếp nội

2.3.5. Phương pháp đổi chỗ trực tiếp – 2 3 5 Phương pháp đổi chỗ trực tiếp

Interchange sort

Đánh giá: Đánh giá:

- Số lượng các phép so sánh xảy ra không phụ thuộc vào tình trạng của dãy số ban đầu. trạng của dãy số ban đầu

- Số lượng phép hoán vị thực hiện tùy thuộc vào kết quả so sánhsá

09/11/2008

Cấu trúc dữ liệu 1

64

2.3. Các giải thuật sắp xếp nội

2.3.6. Phương pháp nổi bọt – Bubble sort 2 3 6 Phương pháp nổi bọt Bubble sort

Ý tưởng: Ý tưởng: - Đưa dần các phần tử có khóa (giá trị) nhỏ về phía trước. trước.

- Xuất phát từ cuối (đầu) dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ (lớn) hơn trong cặp phần tử đó cận để đưa phần tử nhỏ (lớn) hơn trong cặp phần tử đó về vị trí đúng đầu (cuối) dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo.

- Ở lần xử lý thứ i có vị trí đầu dãy là i.

- Lặp lại xử lý trên cho đến khi không còn cặp phần tử - Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét.

09/11/2008

Cấu trúc dữ liệu 1

65

2.3. Các giải thuật sắp xếp nội

2.3.6. Phương pháp nổi bọt – Bubble sort 2 3 6 Phương pháp nổi bọt Bubble sort

Thuật toán: Th ậ

á

- Bước 1: Khởi tạo i =0

- Bước 2: j = n-1; //Duyệt từ cuối dãy ngược về vị trí i

ự

g

j

ệ - Bước 3: Trong khi j > i thực hiện

• Nếu a[j]

- Bước 4: i = i+1; // lần xử lý kế tiếp

• Nếu i = n-1: Dừng. // Hết dãy • Ngược lại: Lặp lại Bước 2.

09/11/2008

Cấu trúc dữ liệu 1

66

2.3. Các giải thuật sắp xếp nội

2.3.6. Phương pháp nổi bọt – Bubble sort 2 3 6 Phương pháp nổi bọt Bubble sort

Ví dụ:

0 1 2 3 4 5 6 j j 7

1 12

2

8

5

1

6

4

15

i

09/11/2008

Cấu trúc dữ liệu 1

67

2.3. Các giải thuật sắp xếp nội

2.3.6. Phương pháp nổi bọt – Bubble sort 2 3 6 Phương pháp nổi bọt Bubble sort

1 2 3 4 5 6 j j 7 0

2

8

5

4

6

15

1

12 2

i

09/11/2008

Cấu trúc dữ liệu 1

68

2.3. Các giải thuật sắp xếp nội

2.3.6. Phương pháp nổi bọt – Bubble sort 2 3 6 Phương pháp nổi bọt Bubble sort

0 2 3 4 5 6 j j 7 1

1

4 12

4

8

5

6

15

2

i

09/11/2008

Cấu trúc dữ liệu 1

69

2.3. Các giải thuật sắp xếp nội

2.3.6. Phương pháp nổi bọt – Bubble sort 2 3 6 Phương pháp nổi bọt Bubble sort

0 1 3 4 5 6 j j 7 2

1

2

5 12

8

5

6

15

4

i

09/11/2008

Cấu trúc dữ liệu 1

70

2.3. Các giải thuật sắp xếp nội

2.3.6. Phương pháp nổi bọt – Bubble sort 2 3 6 Phương pháp nổi bọt Bubble sort

0 1 2 4 5 6 j j 7 3

1

2

4

6 12

8

6

15

5

i

09/11/2008

Cấu trúc dữ liệu 1

71

2.3. Các giải thuật sắp xếp nội

2.3.6. Phương pháp nổi bọt – Bubble sort 2 3 6 Phương pháp nổi bọt Bubble sort

0 1 2 3 5 6 j j 7 4

1

2

4

5

8 12

8

15

6

i

09/11/2008

Cấu trúc dữ liệu 1

72

2.3. Các giải thuật sắp xếp nội

2.3.6. Phương pháp nổi bọt – Bubble sort 2 3 6 Phương pháp nổi bọt Bubble sort

0 1 2 3 4 6 j j 7 5

1

2

4

5

6

12 12

15 15

8

i

09/11/2008

Cấu trúc dữ liệu 1

73

2.3. Các giải thuật sắp xếp nội

2.3.6. Phương pháp nổi bọt – Bubble sort 2 3 6 Phương pháp nổi bọt Bubble sort

Cài đặt: Cài đặ

void BubbleSort(int a[], int n) {

int i, j; for (i = 0 ; i

for (j =n-1; j>i ; j --)

if(a[j]< a[j-1])

swap(a[j], a[j-1]);

} }

09/11/2008

Cấu trúc dữ liệu 1

74

2.3. Các giải thuật sắp xếp nội

2.3.6. Phương pháp nổi bọt – Bubble sort 2 3 6 Phương pháp nổi bọt Bubble sort

Đánh giá: Đánh giá:

- Số lượng các phép so sánh xảy ra không phụ thuộc vào tình trạng của dãy số ban đầu. trạng của dãy số ban đầu

- Số lượng phép hoán vị thực hiện tùy thuộc vào kết quả so sánhsá

09/11/2008

Cấu trúc dữ liệu 1

75

2.3. Các giải thuật sắp xếp nội

2.3.6. Phương pháp nổi bọt – Bubble sort 2 3 6 Phương pháp nổi bọt Bubble sort

Đánh giá: Đánh giá:

Khuyết điểm: - Không nhận diện được tình trạng dãy đã có thứ tự hay - Không nhận diện được tình trạng dãy đã có thứ tự hay có thứ tự từng phần.

- Các phần tử nhỏ được đưa về vị trí đúng rất nhanh, Các phần tử nhỏ được đưa về vị trí đúng rất nhanh trong khi các phần tử lớn lại được đưa về vị trí đúng rất chậm.ậ

09/11/2008

Cấu trúc dữ liệu 1

76

2.3. Các giải thuật sắp xếp nội

2.3.6. Phương pháp nổi bọt – Bubble sort 2 3 6 Phương pháp nổi bọt Bubble sort

Cải tiến: Cải tiến:

Giải thuật ShakerSort: - Dựa trên nguyên tắc đổi chỗ trực tiếp Dựa trên nguyên tắc đổi chỗ trực tiếp - Tìm cách khắc phục các nhược điểm của BubleSort (cid:131) Trong mỗi lần sắp xếp, duyệt mảng theo 2 lượt từ 2 phía khác nhau :

L t ề đẩ

ối

ề

ả

o Lượt đi: đẩy phần tử nhỏ về đầu mảng o Lượt về: đẩy phần tử lớn về cuối mảng hầ tử lớ (cid:131) Ghi nhận lại những đoạn đã sắp xếp nhằm tiết kiệm các phép so sánh thừa. kiệm các phép so sánh thừa

09/11/2008

Cấu trúc dữ liệu 1

77

2.3. Các giải thuật sắp xếp nội

2.3.6. Phương pháp nổi bọt – Bubble sort 2 3 6 Phương pháp nổi bọt Bubble sort

Cải tiến: Cải tiến: Giải thuật ShakerSort: - Bước 1: l = 0; r = n-1; //từ l đến r là đoạn cần được sắp xếp // ghi nhận lại vị trí k xảy ra hoán vị sau

k = n-1;

// đẩy phần tử nhỏ về đầu mảng

cùng để làm cơ sở thu hẹp đoạn l đến r - Bước 2: Bước 2: Bước 2a: j = r ; Trong khi (j > l) :

Nếu a[j]

a[j] ↔ a[j-1];

k = j; //lưu lại nơi xảy ra hoán vị

j = j-1; j = j 1;

l = k; //loại bớt các phần tử đã có thứ tự ở đầu dãy

09/11/2008

Cấu trúc dữ liệu 1

78

2.3. Các giải thuật sắp xếp nội

2.3.6. Phương pháp nổi bọt – Bubble sort 2 3 6 Phương pháp nổi bọt Bubble sort

Cải tiến: Cải tiến: Giải thuật ShakerSort: - Bước 2:

// đẩy phần tử lớn về cuối mảng

ẩ

ầ

ố

ề

Bước 2b: j = l ; Trong khi (j < r):

Nếu a[j]>a[j+1]: Nếu a[j]>a[j+1]:

a[j] ↔ a[j+1]; a[j] ↔ a[j+1]; k = j;//lưu lại nơi xảy ra hoán vị

j = j+1;

r = k; //loại bớt các phần tử đã có thứ tự ở cuối dãy

- Bước 3: Nếu l < r: Lặp lại Bước 2.

09/11/2008

Cấu trúc dữ liệu 1

79

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

h

hi

hầ

hấ

b

h

i

i đ

ó đ

hô

hé

d

á

• Khi tìm phần tử nhỏ nhất ở bước i, phương pháp sắp xếp chọn trực tiếp không tận dụng được các thông tin đã có được do các phép so đ á sánh ở bước i-1.

• Giải thuật Heap Sort khắc phục nhược điểm này bằng cách chọn ra được một cấu trúc dữ liệu cho phép tích lũy các thông tin về sự so sánh giá trị các phần tử trong quá trình sắp xếp. ế

09/11/2008

Cấu trúc dữ liệu 1

80

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

• Xét dãy số : 5 2 6 4 8 1 Xét dãy số : 5 2 6 4 8 1 • Giả sử các phần tử của dãy được bố trí theo quan hệ so sánh và tạo thành sơ đồ dạng cây: quan hệ so sánh và tạo thành sơ đồ dạng cây:

09/11/2008

Cấu trúc dữ liệu 1

81

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

(

y)

p

• Phần tử ở mức i chính là phần tử lớn trong cặp phần Phần tử ở mức i chính là phần tử lớn trong cặp phần tử tương ứng ở mức i+1 p g ⇒ phần tử ở mức 0 (nút gốc của cây) luôn là phần tử lớn nhất của dãy. ạ

y ( g

p

g

• Nếu loại bỏ phần tử gốc ra khỏi cây (nghĩa là đưa phần tử lớn nhất về đúng vị trí), thì việc cập nhật cây chỉ xảy ra trên những nhánh liên quan đến phần tử mới loại bỏ, còn các nhánh khác được bảo toàn, nghĩa là bước kế tiếp có thể sử dụng lại các kết quả so sánh ở bước hiện tại. ở bước hiện tại

09/11/2008

Cấu trúc dữ liệu 1

82

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

• Loại bỏ 8 ra khỏi cây và thế vào các chỗ trống Loại bỏ 8 ra khỏi cây và thế vào các chỗ trống giá trị -∞ để tiện việc cập nhật lại cây:

09/11/2008

Cấu trúc dữ liệu 1

83

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

T à bộ há h t ái ủ

ũ đ

• Toàn bộ nhánh trái của cây cũ được bảo toàn â bả t à ⇒ Bước kế tiếp để chọn được phần tử lớn nhất hiện hành là 6, chỉ cần làm thêm một phép so sánh 1 với 6. hành là 6 chỉ cần làm thêm một phép so sánh 1 với 6

09/11/2008

Cấu trúc dữ liệu 1

84

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

• Tiến hành nhiều lần việc loại bỏ phần tử gốc của cây Tiến hành nhiều lần việc loại bỏ phần tử gốc của cây cho đến khi tất cả các phần tử của cây đều là -∞, khi đó xếp các phần tử theo thứ tự loại bỏ trên cây sẽ có dãy đã sắp xếp.

ể

• Để cài đặt thuật toán hiệu quả, cần phải tổ chức một ấ cấu trúc lưu trữ dữ liệu có khả năng thể hiện được quan hệ của các phần tử trong cây với n ô nhớ thay vì 2n-1 như trong ví dụ. 2 1 hư t

í d

• Khái niệm heap và phương pháp sắp xếp Heapsort do J Williams đề xuất đã giải quyết được các khó khăn J.Williams đề xuất đã giải quyết được các khó khăn trên.

09/11/2008

Cấu trúc dữ liệu 1

85

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

Định nghĩa heap: • Heap là một dãy các phần tử aleft, aleft+1,... , aright ầ

thoả các quan hệ: – ai ≥ a2i – ai ≥ a2i+1 – với ∀i ∈ [left, right]

• Khi đó (ai , a2i), (ai ,a2i+1) được gọi là các cặp phần

tử liên đới.

dầ khi ắ

iả

ờ

h

ế

ă

ế

• Heap được định nghĩa như trên được dùng trong trường hợp sắp xếp tăng dần, khi sắp xếp giảm dần dầ ắ phải đổi chiều các quan hệ.

09/11/2008

Cấu trúc dữ liệu 1

86

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

Ví dụ dãy là heap: Ví dụ dãy là heap:

0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7

15

12

8

5

1

4

6

2

09/11/2008

Cấu trúc dữ liệu 1

87

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

a1 a

a2 a3 tử phần Các tử phần Các của dãy được biểu diễn theo các mối quan ố hệ liên đới

a4 a5 a6 a7

a8 8

09/11/2008

Cấu trúc dữ liệu 1

88

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

• Một số tính chất của Heap:

ố

ấ

ắ

ố

ầ

ột h

là

– Tính chất 1: Nếu aleft, aleft+1, …, aright là một heap thì khi cắt bỏ một số phần tử ở hai đầu của heap, ầ dãy con còn lại vẫn là một heap. – Tính chất 2: Nếu a0, a1, …, an-1 là một heap thì Tí h hấ 2 Nế thì phần tử a0 (đầu heap) luôn là phần tử lớn nhất trong heap. trong heap

– Tính chất 3: Mọi dãy con aleft, aleft+1, ..., aright thỏa:

2left > right đều là heap. 2left > right đều là heap

09/11/2008

Cấu trúc dữ liệu 1

89

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

Ví dụ các tính chất của heap Ví dụ các tính chất của heap

0 1 2 3 4 5 6 7

15

12

8

5

1

6

4

2

12

8

5

1

6

4

1

6

4

2

09/11/2008

Cấu trúc dữ liệu 1

90

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

• Sắp xếp dãy tăng dần qua 2 giai đoạn: dầ

ế dã tă

2 i i đ

Sắ

– Giai đoạn 1: Dựa vào tính chất 3 của heap để hiệu Giai đoạn 1: Dựa vào tính chất 3 của heap để hiệu

chỉnh dãy ban đầu thành heap

– Giai đoạn 2: Dựa vào các tính chất 1 và 2 của heap

để sắp xếp heap có được sau giai đoạn 1 thành dãy để sắp xếp heap có được sau giai đoạn 1 thành dãy

tăng dần

09/11/2008

Cấu trúc dữ liệu 1

91

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

ột ố hầ tử t ê dã

• Vấn đề: Đổi chỗ một số phần tử trên dãy a1,…,

Vấ đề Đổi hỗ an để dãy trở thành heap.

• Ý tưởng: theo tính chất 3, dãy con an/2+1, an/2+2,... ,an đương nhiên là heap. Lần lượt thêm vào phía trước dãy các phần tử an/2, an/2-1, …, a1; mỗi bước thêm vào cần hiệu chỉnh vị trí các phần tử theo mối quan hệ liên đới ta sẽ nhận được heap mong muốn.

09/11/2008

Cấu trúc dữ liệu 1

92

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

Giai đoạn 1 Giai đoạn 1 //input: dãy (a, n) //output: dãy (a, n) là một heap //output: dãy (a n) là một heap • Bước 1: left = n/2; //Thêm các phần tử aleft, .., a1 vào

heapheap

• Bước 2: Trong khi left > 0 //Lưu ý: đoạn aleft+1, …, an đã là heap //Lưu ý: đoạn a a đã là heap – Bước 21: Hiệu chỉnh đoạn aleft, …, an thành heap – Bước 22: left = left - 1; left 1; //Hết lặp

Bước 22: left

09/11/2008

Cấu trúc dữ liệu 1

93

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

Giai đoạn 1 Giai đoạn 1

0 1 2 3 4 5 6 7

12

2

8

5

1

6

4

15

09/11/2008

Cấu trúc dữ liệu 1

94

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

Giai đoạn 1 Giai đoạn 1

0 1 2 joint 5 4 joint 7 6 curr 3

5 515 15

12

2

8

6

1

4

5

left l ft

09/11/2008

Cấu trúc dữ liệu 1

95

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

Giai đoạn 1 Giai đoạn 1

curr 1 0 joint 3 joint 4 5 6 joint 7 2

2

12

15

1

6

4

5

8 8

left l ft

09/11/2008

Cấu trúc dữ liệu 1

96

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

Giai đoạn 1 Giai đoạn 1

curr 0 joint 2 joint 1 3 4 5 6 7

12

8

15

5

1

6

4

2

left l ft

09/11/2008

Cấu trúc dữ liệu 1

97

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

Giai đoạn 1 Giai đoạn 1

0 1 2 3 4 5 6 7

15

12

8

5

1

6

4

2

09/11/2008

Cấu trúc dữ liệu 1

98

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort Giai đoạn 2 • Vấn đề: Sắp xếp heap a0, …, an-1 thành dãy tăng dần n 1 (cid:206)dãy a1, …, aright là heap. //Đặt: right = n-1 (cid:206)dãy a1, …, aright là heap. //Đặt: right • Ý tưởng:

g

– Theo tính chất 2: a sẽ là phần tử lớn nhất vì vậy vị trí đúng Theo tính chất 2: a0 sẽ là phần tử lớn nhất, vì vậy vị trí đúng của a0 phải là right - cuối dãy. → Đổi chỗ (a0, aright) (cid:206)được thêm một phần tử ở đúng vị trí

à dã à hiệ Giả

– Theo tính chất 3: dãy con a1, …, aright-1 vẫn là heap → Giảm right, thêm a0 vào dãy và hiệu chỉnh lại hỉ h l i i ht thê → dãy a0, …, aright là heap.

09/11/2008

Cấu trúc dữ liệu 1

99

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort Giai đoạn 2

B ớ 1 i h

hiệ ừ

h

//input: dãy (a, n) là heap //output: dãy (a, n) sắp tăng dần • Bước 1: right = n-1; //Bắt đầu thực hiện từ cuối dãy ối dã 1 //Bắ đầ • Bước 2: Trong khi right > 0 hầ tử lớ

) ề ị t í

hất (

//Đ //Đưa phần tử lớn nhất (a0)về vị trí right i ht – Bước 21: Hoánvị (a0 , aright);

//Loại bỏ phần tử lớn nhất ra khỏi heap //Loại bỏ phần tử lớn nhất ra khỏi heap

g

– Bước 22: right := right -1; – Bước 23: Hiệu chỉnh đoạn a0, a1, …, aright thành heap //Hết lặp

09/11/2008

Cấu trúc dữ liệu 1

100

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

Giai đoạn 2ạ

0 1 2 3 4 5 6 7

15

12

8

5

1

6

4

2

right

swap(a0, aright)

09/11/2008

Cấu trúc dữ liệu 1

101

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort Giai đoạn 2

curr curr 0 joint joint 1 joint joint 2 3 4 5 6 7

2

12

8

5

1

6

4

15

right

Shift(a, 0, right)

09/11/2008

Cấu trúc dữ liệu 1

102

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort Giai đoạn 2

0 1 2 3 4 5 6 7

12

5

8

2

1

6

4

15

right

swap(a0, aright)

09/11/2008

Cấu trúc dữ liệu 1

103

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort Giai đoạn 2

curr curr 0 joint joint 1 joint joint 2 3 4 joint joint 5 7 6

4

5

8

2

1

6

15

12

right

Shift(a, 0, right)

09/11/2008

Cấu trúc dữ liệu 1

104

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort Giai đoạn 2

0 1 2 3 4 5 6 7

8

5

6

2

1

4

12

15

right

swap(a0, aright)

09/11/2008

Cấu trúc dữ liệu 1

105

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort Giai đoạn 2

0 1 2 3 4 5 6 7

4

5

6

2

1

8

12

15

1 1

2 2

4 4

5

6 6

8 8

12 12

15 1

09/11/2008

Cấu trúc dữ liệu 1

106

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort Hiệu chỉnh Heap

ệu c

ợp

left

• Vấn đề: dãy con aleft+1, aleft+2, …, aright là heap, cần hiệu chỉnh lại để aleft, …, aright là heap ạ để aleft, …, aright à eap • Ý tưởng: do aleft+1, aleft+2, …, aright là heap nên tất cả các phần tử này đều đã thỏa điều kiện liên đới (cid:206) các phần tử này đều đã thỏa điều kiện liên đới (cid:206) vấn đề trở thành: kiểm tra quan hệ liên đới của aleft và đổi chỗ aleft với liên đới thích hợp của nó nếu quan hệ liên đới bị vi phạm; sau khi hiệu chỉnh sự vi phạm điều kiện liên đới có thể lan truyền đến các vị trí mới hiệu chỉnh.

09/11/2008

Cấu trúc dữ liệu 1

107

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort Hiệu chỉnh Heap

0 curr 1 joint 3 joint 4 2 5 6 joint 7

2

15

1

8

6

4

2 5

right left

09/11/2008

Cấu trúc dữ liệu 1

108

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort Hiệu chỉnh Heap

ị t í

Nhận xét: Quá trình hiệu chỉnh có nhiều bước đổi chỗ trung gian không cần thiết. đổi chỗ trung gian không cần thiết • Trong ví dụ: đổi chỗ (2, 15), sau đó đổi chỗ tiế (2 5) tiếp (2, 5): vị trí cuối cùng của 2 là 8, 2 ở vị trí ủ 2 là 8 2 ở ị t í ối ù 4 chỉ là tạm thời, không cần thiết.

ể

ỗ

• Có thể thực hiện việc dời chỗ hàng loạt, sau đó đưa giá trị cần hiệu chỉnh vào đúng chỗ

09/11/2008

Cấu trúc dữ liệu 1

109

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort Hiệu chỉnh Heap

dã

là h

//input: dãy con aleft+1, aleft+2, …, aright là heap // //output: dãy con aleft, aleft+1, …, aright là heap • Bước 1:

– curr = left; x = acurr; //Bắt đầu kiểm tra từ vị trí left – joint = 2*curr + 1; //Liên đới thứ nhất của curr (j

g )

g

• Bước 2: Trong khi (joint ≤ right) //Còn liên đới để xét – Bước 21: Nếu (joint < right) && (ajoint+1 > ajoint)

joint = joint + 1; //joint: vị trí liên đới lớn nhất

//Thỏa điều kiện liên đới //Thỏa điều kiện liên đới

– Bước 22: Nếu ajoint ≤ x Bước 22: Nếu ajoint ≤ x

Chuyển đến Bước 3

– Bước 23: acurr = ajoint; curr = joint; joint = 2*curr + 1;

//Hết lặp //Hết lặp • Bước 3: acurr = x;

09/11/2008

Cấu trúc dữ liệu 1

110

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

Hiệu chỉnh Heap Hiệu chỉnh Heap

0 curr 1 joint 3 ??? 4 2 5 6 joint 7

5 5 2 2

2 2

15 15

1 1

8 8

6 6

4 4

right right left l ft

09/11/2008

Cấu trúc dữ liệu 1

111

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort Cài đặt

• Để cài đặt giải thuật Heapsort cần xây dựng các thủ

ể đổi d h h

tục: – Thủ tục hiệu chỉnh dãy aleft, aleft+1, …, aright thành heap: void Shift(int a[],int left,int right) – Thủ tục chuyển đổi dãy a0, a2, …, an-1 thành heap: h h h void CreateHeap(int a[], int n ) – Thủ tục sắp xếp dãy a0, a2, …, an-1 tăng dần: tăng dần: void HeapSort(int a[], int n)

Thủ tục sắp xếp dãy a a a

09/11/2008

Cấu trúc dữ liệu 1

112

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort Cài đặt void Shift (int a[], int left, int right) { {

x, curr, joint;

int curr = left; joint =2*curr+1 ; // ajoint: phần tử liên đới x = a[curr]; x = a[curr]; while (joint <= right) {

if (joint < right) // nếu có đủ 2 phần tử liên đới if (joint < right) // nếu có đủ 2 phần tử liên đới

if (a[joint] < a[joint+1])

q

joint = joint+1; j

if (a[joint]

} a[curr] = x;

} 09/11/2008

Cấu trúc dữ liệu 1

113

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

Cài đặt

void CreateHeap(int a[], int n) {

left;

int //left: vị trí phần tử cần ghép thêm for (left = (n-1)/2; left >= 0; left --) for (left = (n-1)/2; left >= 0; left --)

Shift(a, left, n-1);

}

09/11/2008

Cấu trúc dữ liệu 1

114

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

HeapSort (int a[], int n)

Cài đặt void {

g t; right;

hil

int t CreateHeap(a, n); //sắp xếp dãy a thành heap right = n-1; // right là vị trí đúng cho phần tử lớn nhất while (right > 0) ( i ht > 0) {

swap(a[0],a[right]); right --; Shift(a,0,right);

}}

}

09/11/2008

Cấu trúc dữ liệu 1

115

2.3. Các giải thuật sắp xếp nội

2.3.7. Sắp xếp cây –Heap sort 2 3 7 Sắp xếp cây Heap sort

Đánh giá

• Việc đánh giá một cách chính xác giải

thuật Heapsort rất phức tạp. Tuy nhiên, có thể đánh giá một cách tương đối dựa vào một số nhận xét: một cách tương đối dựa vào một số nhận xét: – Khi xem xét heap ở dạng cây quan hệ liên đới (cid:198) các phần tử của heap tạo thành cây nhị phân có độ cao h≈log2n. – Ở mỗi bước hiệu chỉnh, số phép điều chỉnh các vi phạm

p ạ ị p y ộ g2

– Ở cả giai đoạn 1 và giai đoạn 2 số phép hiệu chỉnh không ố

(cid:206)Trong trường hợp xấu nhất độ phức tạp thuật toán (cid:206)Trong trường hợp xấu nhất độ phức tạp thuật toán

O(nlog2n)

liên đới không vượt quá chiều cao h của cây liên đới. Ở vượt quá n

09/11/2008

Cấu trúc dữ liệu 1

116

2.3. Các giải thuật sắp xếp nội

2.3.8. Sắp xếp chèn với độ dài bước giảm 2 3 8 Sắp xếp chèn với độ dài bước giảm

dần - Shell sort

p g p p ự p g p p p y

Ý tưởng Ý t ở • ShellSort là một phương pháp cải tiến của phương pháp sắp xếp chèn trực tiếp. Ý tưởng của phương pháp sắp xếp này là xem xét dãy ban đầu như những dãy con gồm các phần tử ở cách nhau k vị trí; tiến hành sắp xếp trên từng dãy con; giảm dần bước k đến khi k = 1 (cid:206) sắp xếp xong. dần bước k đến khi k = 1 (cid:206) sắp xếp xong

• Dãy ban đầu : a0, a1, ..., an-1 được xem như sự xen kẽ của các

... ...

: a0 : a1

ak ak+1

a2k a2k+1

dãy con sau : – Dãy con thứ nhất – Dãy con thứ hai – .... – Dãy con thứ k

...

: ak-1

a2k-1

a3k-1

09/11/2008

Cấu trúc dữ liệu 1

117

2.3. Các giải thuật sắp xếp nội

2.3.8. Sắp xếp chèn với độ dài bước giảm 2 3 8 Sắp xếp chèn với độ dài bước giảm

dần - Shell sort

Ý tưởng Ý tưởng • Việc sắp xếp các phần tử trong cùng dãy con sẽ làm cho các phần tử được đưa về vị trí đúng tương đối (chỉ đúng trong dãy con so với toàn bộ các phần tử trong dãy ban đầu có thể chưa con, so với toàn bộ các phần tử trong dãy ban đầu có thể chưa đúng) một cách nhanh chóng.

g g y

• Khi khoảng cách k giảm tạo thành các dãy con mới (cid:206) một phần tử được so sánh với nhiều phần tử khác trước đó không ở cùng dãy con với nó.

• Thuật toán dừng sau khi sắp xong dãy con với k = 1, thuật toán • Thuật toán dừng sau khi sắp xong dãy con với k 1 thuật toán lúc này thực hiện như thuật toán chèn trực tiếp. Tuy nhiên, phần lớn các phần tử trong dãy đã có thứ tự bộ phận.

• Các phần tử trên cùng một dãy con cách nhau k vị trí được gọi

là cùng dãy liên đới bước k.

09/11/2008

Cấu trúc dữ liệu 1

118

2.3. Các giải thuật sắp xếp nội

2.3.8. Sắp xếp chèn với độ dài bước giảm 2 3 8 Sắp xếp chèn với độ dài bước giảm

dần - Shell sort

//h[step]: độ dài bước lặp

Thuật toán Thuật toán //input: dãy (a, n); dãy (h, k): k độ dài các bước lặp - const //output: dãy (a, n) là được sắp tăng dần //output: dãy (a, n) là được sắp tăng dần • Bước 1: step = 1; • Bước 2: Trong khi (step ≤ k) //độ dài bước còn >1 Bước 2: Trong khi (step ≤ k) //độ dài bước còn >1 – Bước 21: len = h[step]; //lấy độ dài bước – Bước 22: Lặp với i=len+1 .. n-1 //sắp xếp các dãy liên p

ặp y

p đới bước len Chèn a[i] vào dãy liên đới bước len;

//Hết lặp

– Bước 23: step ++;

Cấu trúc dữ liệu 1

119

09/11/2008

2.3. Các giải thuật sắp xếp nội

2.3.8. Sắp xếp chèn với độ dài bước giảm 2 3 8 Sắp xếp chèn với độ dài bước giảm

dần - Shell sort

Ví dụ Ví dụ

; len = 5;

; h = (5, 3, 1); k = 3; ,

( ,

);

joint 0 0 1 1 2 2 3 3 4 4 curr 5 5 6 6 7 7

12

2

8

5

1

6

4

15

09/11/2008

Cấu trúc dữ liệu 1

120

2.3. Các giải thuật sắp xếp nội

2.3.8. Sắp xếp chèn với độ dài bước giảm 2 3 8 Sắp xếp chèn với độ dài bước giảm

dần - Shell sort

Ví dụ Ví dụ

; len = 5;

; h = (5, 3, 1); k = 3; ,

( ,

);

0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7

6

2

8

5

1

12

4

15

09/11/2008

Cấu trúc dữ liệu 1

121

2.3. Các giải thuật sắp xếp nội

2.3.8. Sắp xếp chèn với độ dài bước giảm 2 3 8 Sắp xếp chèn với độ dài bước giảm

dần - Shell sort

Ví dụ Ví dụ

; h = (5, 3, 1); k = 3; ,

( ,

);

; len = 3;

joint 0 0 1 1 2 2 curr 3 3 4 4 5 5 6 6 7 7

6

2

15

5

1

12

4

8

09/11/2008

Cấu trúc dữ liệu 1

122

2.3. Các giải thuật sắp xếp nội

2.3.8. Sắp xếp chèn với độ dài bước giảm 2 3 8 Sắp xếp chèn với độ dài bước giảm

dần - Shell sort

Ví dụVí dụ

; h = (5, 3, 1); k = 3; ,

( ,

);

; len = 3;

joint 0 0 1 1 2 2 joint 3 3 4 4 5 5 curr 6 6 7 7

5

1

12

6

2

15

4

8

09/11/2008

Cấu trúc dữ liệu 1

123

2.3. Các giải thuật sắp xếp nội

2.3.8. Sắp xếp chèn với độ dài bước giảm 2 3 8 Sắp xếp chèn với độ dài bước giảm

dần - Shell sort

Ví dụVí dụ

; h = (5, 3, 1); k = 3; ,

( ,

);

; len = 3;

0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7

4

1

12

5

2

15

6

8

09/11/2008

Cấu trúc dữ liệu 1

124

2.3. Các giải thuật sắp xếp nội

2.3.8. Sắp xếp chèn với độ dài bước giảm 2 3 8 Sắp xếp chèn với độ dài bước giảm

dần - Shell sort

Ví dụVí dụ

; h = (5, 3, 1); k = 3; ,

( ,

);

; len = 1;

joint 0 0 jointcurr 1 1 joint 2 2 3 3 4 4 5 5 6 6 7 7

4

1

12

5

2

15

6

8

09/11/2008

Cấu trúc dữ liệu 1

125

2.3. Các giải thuật sắp xếp nội

2.3.8. Sắp xếp chèn với độ dài bước giảm 2 3 8 Sắp xếp chèn với độ dài bước giảm

dần - Shell sort

Ví dụVí dụ

; h = (5, 3, 1); k = 3; ,

( ,

);

; len = 1;

joint 0 0 joint 1 1 joint 2 2 joint joint 3 3 jointcurr 4 4 joint 5 5 joint 6 6 7 7

1

4

5

12

2

15

6

8

09/11/2008

Cấu trúc dữ liệu 1

126

2.3. Các giải thuật sắp xếp nội

2.3.8. Sắp xếp chèn với độ dài bước giảm 2 3 8 Sắp xếp chèn với độ dài bước giảm

dần - Shell sort

Ví dụVí dụ

0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7

1

2

4

5

6

8

12

15

09/11/2008

Cấu trúc dữ liệu 1

127

2.3. Các giải thuật sắp xếp nội

2.3.8. Sắp xếp chèn với độ dài bước giảm 2 3 8 Sắp xếp chèn với độ dài bước giảm

dần - Shell sort

Cài đặt Cài đặt

void ShellSort(int a[], int n) {

int h[], k; int step, i, pos, x, len; for (step = 0; step < k; step ++) {

ầ

ế

len = h[step]; //khoảng cách 2 phần tử liên tiếp của dãy con for (i = len; i < n; i++) {

[i]

x = a[i]; for(pos=i;(pos-len>=0)&&(x

a[pos] = a[pos-len];

a[pos] x; a[pos] = x;

}

}

09/11/2008

Cấu trúc dữ liệu 1

128

}

2.3. Các giải thuật sắp xếp nội

2.3.8. Sắp xếp chèn với độ dài bước giảm 2 3 8 Sắp xếp chèn với độ dài bước giảm

dần - Shell sort

Đánh giá Đá h iá • Yếu tố quyết định tính hiệu quả của thuật toán: – Cách chọn khoảng cách h trong từng bước sắp xếp – Số bước sắp xếp.

• Giả sử quyết định sắp xếp k bước, các khoảng

cách chọn phải thỏa điều kiện : cách chọn phải thỏa điều kiện : hi > hi+1 và hk = 1

09/11/2008

Cấu trúc dữ liệu 1

129

2.3. Các giải thuật sắp xếp nội

2.3.8. Sắp xếp chèn với độ dài bước giảm 2 3 8 Sắp xếp chèn với độ dài bước giảm

dần - Shell sort

iá t ị kh ả

Đánh giá Đá h iá • Chưa có tiêu chuẩn rõ ràng trong việc lựa chọn dãy giá trị khoảng cách tốt nhất. Một gợi ý: dãy được á h tốt hất Một ợi ý dã đượ chọn không nên có các số là bội số của nhau.

• Một số dãy được Knuth đề nghị : • Một số dãy được Knuth đề nghị :

hi = (hi-1 - 1)/3 và hk = 1, k = log3n-1 ví dụ: 121, 40, 13, 4, 1 121 40 13 4 1

í d

hay

1)/2 à h

1 k

(h

l

hi = (hi-1 - 1)/2 và hk = 1, k = log2n-1 h 1 ví dụ: 15, 7, 3, 1

Cấu trúc dữ liệu 1

09/11/2008

130

2.3. Các giải thuật sắp xếp nội

2.3.8. Sắp xếp chèn với độ dài bước giảm 2 3 8 Sắp xếp chèn với độ dài bước giảm

dần - Shell sort

ất hứ t

ột ố h

hí

đ

• Hiệu quả của thuật toán còn phụ thuộc vào dãy các độ á độ ò

ả ủ th ật t á

h th ộ

à dã

Đánh giá Đá h iá • Việc đánh giá giải thuật Shellsort dẫn đến những vấn đề toán học rất phức tạp, thậm chí một số chưa được đề t á h thậ chứng minh. Hiệ dài được chọn.

• Trong trường hợp chọn dãy độ dài theo công thức • Trong trường hợp chọn dãy độ dài theo công thức

hi = (hi-1 - 1)/2 và hk = 1, k = log2n-1

iải th ật ó độ hứ t

thì giải thuật có độ phức tạp ≈ n1,2 << n2 1 2 << 2 thì

09/11/2008

Cấu trúc dữ liệu 1

131

2.3. Các giải thuật sắp xếp nội

2.3.9. Sắp xếp dựa trên phân hoạch – Quick 2 3 9 Sắp xếp dựa trên phân hoạch Quick

sort Ý tưởng Ý tưởng • Một vài hạn chế của thuật toán Đổi chỗ trực tiếp:

– Độ phức tạp của thuật toán O(n2) (cid:206) khi n đủ lớn thuật toán sẽ ẽ

đủ lớ th ật t á

– Mỗi lần đổi chỗ chỉ thay đổi 1 cặp phần tử trong nghịch thế; các Mỗi lần đổi chỗ chỉ thay đổi 1 cặp phần tử trong nghịch thế; các (*) chỉ cần thực hiện 1 lần trường hợp như: i < j < k và ai > aj > ak đổi chỗ (ai, ak): thuật toán không làm được. ủ th ật t á O( 2) (cid:206) khi Độ hứ t rất chậm

y

g p

ạ

ậ

(cid:206) Ý tưởng: phân chia dãy thành các đoạn con (cid:198) tận dụng ụ g được các phép đổi chỗ dạng (*) và làm giảm độ dài dãy khi sắp xếp (cid:198) cải thiện đáng kể độ phức tạp của thuật t átoán.

09/11/2008

Cấu trúc dữ liệu 1

132

2.3. Các giải thuật sắp xếp nội

2.3.9. Sắp xếp dựa trên phân hoạch – Quick 2 3 9 Sắp xếp dựa trên phân hoạch Quick

sort Ý tưởng Ý tưởng • Giải thuật QuickSort sắp xếp dãy a0, a1 ..., an-1 dựa trên việc

hầ ử ó iá ị khô

Phầ 3 Gồ

bé h

á

phân hoạch dãy ban đầu thành 3 phần: phân hoạch dãy ban đầu thành 3 phần: – Phần 1: Gồm các phần tử có giá trị không lớn hơn x – Phần 2: Gồm các phần tử có giá trị bằng x – Phần 3: Gồm các phần tử có giá trị không bé hơn x

với x là giá trị của một phần tử tùy ý trong dãy ban đầu. • Sau khi thực hiện phân hoạch dãy ban đầu được phân thành 3 Sau khi thực hiện phân hoạch, dãy ban đầu được phân thành 3 đoạn: 1. ak ≤ x , với k = 0 .. j 2 2. ak = x , với k = j+1 .. i-1 j 1 i 1 ới k 3. ak ≥ x , với k = i..n-1

09/11/2008

Cấu trúc dữ liệu 1

133

2.3. Các giải thuật sắp xếp nội

2.3.9. Sắp xếp dựa trên phân hoạch – Quick 2 3 9 Sắp xếp dựa trên phân hoạch Quick

sort Ý tưởng Ý tưởng

• Đoạn thứ 2 đã có thứ tự. • Nếu các đoạn 1 và 3 chỉ có 1 phần tử thì chúng cũng đã

có thứ tự, khi đó dãy con ban đầu đã được sắp.

• Ngược lại, nếu các đoạn 1 và 3 có nhiều hơn 1 phần tử thì dãy con ban đầu chỉ có thứ tự khi các đoạn 1, 3 được sắpsắp.

• Để sắp xếp các đoạn 1 và 3, ta lần lượt tiến hành việc phân hoạch từng dãy con theo cùng phương pháp phân phân hoạch từng dãy con theo cùng phương pháp phân hoạch dãy ban đầu vừa trình bày …

09/11/2008

Cấu trúc dữ liệu 1

134

2.3. Các giải thuật sắp xếp nội

2.3.9. Sắp xếp dựa trên phân hoạch – Quick 2 3 9 Sắp xếp dựa trên phân hoạch Quick

sort Thuật toán Thuật toán //input: dãy con (a, left, right) //output: dãy con (a, left, right) được sắp tăng dần //output: dãy con (a left right) được sắp tăng dần • Bước 1: Nếu left ≥ right //dãy có ít hơn 2 phần tử

Kết thúc; Kết thúc;

//dãy đã được sắp xếp //dãy đã được sắp xếp

• Bước 2: Phân hoạch dãy aleft … aright thành các đoạn: aleft..

aj, aj+1.. ai-1, ai.. aright aj, aj+1.. ai 1, ai.. aright

p

ạ

left

//Đoạn 0 ≤x - Đoạn 2: aj+1.. ai-1 = x - Đoạn 3: ai.. aright ≥x • Bước 3: Sắp xếp đoạn 1: aleft.. aj p j • Bước 4: Sắp xếp đoạn 3: ai.. aright

09/11/2008

Cấu trúc dữ liệu 1

135

2.3. Các giải thuật sắp xếp nội

2.3.9. Sắp xếp dựa trên phân hoạch – Quick 2 3 9 Sắp xếp dựa trên phân hoạch Quick

sort Phân hoạch dãy Phân hoạch dãy

ố

ầ

//input: dãy con aleft, …, aright //output: dãy con chia thành 3 đoạn: đoạn 1 ≤ đoạn 2 ≤ đoạn 3 • Bước 1: Chọn tùy ý một phần tử a[p] trong dãy con là giá trị mốc: x=a[p]; • Bước 2: Duyệt từ 2 đầu dãy để phát hiện và hiệu chỉnh cặp phần tử a[i], a[j]

ệ

p ạ

vi phạm điều kiện – Bước 21: i = left; j = right; – Bước 22: Trong khi (a[i]x) j--; ; Bước 23: Trong khi (a[j]>x) j – Bước 24: Nếu i<= j // a[i] ≥ x ≥ a[j] mà a[j] đứng sau a[i]

j--;

• Hoán vị (a[i],a[j]); ế

– Bước 25: Nếu i < j:

i++; Lặp lại Bước 22.//chưa xét hết mảng

ế

//Hết duyệt

09/11/2008

Cấu trúc dữ liệu 1

136

2.3. Các giải thuật sắp xếp nội

2.3.9. Sắp xếp dựa trên phân hoạch – Quick 2 3 9 Sắp xếp dựa trên phân hoạch Quick

sort Ví dụ Ví dụ

Phân hoạch dãy Phân hoạch dãy

X 5

i 0 1 2 3 4 5 6 j 7

12

2

8

5

1

6

4

15

right left

STOP

STOP

Not less than XNot greater than X

09/11/2008

Cấu trúc dữ liệu 1

137

2.3. Các giải thuật sắp xếp nội

2.3.9. Sắp xếp dựa trên phân hoạch – Quick 2 3 9 Sắp xếp dựa trên phân hoạch Quick

sort Ví dụ Ví dụ

Phân hoạch dãy Phân hoạch dãy

X 5

0 i 1 2 3 4 j 5 6 7

4

2

8

5

1

6

12

15

right left

STOP

STOP

Not less than XNot greater than X

09/11/2008

Cấu trúc dữ liệu 1

138

2.3. Các giải thuật sắp xếp nội

2.3.9. Sắp xếp dựa trên phân hoạch – Quick 2 3 9 Sắp xếp dựa trên phân hoạch Quick

sort Ví dụVí dụ

0 1 j 2 3 i 4 5 6 7

4

2

1

5

8

6

12

15

right left

09/11/2008

Cấu trúc dữ liệu 1

139

2.3. Các giải thuật sắp xếp nội

2.3.9. Sắp xếp dựa trên phân hoạch – Quick 2 3 9 Sắp xếp dựa trên phân hoạch Quick

sort Ví dụ Ví dụ

Phân hoạch dãy Phân hoạch dãy

X 6

0 1 2 3 5 6 i 4 j 7

1

2

4

5

6

12

8

15

right left

Sắp xếp đoạn 3 Sắp xếp đoạn 3

STOP STOP

STOP STOP

Not less than X

09/11/2008

Not greater than X 140

Cấu trúc dữ liệu 1

2.3. Các giải thuật sắp xếp nội

2.3.9. Sắp xếp dựa trên phân hoạch – Quick 2 3 9 Sắp xếp dựa trên phân hoạch Quick

sort Ví dụVí dụ

0 1 2 3 j 4 i 5 6 7

1

2

4

5

6

8

12

15

right left

Sắp xếp đoạn 3 Sắp xếp đoạn 3

09/11/2008

Cấu trúc dữ liệu 1

141

2.3. Các giải thuật sắp xếp nội

2.3.9. Sắp xếp dựa trên phân hoạch – Quick 2 3 9 Sắp xếp dựa trên phân hoạch Quick

sort Ví dụVí dụ

0 1 2 3 4 5 6 7

1

2

4

5

6

8

12

15

09/11/2008

Cấu trúc dữ liệu 1

142

2.3. Các giải thuật sắp xếp nội

2.3.9. Sắp xếp dựa trên phân hoạch – Quick 2 3 9 Sắp xếp dựa trên phân hoạch Quick

sort Cài đặt Cài đặt void QuickSort(int a[], int left, int right) {

return;

int i, j, x; if (left >= right) x = a[(left+right)/2]; // chọn phần tử giữa làm giá trị mốc i = left; j = right; j) { while(i < j) {

( while(a[i] < x) i++; while(a[j] > x) j--; if(i <= j) {

( [i]

[j])

swap(a[i], a[j]); i++ ; j--;

}

} QuickSort(a, left, j); QuickSort(a, i, right);

} 09/11/2008

Cấu trúc dữ liệu 1

143

2.3. Các giải thuật sắp xếp nội

2.3.9. Sắp xếp dựa trên phân hoạch – Quick 2 3 9 Sắp xếp dựa trên phân hoạch Quick

sort Nhận xét Nhận xét • Về nguyên tắc, có thể chọn giá trị mốc x là một phần tử tùy ý trong dãy, nhưng để đơn giản, phần tử có vị trí giữa thường được chọn, khi đó p = (l + r) / 2.

• Giá trị mốc x được chọn sẽ có tác động đến hiệu quả thực hiện

vị (median), nhiều nhất nếu x là cực trị của dãy.

– Tuy nhiên do chi phí xác định phần tử median quá cao nên trong thực tế người ta không chọn phần tử này mà chọn phần tử nằm chính giữa dãy làm mốc với hy vọng nó có thể gần với giá trị median.

thuật toán vì nó quyết định số lần phân hoạch. thuật toán vì nó quyết định số lần phân hoạch – Số lần phân hoạch sẽ ít nhất nếu ta chọn được x là phần tử trung

09/11/2008

Cấu trúc dữ liệu 1

144

2.3. Các giải thuật sắp xếp nội

2.3.9. Sắp xếp dựa trên phân hoạch – Quick 2 3 9 Sắp xếp dựa trên phân hoạch Quick

sort Đánh giá Đánh giá • Hiệu quả phụ thuộc vào việc chọn giá trị mốc:

– Trường hợp tốt nhất: mỗi lần phân hoạch đều chọn Trường hợp tốt nhất: mỗi lần phân hoạch đều chọn phần tử median làm mốc, khi đó dãy được phân chia thành 2 phần bằng nhau và cần log2(n) lần phân hoạch thì sắp xếp xong. ế

ắ

tiể ) là

ẽ bị hâ

hi

ạ g

) p

ậy

p

ạ

(

,

– Nếu mỗi lần phân hoạch chọn phần tử có giá trị cực đại (hay cực tiểu) là mốc (cid:206) dãy sẽ bị phân chia thành ố (cid:206) dã đ i (h thà h 2 phần không đều: một phần chỉ có 1 phần tử, phần còn lại gồm (n-1) phần tử, do vậy cần phân hoạch n lần mới sắp xếp xong.

09/11/2008

Cấu trúc dữ liệu 1

145

2.3. Các giải thuật sắp xếp nội

2.3.9. Sắp xếp dựa trên phân hoạch – Quick 2 3 9 Sắp xếp dựa trên phân hoạch Quick

sort Độ phức tạp thuật toán Độ hứ t

th ật t á

Trường hợp

Độ phức tạp

Tốt nhất

O(nlogn)

Trung bình

O(nlogn)

Xấu nhất Xấu nhất

O(n2) O(n2)

09/11/2008

Cấu trúc dữ liệu 1

146

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Ý tưởng Ý tưởng

• Giải thuật Merge sort sắp xếp dãy a0, a1, ..., an-1 dựa trên

nhận xét sau: nhận xét sau:

• Mỗi dãy a0, a1, ..., an-1 bất kỳ là một tập hợp các dãy

p

con liên tiếp mà mỗi dãy con đều đã có thứ tự. ự y – Ví dụ: dãy 12, 2, 8, 5, 1, 6, 4, 15 có thể coi như gồm 5 dãy con không giảm (12); (2, 8); (5); (1, 6); (4, 15).

• Dãy đã có thứ tự coi như có 1 dãy con. • Hướng tiếp cận: tìm cách làm giảm số dãy con không

giảm của dãy ban đầu.

ầ

09/11/2008

Cấu trúc dữ liệu 1

147

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Ý tưởng Ý tưởng

– Phương án phân hoạch dãy ban đầu thành các dãy con. – Phương án làm giảm số dãy con Phương án làm giảm số dãy con.

• Các vấn đề cần giải quyết:

– Phương án 1: Phân hoạch dãy theo các đường chạy (cid:198) sắp xếp trộn tự

nhiên.

– Phương án 2: Phân hoạch thành các dãy con có số phần tử bằng nhau

(1, 2, 4, …) (cid:198) sắp xếp trộn trực tiếp.

• Phân hoạch dãy ban đầu thành các dãy con tăng dần:

– Các dãy con tăng dần sẽ được tách ra 2 dãy phụ theo nguyên tắc phân

• Làm giảm số dãy con:

phối đều luân phiên. phối đều luân phiên.

– Trộn từng cặp dãy con của hai dãy phụ thành một dãy con của dãy ban

đầu (cid:198) dãy mới có số lượng dãy con giảm đi so với dãy ban đầu.

09/11/2008

Cấu trúc dữ liệu 1

148

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

ầ

Thuật toán Thuật toán //input: dãy (a, n) //output: dãy (a, n) được sắp tăng dần • Bước 1 : k = 1; // dãy con có 1 phần tử là dãy không giảm • Bước 2 : Lặp trong khi (k < n) // dãy còn hơn 1 dãy con

h h

h

d

d

– Bước 21: Phân phối đều luân phiên dãy a0, a1, …, an-1 thành 2 dãy b, b hi

hối đề l c theo từng nhóm k phần tử liên tiếp nhau.

0

3k 1

2k

//b = a0, …, ak-1, a2k, …, a3k-1, … k 1 //c = ak, …, a2k-1, a3k, …, a4k-1, …

– Bước 22: Trộn từng cặp dãy con gồm k phần tử của 2 dãy b, c vào a. – Bước 23: k = k*2; k*2

B ớ 23 k

//Hết lặp

09/11/2008

Cấu trúc dữ liệu 1

149

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Ví dụ Ví dụ

Phân phối đều luân phiên

; k = 1;

0 1 2 3 4 5 6 7

12

2

8

5

1

6

4

15

09/11/2008

Cấu trúc dữ liệu 1

150

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Ví dụ Ví dụ

Phân phối đều luân phiên

; k = 1;

0 1 2 3 4 5 6 7

12

2

8

5

1

6

4

15

09/11/2008

Cấu trúc dữ liệu 1

151

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Ví dụ Ví dụ

Trộn từng cặp đường chạy

; k = 1;

0 1 2 3 4 5 6 7

4

8

12

1

5

2

6

15

09/11/2008

Cấu trúc dữ liệu 1

152

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Ví dụ Ví dụ

Trộn từng cặp đường chạy

k = 1;

0 1 2 3 4 5 6 7

4

8

12

1

5

2

6

15

09/11/2008

Cấu trúc dữ liệu 1

153

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Ví dụ Ví dụ

Phân phối đều luân phiên

; k = 2;

0 1 2 3 4 5 6 7

2

12

5

8

1

6

4

15

09/11/2008

Cấu trúc dữ liệu 1

154

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Ví dụ Ví dụ

Trộn từng cặp đường chạy

k = 2;

1 2 3 4 5 6 7 0

6

12

2

1

8

5

4

15

09/11/2008

Cấu trúc dữ liệu 1

155

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Ví dụ Ví dụ

Trộn từng cặp đường chạy

k = 2;

0 1 2 3 4 5 6 7

6

12

2

1

8

5

4

15

09/11/2008

Cấu trúc dữ liệu 1

156

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Ví dụ Ví dụ

Phân phối đều luân phiên

; k = 4;

0 1 2 3 4 5 6 7

2

5

8

12

1

4

6

15

09/11/2008

Cấu trúc dữ liệu 1

157

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Ví dụ Ví dụ

Trộn từng cặp đường chạy

k = 4;

1 2 3 4 5 6 7 0

12

5

2

8

4

1

6

15

09/11/2008

Cấu trúc dữ liệu 1

158

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Ví dụ Ví dụ

Trộn từng cặp đường chạy

; k = 4;

1 2 3 4 5 6 7 0

12

5

2

8

4

1

6

15

09/11/2008

Cấu trúc dữ liệu 1

159

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Ví dụ Ví dụ

k = 8;

0 1 2 3 4 5 6 7

1

2

4

5

6

8

12

15

STOP

Only one subarray

09/11/2008

Cấu trúc dữ liệu 1

160

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Ví dụVí dụ

0 1 2 3 4 5 6 7

1

2

4

5

6

8

12

15

09/11/2008

Cấu trúc dữ liệu 1

161

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Cài đặt Cài đặt

• Dữ liệu hỗ trợ: 2 mảng b, c:

int

b[MAX], c[MAX], nb, nc;

• Các hàm cần cài đặt: ầ

– MergeSort: Sắp xếp mảng (a, n) tăng dần void MergeSort(int a[], int n);

ố

ề

– Distribute: Phân phối đều luân phiên các dãy con độ dài k từ mảng

a vào hai mảng b và c

void Distribute(int a[], int n,

int &nb, int &nc, int k); int &nb int k); int &nc – Merge: Trộn mảng b và mảng c vào mảng a

cặp d y co ừ b v c v o

ộ

void Merge(int a[], int nb, int nc, int k); e geSuba : – MergeSubarr: Trộn 1 cặp dãy con từ b và c vào a void MergeSubarr(int a[], int nb, int nc,

int &pa, int &pb, int &pc, int k);

09/11/2008

Cấu trúc dữ liệu 1

162

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Cài đặt Cài đặt

// khai báo 2 mảng phụ ; int b[MAX], c[MAX], nb, nc; , [ ],

],

[

void MergeSort(int a[], int n) { {

int k; for (k = 1; k < n; k *= 2) {{

Distribute(a, n, nb, nc, k); Merge(a, nb, nc, k);

}}

}

09/11/2008

Cấu trúc dữ liệu 1

163

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Cài đặt Cài đặt

void Distribute(int

n,

a[], int &nb, int &nc, int k)

int

{ {

int i, pa, pb, pc; pa = pb = pc = 0; ) while (pa < n) (p {

for (i=0; (pa

b[pb] a[pa]; b[pb] = a[pa];

for (i=0; (pa

c[pc] = a[pa];

}} nb = pb; nc = pc;

} 09/11/2008

Cấu trúc dữ liệu 1

164

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Cài đặt Cài đặt

void Merge(int a[], int nb, int nc, int k) {

int pa, pb, pc; pa = pb = pc = 0; while ((pb < nb) && (pc < nc)) while ((pb < nb) && (pc < nc))

MergeSubarr(a, nb, nc, pa, pb, pc, k);

while (pb < nb)

a[pa ++] = b[pb ++];

while (pc < nc)

a[pa ++] = c[pc ++]; a[pa ++] = c[pc ++];

}

09/11/2008

Cấu trúc dữ liệu 1

165

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Cài đặt Cài đặt

void MergeSubarr(int a[], int nb, int nc,

int &pa, int &pb, int &pc, int k)

{ {

rc = min(nc, pb+k);

int rb, rc; rb = min(nb, pb+k); while ((pb < rb) && (pc < rc)) while ((pb < rb) && (pc < rc))

if (b[pb] < c[pc])

else

a[pa ++] = b[pb ++]; a[pa ++] = c[pc ++];

while (pb < rb)

a[pa ++] = b[pb ++];

while (pc < rc)

a[pa ++] = c[pc ++];

}

09/11/2008

Cấu trúc dữ liệu 1

166

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Đánh giá Đánh giá

Giải thuật trộn trực tiếp là phương pháp trộn đơn giản nhất: • Việc phân hoạch thành các dãy con chỉ là tách dãy thành các

dãy con không giảm độ dài k.

• Độ dài của dãy con là 1, 2, 4, 8, … đảm bảo dãy con luôn là

dãy con không giảm sau mỗi bước tách - trộn. dãy con không giảm sau mỗi bước tách trộn

ệ q

ầ ế

• Không sử dụng thông tin về thứ tự của dãy ban đầu → 2 hệ quả: • Độ phức tạp thuật toán không phụ thuộc vào dãy ban đầu. • Một dãy con không giảm đang có sẵn bị chia nhỏ thành các dãy không cần thiết → cải tiến thành thuật toán: Trộn tự nhiên ế (Natural Merge sort).

09/11/2008

Cấu trúc dữ liệu 1

167

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Đánh giá Đánh giá

ỗ ầ

• Số lần thực hiện việc chia luân phiên và trộn: • Sau mỗi lần tách – trộn, độ dài K của dãy con tăng gấp đôi (cid:198) Số lần tách – trộn trong thuật toán: log2n .

• Chi phí thực hiện tách - trộn tỉ lệ thuận với n. (cid:206) Chi phí thực hiện của giải thuật MergeSort là

(

g2 ) O(nlog2n).

09/11/2008

Cấu trúc dữ liệu 1

168

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Đánh giá Đánh giá

th ật t á

dù

đ

ậ

• Một nhược điểm lớn nữa của các thuật toán trộn là khi cài đặt thuật toán đòi hỏi thêm trộn là khi cài đặt thuật toán đòi hỏi thêm không gian bộ nhớ để lưu các dãy phụ b, c. • Hạn chế này khó chấp nhận trong thực tế vì • Hạn chế này khó chấp nhận trong thực tế vì các dãy cần sắp xếp thường có kích thước lớn. • Vì vậy thuật toán trộn thường được dùng để để t ộ th ờ Vì sắp xếp các cấu trúc dữ liệu khác phù hợp hơn như danh sách liên kết hoặc file. h d h á h liê kết h ặ fil

09/11/2008

Cấu trúc dữ liệu 1

169

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Sắp xếp trộn tự nhiên Natural Merge Sort Sắp xếp trộn tự nhiên – Natural Merge Sort

j

i ),[ j

k ∈∀

k

a a i a a

j

a ≤ +1 k a < − 1i a a > +1j > 1

⎧ ⎪ ⎪ ⎨ ⎪ ⎩ ⎩

• Một đường chạy của dãy số a là một dãy con không giảm của cực đại của a. Nghĩa là, đường chạy r = (ai, ai+1, …, aj) phải thỏa điều kiện: ề

• Ví dụ dãy 12, 2, 8, 5, 1, 6, 4, 15 có thể coi như gồm 5 đường g , ụ y g , , , , ,

, chạy (12); (2, 8); (5); (1, 6); (4, 15).

09/11/2008

Cấu trúc dữ liệu 1

170

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Sắp xếp trộn tự nhiên Natural Merge Sort Sắp xếp trộn tự nhiên – Natural Merge Sort

ứ

iế

hắ

ì l ô

hỗ h

h

h

đ

h

ối ù

dừ

• Thuật toán trộn tự nhiên khác thuật toán trộn trực tiếp ở chỗ thay vì luôn cứng nhắc phân hâ hoạch theo dãy con có chiều dài k, việc phân h hoạch sẽ theo đơn vị là đường chạy. ta chỉ cần hỉ ầ ị là đ ờ biết số đường chạy của a sau lần phân hoạch cuối cùng là có thể biết thời điểm dừng của ủ là ó hể biế hời điể thuật toán vì dãy đã có thứ tự là dãy chỉ có một đường chạy. đ ờ

h

09/11/2008

Cấu trúc dữ liệu 1

171

2.3. Các giải thuật sắp xếp nội

2.3.10. Sắp xếp theo phương pháp trộn trực 2.3.10. Sắp xếp theo phương pháp trộn trực

tiếp – Merge sort

Sắp xếp trộn tự nhiên Natural Merge Sort Sắp xếp trộn tự nhiên – Natural Merge Sort

• Bước 1 : // Chuẩn bị g ; ạy r = 0; // r dùng để đếm số dường chạy g

• Bước 2 : Tách dãy a1, a2, …, an thành 2 dãy b, c theo nguyên

• Phân phối cho b một đường chạy; r = r+1; • Nếu a còn phần tử chưa phân phối

– Phân phối cho c một đường chạy; r = r+1;

– Bước 2.2 : Nếu a còn phần tử: quay lại bước 2.1;

tắc luân phiên từng đường chạy: – Bước 2.1 :

• Bước 3 : Trộn từng cặp đường chạy của 2 dãy b c vào a • Bước 3 : Trộn từng cặp đường chạy của 2 dãy b, c vào a. • Bước 4 : Nếu r <= 2 thì trở lại bước 2; Ngược lại: Dừng.

09/11/2008

Cấu trúc dữ liệu 1

172

2.3. Các giải thuật sắp xếp nội

2.3.11. Sắp xếp theo phương pháp cơ số 2.3.11. Sắp xếp theo phương pháp cơ số –

Radix sort

Ý tưởng Ý tưởng

• Radix Sort là một thuật toán tiếp cận theo một hướng

hoàn toàn khác.

l i d

i h

b

h

l

• Nếu như trong các thuật toán khác, cơ sở để sắp xếp luôn là việc so sánh giá trị của 2 phần tử thì Radix Sort lại dựa trên nguyên tắc phân loại thư của bưu ắ điện. Vì lý do đó Radix Sort còn có tên là Postman’s sort. sort

• Radix Sort không hề quan tâm đến việc so sánh giá trị của phần tử mà bản thân việc phân loại và trình tự của phần tử mà bản thân việc phân loại và trình tự phân loại sẽ tạo ra thứ tự cho các phần tử.

09/11/2008

Cấu trúc dữ liệu 1

173

2.3. Các giải thuật sắp xếp nội

2.3.11. Sắp xếp theo phương pháp cơ số 2.3.11. Sắp xếp theo phương pháp cơ số –

Radix sort

Ý tưởng Ý tưởng

• Để chuyển một khối lượng thư lớn đến tay người nhận ở nhiều địa phương khác nhau, bưu điện thường tổ chức một hệ thống phân loại thư phân cấp. ấ

• Trước tiên, các thư đến cùng một tỉnh, thành phố sẽ được sắp

chung vào một lô để gửi đến tỉnh thành tương ứng. chung vào một lô để gửi đến tỉnh thành tương ứng

• Bưu điện các tỉnh thành này lại thực hiện công việc tương tự. Các thư đến cùng một quận, huyện sẽ được xếp vào chung một lô và gửi đến quận, huyện tương ứng.

• Cứ như vậy, các bức thư sẽ được trao đến tay người nhận một cách có hệ thống mà công việc sắp xếp thư không quá nặng cách có hệ thống mà công việc sắp xếp thư không quá nặng nhọc.

09/11/2008

Cấu trúc dữ liệu 1

174

2.3. Các giải thuật sắp xếp nội

2.3.11. Sắp xếp theo phương pháp cơ số 2.3.11. Sắp xếp theo phương pháp cơ số –

Radix sort

Ý tưởng Ý tưởng

• Mô phỏng lại qui trình trên, để sắp xếp dãy a0, a1, ...,

hư

iải th ật R di S t thự hiệ

g ự

ụ ,

ị,

g

g

,

an-1, giải thuật Radix Sort thực hiện như sau: – Trước tiên, ta có thể giả sử mỗi phần tử ai trong dãy a0, a1, ..., an-1 là một số nguyên có tối đa m chữ số. a1 a 1 là một số nguyên có tối đa m chữ số – Ta phân loại các phần tử lần lượt theo các chữ số hàng đơn vị, hàng chục, hàng trăm, … tương tự việc phân ệ p loại thư theo tỉnh thành, quận huyện, phường xã, ….

09/11/2008

Cấu trúc dữ liệu 1

175

2.3. Các giải thuật sắp xếp nội

2.3.11. Sắp xếp theo phương pháp cơ số 2.3.11. Sắp xếp theo phương pháp cơ số –

Radix sort

Thuật toán Thuật toán

• Bước 1 :// k cho biết chữ số dùng để phân loại hiện hành

; k = 0; ụ ; g

ị; // k = 0: hàng đơn vị; k = 1: hàng chục; … g • Bước 2 : //Tạo các lô chứa các loại phần tử khác nhau

Khởi tạo 10 lô B0, B1, …, B9 rỗng;

Đặt ai vào lô Bt với t: chữ số thứ k của ai;

• Bước 3 : For i = 0 .. n-1 do

B ớ 4 Nối B B t ì h t ) thà h đú

• Bước 4 : Nối B0, B1, …, B9 lại (theo đúng trình tự) thành a. B l i (th • Bước 5 :

k = k+1; Nếu k < m thì trở lại bước 2. Ngược lại: Dừng Nếu k < m thì trở lại bước 2 Ngược lại: Dừng

09/11/2008

Cấu trúc dữ liệu 1

176

2.3. Các giải thuật sắp xếp nội

2.3.11. Sắp xếp theo phương pháp cơ số 2.3.11. Sắp xếp theo phương pháp cơ số –

Radix sort

Ví dụVí dụ

09/11/2008

Cấu trúc dữ liệu 1

177

2.3. Các giải thuật sắp xếp nội

2.3.11. Sắp xếp theo phương pháp cơ số 2.3.11. Sắp xếp theo phương pháp cơ số –

Radix sort

Ví dụVí dụ

09/11/2008

Cấu trúc dữ liệu 1

178

2.3. Các giải thuật sắp xếp nội

2.3.11. Sắp xếp theo phương pháp cơ số 2.3.11. Sắp xếp theo phương pháp cơ số –

Radix sort

Ví dụVí dụ

09/11/2008

Cấu trúc dữ liệu 1

179

2.3. Các giải thuật sắp xếp nội

2.3.11. Sắp xếp theo phương pháp cơ số 2.3.11. Sắp xếp theo phương pháp cơ số –

Radix sort

Ví dụVí dụ

09/11/2008

Cấu trúc dữ liệu 1

180

2.3. Các giải thuật sắp xếp nội

2.3.11. Sắp xếp theo phương pháp cơ số 2.3.11. Sắp xếp theo phương pháp cơ số –

Radix sort

Ví dụVí dụ

09/11/2008

Cấu trúc dữ liệu 1

181

2.3. Các giải thuật sắp xếp nội

2.3.11. Sắp xếp theo phương pháp cơ số 2.3.11. Sắp xếp theo phương pháp cơ số –

Radix sort

Đánh giá Đánh giá

• Trong thao tác phân lô, mỗi phần tử chỉ được

ỗi hầ tử hỉ đ

hâ lô

th

tá

• Với một dãy n số, mỗi số có tối đa m chữ số, thuật toán thực hiện m lần các thao tác phân lô thuật toán thực hiện m lần các thao tác phân lô và ghép lô. T xét đúng một lần, khi ghép cũng vậy.

• Như vậy, chi phí cho việc thực hiện thuật toán

hiển nhiên là O(2mn) = O(n).

09/11/2008

Cấu trúc dữ liệu 1

182

2.3. Các giải thuật sắp xếp nội

2.3.11. Sắp xếp theo phương pháp cơ số 2.3.11. Sắp xếp theo phương pháp cơ số –

Radix sort

Nhận xét Nhận xét

y g

9

0

1

• Sau lần phân phối thứ k các phần tử của A vào các lô B0, B1, …, B9, và lấy ngược trở ra, nếu chỉ xét đến k+1 chữ số của các phần tử trong A, ta sẽ có một mảng tăng dần nhờ trình tự lấy ra từ 0 → 9. Nhận xét này bảo đảm tính đúng đắn của thuật toán. à bả đả

ủ h ậ

í h đú

á

hầ tử hất là khi khó

ố ất hiề

ắ

đắ • Thuật toán có độ phức tạp tuyến tính nên hiệu quả khi sắp dãy cố rất nhiều phần tử, nhất là khi khóa sắp xếp ắ dã ế không quá dài so với số lượng phần tử (điều này thường gặp trong thực tế). thường gặp trong thực tế)

09/11/2008

Cấu trúc dữ liệu 1

183

2.3. Các giải thuật sắp xếp nội

2.3.11. Sắp xếp theo phương pháp cơ số 2.3.11. Sắp xếp theo phương pháp cơ số –

Radix sort

Nhận xét Nhận xét

• Thuật toán không có trường hợp xấu nhất và tốt nhất. Mọi dãy số đều được sắp với chi phí tốt nhất Mọi dãy số đều được sắp với chi phí như nhau nếu chúng có cùng số phần tử và các khóa có cùng chiều dài. khóa có cùng chiều dài

• Thuật toán cài đặt thuận tiện với các mảng với khóa sắp xếp là chuỗi (ký tự hay số) hơn là khóa sắp xếp là chuỗi (ký tự hay số) hơn là khóa số như trong ví dụ do tránh được chi phí lấy các chữ số của từng số. lấy các chữ số của từng số

09/11/2008

Cấu trúc dữ liệu 1

184

2.3. Các giải thuật sắp xếp nội

2.3.11. Sắp xếp theo phương pháp cơ số 2.3.11. Sắp xếp theo phương pháp cơ số –

Radix sort

Nhận xét Nhận xét

tiế

A h

h ỗi ký t

) h

ê t khô

thể dù

để biể

đầ

ả

• Số lượng lô lớn (10 khi dùng số thập phân, 26 khi dùng chuỗi ký tự tiếng Anh, …) nhưng khi dù tổng kích thước của tất cả các lô chỉ bằng dãy b ban đầu nên ta không thể dùng mảng để biểu diễn B. Như vậy, phải dùng cấu trúc dữ liệu động để biểu diễn B ⇒ Radix Sort rất thích độ để biể diễ B ⇒ R di S t ất thí h hợp cho sắp xếp trên danh sách liên kết.

09/11/2008

Cấu trúc dữ liệu 1

185

2.3. Các giải thuật sắp xếp nội

2.3.11. Sắp xếp theo phương pháp cơ số 2.3.11. Sắp xếp theo phương pháp cơ số –

Radix sort

Nhận xét Nhận xét

ắ

ế

ễ

ể

ể

ễ

ầ

• Người ta cũng dùng phương pháp phân lô theo biểu diễn nhị phân của khóa sắp xếp. Khi đó ta có thể dùng hoàn toàn cấu trúc dữ liệu mảng để biểu diễn B vì chỉ cần dùng hai lô B0 và B1. ể ầ Tuy nhiên, khi đó chiều dài khóa sẽ lớn. Khi sắp các dãy không nhiều phần tử, thuật toán ề ắ Radix sort sẽ mất ưu thế so với các thuật toán khác.

09/11/2008

Cấu trúc dữ liệu 1

186