CHƯƠNG 3 CÁC THUẬT TOÁN SẮP XẾP

GV Th.S. Thiều Quang Trung Bộ môn Khoa học cơ bản Trường Cao đẳng Kinh tế Đối ngoại

Nội dung

• Chọn trực tiếp - Selection Sort

• Chèn trực tiếp - Insertion Sort

• Đổi chỗ trực tiếp - Interchange Sort

• Nổi bọt - Bubble Sort

• Sắp xếp dựa trên phân hoạch - Quick Sort

• Trộn trực tiếp - Merge Sort

1 2 3 4 5 6

GV. Thiều Quang Trung

2

Các khái niệm

• Sắp xếp là gì ?

– 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 đó.

• Khái niệm nghịch thế:

– Xét một mảng các số a0, a1, … ,aN – Giả sử xét mảng có thứ tự tăng dần, nếu có i < j và

ai > aj, thì ta gọi đó là nghịch thế.

GV. Thiều Quang Trung

3

Các khái niệm

• Để sắp xếp một mảng => tìm cách giảm số các nghịch thế trong mảng này bằng cách hoán vị các cặp phần tử.

• Cho trước một dãy số a1, a2, … aN được lưu trữ

trong cấu trúc dữ liệu mảng.

Ví dụ: int a[N]; => Chọn lựa một số phương pháp để sắp xếp.

GV. Thiều Quang Trung

4

Chọn trực tiếp - Selection Sort

• Ý tưởng: thực hiện N-1 lần việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đứng ở đầu dãy • Nhận xét: nếu mảng có thứ tự thì phần tử ai luôn là min (ai,ai+1,..,an-1) => Ý tưởng của thuật toán chọn trực tiếp: – Chọn phần tử nhỏ nhất trong N phần tử ban đầu, đưa

phần tử này về vị trí đứng đầu dãy hiện hành;

– Sau đó không quan tâm phần tử này nữa, xem dãy hiện hành chỉ còn N-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2;

– Lặp lại quá trình trên cho dãy hiện hành … cho đến khi

GV. Thiều Quang Trung

5

dãy hiện hành chỉ còn một phần tử.

Chọn trực tiếp (tt)

• Giải thuật : B1: i = 0; B2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n] B3: if (min ≠ i) : hoán vị a[min] và a[i] B4: if (i≤ (n-1): B4.1: i++ B4.2: Lặp lại B2 Ngược lại : dừng // vì n-1 phần tử đã nằm đúng vị trí

GV. Thiều Quang Trung

6

1. Chọn trực tiếp (tt)

GV. Thiều Quang Trung

7 7

1. Chọn trực tiếp (tt)

GV. Thiều Quang Trung

8 8

Cài đặt giải thuật Chọn trực tiếp

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

min = j; // ghi nhận vị trí phần tử nhỏ nhất if (min != i)

void SelectionSort(int a[],int n ) { int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành for (int i=0; i

GV. Thiều Quang Trung

9

Đánh giá giải thuật Chọn trực tiếp

• Ở lượt thứ I, cần (n-i) lần so sánh để tìm phần tử nhỏ nhất

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

• Trong mọi trường hợp số lần so sánh là • 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ố.

Trường hợp Số lần so sánh Số phép gán

Tốt nhất 0

GV. Thiều Quang Trung

10

Xấu nhất

Chèn trực tiếp - Insertion Sort

Ý tưởng: • Giả sử dãy {a0,a1,…an-1} có k phần tử đầu tiên

{a0,a1,…ak-1} đã có thứ tự.

• Chèn phần tử ak vào k phần tử đầu tiên đã có thứ tự bằng cách tìm vị trí đúng của phần tử k theo giải thuật tìm tuần tự (Sequential Search)  có dãy mới {a0,a1,…,ak-1,ak} có thứ tự.

• Vị trí cần chèn ak chính là giữa 2 phần tử ai-1 và ai

sao cho ai-1 ≤ ak+1 ≤ ai

GV. Thiều Quang Trung

11

Chèn trực tiếp - Insertion Sort (tt)

Thuật toán:

B1: k = 1 //Giả sử đoạn a[0] đã sắp xếp B2: x = ak Tìm vị trí pos thích hợp trong đoạn a0 đến ak-1 để

chèn ak vào

B3: Dời chỗ các phần tử từ apos đến ak-1 sang phải 1 vị trí để

dành chỗ cho ak

GV. Thiều Quang Trung

12

B4: apos = x; // đoạn a0 … ak đã được sắp B5: k = k+1 Nếu i<= n: lặp lại B2 Ngược lại : dừng

Ví dụ mô phỏng chèn trực tiếp

•

Cho dãy số a : N = 8 ; 12

2

8

5

1

6

4

15

GV. Thiều Quang Trung

13 13

Ví dụ mô phỏng chèn trực tiếp (tt)

GV. Thiều Quang Trung

14 14

Cài đặt giải thuật Chèn trực tiếp

int x=a[k+1]; i=k; while (x0) a[i+1] = a[i]; { i--; } a[i+1]=x; k++;

GV. Thiều Quang Trung

while (a[k]≤a[k+1] && k

void InsertionSort (int a [ ], int n)

15

{ int k=0, i; }

Đánh giá giải thuật Chèn trực tiếp

• Trường hợp tốt nhất: khi mảng a ban đầu đã

có thứ tự tăng – Số phép gán: Gmin = 2*(n-1) – Số phép so sánh: Smin = 1+2+…+ (n-1) = n*(n-1)/2

• Trường hợp xấu nhất: khi mảng a ban đầu

luôn có phần tử nhỏ nhất trong n-k phần tử còn lại – Số phép gán: Gmax = 2*(n-1) + n*(n-1)/2 – Số phép so sánh: Smax = n-1

• Độ phức tạp của thuật toán: O(n2)

GV. Thiều Quang Trung

16

Chèn nhị phân – Binary Insertion Sort

Ý tưởng: • Phương pháp chèn nhị phân tương tự

phương pháp chèn trực tiếp.

• Tuy nhiên, khi thực hiện tìm kiếm vị trí i cho phần tử ai để chèn vào đoạn {a0,a1,…,ai-1} có thể dùng phương pháp tìm kiếm nhị phân (Binary Search) thay cho tìm kiếm tuần tự (Sequential Search)

GV. Thiều Quang Trung

17

Cài đặt Binary Insertion Sort

// tìm vị trí chèn x

while(l<=r) { m = (l+r)/2; // tìm vị trí thích hợp m 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 a[l] = x;

// chèn x vào dãy

GV. Thiều Quang Trung

18

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

Đánh giá Binary Insertion Sort

• Phương pháp chèn nhị phân chỉ cải tiến cách tìm kiếm vị trí thích hợp của phần tử a[i], làm giảm số lần so sánh nhưng lại không làm thay đổi số lần di chuyển.

• Vì vậy việc cải tiến này không đáng kể lắm 

Độ phức tạp của thuật toán vẫn là O(n2)

GV. Thiều Quang Trung

19

Đổi chỗ trực tiếp - Interchange Sort

• Ý tưởng : Ý tưởng chính của giải thuật là xuất phá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 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.

GV. Thiều Quang Trung

20 20

3. Đổi chỗ trực tiếp (tt)

• Giải thuật : B1 : i = 1 ; // Bắt đầu từ đầu dãy. B2 : j = i + 1 ; // Tìm các phần tử a[j] < a[i], j > i B3 : Trong khi j  n thực hiện Nếu a[j] < a[i] : Hoán vị a[i] và a[j] ; j = j +1; B4 : i = i+1;

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

GV. Thiều Quang Trung

21 21

Ví dụ mô phỏng Đổi chỗ trực tiếp

• Cho dãy số a : N = 8 ; 12

8

5

2

1

6

4

15

GV. Thiều Quang Trung

22 22

Ví dụ mô phỏng Đổi chỗ trực tiếp (tt)

GV. Thiều Quang Trung

23 23

Ví dụ mô phỏng Đổi chỗ trực tiếp (tt)

GV. Thiều Quang Trung

24 24

Ví dụ mô phỏng Đổi chỗ trực tiếp (tt)

GV. Thiều Quang Trung

25 25

Ví dụ mô phỏng Đổi chỗ trực tiếp (tt)

GV. Thiều Quang Trung

26 26

Ví dụ mô phỏng Đổi chỗ trực tiếp (tt)

GV. Thiều Quang Trung

27 27

Cài đặt thuật toán Đổi chỗ trực tiếp

for (int i = 0 ; i < N - 1 ; i ++ )

for (int j = i +1 ; j < N ; j ++)

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

if (a[j] < a[i]) // Nếu có sự sai vị trí thì đổi chỗ

void InterchangeSort ( int a[] , int N )  

GV. Thiều Quang Trung

28 28

Đánh giá giải thuật Đổi chỗ trực tiếp

Số lượng các phép so sánh không phụ thuộc vào tình trạng của dãy số ban đầu, nhưng số lượng các phép hoán vị phụ thuộc vào kết quả so sánh

Trường hợp Số lần so sánh Số lần hoán vị

Xấu nhất

GV. Thiều Quang Trung

29 29

Tốt nhất 0

Giải thuật Nổi bọt (Bubble Sort)

Ý tưởng : • 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ử đó 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 sẽ 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ử

nào để xét.

GV. Thiều Quang Trung

30 30

Giải thuật Nổi bọt (Bubble Sort)

Giải thuật : B1: i = 0 ; // Lần xử lý đầu tiên B2: j = N-1 ; // Duyệt từ cuối dãy ngược về vị trí i

if a[j] < a[j-1] : swap (a[j], a[j-1]); j = j - 1;

Trong khi (j > i) thực hiện B3: i = i + 1;

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

GV. Thiều Quang Trung

31 31

// Lần xử lý kế tiếp

Cài đặt giải thuật Nổi bọt

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]);

}

GV. Thiều Quang Trung

32

Ví dụ mô phỏng giải thuật Nổi bọt

2

5

1

6

4

15

• Cho dãy số a : N = 8 ; 8 12

GV. Thiều Quang Trung

33 33

4. Nổi bọt (tt)

GV. Thiều Quang Trung

34 34

4. Nổi bọt (tt)

GV. Thiều Quang Trung

35 35

4. Nổi bọt (tt)

GV. Thiều Quang Trung

36 36

4. Nổi bọt (tt)

GV. Thiều Quang Trung

37 37

4. Nổi bọt (tt)

GV. Thiều Quang Trung

38 38

Đánh giá thuật toán Nổi bọt

• 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,

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

quả so sánh

Trường hợp Số lần so sánh Số lần hoán vị

Tốt nhất 0

GV. Thiều Quang Trung

39 39

Xấu nhất

Sắp xếp dựa trên phân hoạch - Quick Sort

• Ý tưởng : Để sắp xếp dãy a1, a2, … , an giải thuật QuickSort dựa trên

việc phân hoạch dãy ban đầu thành hai phần :

Dãy con 1 : gồm các phần tử a1 .. ai có giá trị nhỏ hơn x. Dãy con 2 : gồm các phần tử ai .. an có giá trị lớn hơn x. Với x là giá trị của một phần tử tùy ý trong dãy ban đầu.

GV. Thiều Quang Trung

40 40

 x  x x

Sắp xếp dựa trên phân hoạch (tt)

Giải thuật sắp xếp : Cho dãy aL, aL + 1, …, aR : B1 : Phân hoạch dãy aL … aR thành các dãy con :

B2 :

Nếu (L < j) Phân hoạch dãy aL ... aj Nếu (i < R) Phân hoạch dãy ai .. aR

GV. Thiều Quang Trung

41 41

– Dãy con 1 : aL ... aj  x – Dãy con 2 : aj + 1 ... ai -1 = x – Dãy con 3 : ai ... aR  x

Sắp xếp dựa trên phân hoạch (tt)

x = a[k]; i = L; j = R ;

Giải thuật phân hoạch: (Phân hoạch dãy aL, aL + 1, …, aR thành 2 dãy con) B1 : Chọn tùy ý một phần tử a[k] trong dãy là giá trị mốc, LkR : B2 : Phát hiện và hiệu chỉnh cặp phần tử a[i], a[j] nằm sai chỗ B2.1 : Trong khi (a[i] < x) i++; B2.2: Trong khi (a[j] > x) j--; B2.3 : Nếu (i < j) Hoán vị a[i] và a[j]; B3 : Nếu i < j : lặp lại bước 2. Ngược lại : Dừng phân hoạch.

GV. Thiều Quang Trung

42 42

Cài đặt giải thuật sắp Quicksort

{

while(a[i] < x) i++;

{ Swap(a[i], a[j]); i++ ; j--;

GV. Thiều Quang Trung

43

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

Đánh giá giải thuật Quicksort

• 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 phần tử

median làm mốc  dãy được chia thành 2 phần bằng nhau  log2(n) lần phân hoạch thì sắp xếp xong.

• 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  dãy sẽ bị phân chia thành 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ử  n lần phân hoạch mới sắp xếp xong.

Trường hợp Độ phức tạp

Tốt nhất Trung bình

GV. Thiều Quang Trung

44

Xấu nhất n*log(n) n*log(n) n2

5. Sắp xếp dựa trên phân hoạch (tt)

• Ví dụ : Cho dãy số a : N = 8 ;

12 2

5

8

1

6

4

15

GV. Thiều Quang Trung

45 45

5. Sắp xếp dựa trên phân hoạch (tt)

GV. Thiều Quang Trung

46 46

5. Sắp xếp dựa trên phân hoạch (tt)

GV. Thiều Quang Trung

47 47

Giải thuật Trộn trực tiếp - Merge Sort

• Ý tưởng : Để sắp xếp dãy a1, a2, ... , an, giải thuật trộn trực tiếp

dựa trên nhận xét sau : – Mỗi dãy a1, a2, ... , an bất kỳ đều có thể coi như là một tập hợp các dãy con liên tiếp mà mỗi dãy con đều đã có thứ tự. 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.

GV. Thiều Quang Trung

48 48

Giải thuật Trộn trực tiếp - Merge Sort (tt)

 Cách tiếp cận để sắp xếp dãy là tìm cách làm giảm số dãy con không giảm của nó => Phân hoạch dãy ban đầu thành các dãy con.

 Sau khi phân hoạch xong, dãy ban đầu sẽ được tách ra thành 2 dãy phụ theo nguyên tắc phân phối đều luân phiên.

 Trộn từng cặp dãy con của 2 dãy phụ thành một dãy con của dãy ban đầu, ta sẽ nhận lại dãy ban đầu nhưng với số lượng dãy con ít nhất giảm đi một nửa.

 Lặp lại quá trình trên sau một số bước, ta sẽ nhận được

một dãy gồm 1 dãy con không giảm. Nghĩa là dãy ban đầu đã được sắp xếp.

GV. Thiều Quang Trung

49 49

Giải thuật Trộn trực tiếp - Merge Sort (tt)

 Giải thuật trộn là phương pháp đơn giản nhất. Việc phân hoạch thành các dãy con đơn giản là tách dãy gồm n phần tử thành n dãy con. Cứ mỗi lần tách rồi trộn, chiều dài của các dãy con sẽ được nhân đôi.

GV. Thiều Quang Trung

50 50

Giải thuật Trộn trực tiếp - Merge Sort (tt)

Giải thuật : B1 : k = 1; // k là chiều dài của dãy con trong bước hiện hành B2 : Tách dãy a1, a2, … , an thành 2 dãy b, c theo nguyên tắc luân

phiên từng nhóm k phần tử :

c = ak + 1, … , a2k, a3k +1, … a4k, …

GV. Thiều Quang Trung

51 51

b = a1, … , ak, a2k +1, … a3k, … B3 : 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. B4 : k = k * 2; Nếu k < n thì trở lại bước 2. Ngược lại : Dừng.

Ví dụ mô phỏng giải thuật Merge Sort

• Cho dãy số a : N = 8 ;

12

8

2

5

1

6

4

15

GV. Thiều Quang Trung

52 52

Ví dụ mô phỏng giải thuật Merge Sort (tt)

GV. Thiều Quang Trung

53 53

Cài đặt giải thuật Merge Sort

// độ dài của dãy con khi phân hoạch

// hai mảng phụ

for (i = 0 ; (pa < N) && (i < k) ; i++) b [pb++] = a [pa++]; for (i = 0 ; (pa < N) && (i < k) ; i ++) c [pc++] = a [pa++]

 while (k < N);

int pa, pb, pc; // các chỉ số trên các mảng a,b,c int i, k = 1; int b [N], c[N]; do  // tách a thành b và c pa = pb = pc = 0; while (pa < N)   Merge (a, b, c, pb, pc, k); // trộn b, c lại thành a k * = 2; 

GV. Thiều Quang Trung

54 54

void MergeSort (int a[], int N) 

Cài đặt giải thuật Merge Sort (tt)

a [pa ++] = c [pc + ic] ; pb += kb ; pc += kc ; ib = ic = 0 ; nb = kb ; nc = kc;

for (; ic < kc ; ic ++ )

a [pa++] = b [pb + ib]; ib ++; if (ib = = kb)  

kb = min (k, nb) ; kc = min (k, nc) ; if (b [pb + ib] <= c [pc + ic]) 

GV. Thiều Quang Trung

55 55

void Merge ( int a [], int b [], int c [], int nb, int nc, int k)  int pa, pb, pc, ib, ic, kb, kc; pa = pb = pc = 0 ; ib = ic = 0 ; while ((nb > 0) && (nc > 0))

Cài đặt giải thuật Merge Sort (tt)

a [pa ++] = b [pb + ib] ; pb += kb ; pc += kc ; ib = ic = 0; nb = kb ; nc = kc ;

a [pa ++] = c [pc + ic] ; ic ++; if (ic = = kc)  

for (; ib < kb ; ib ++)

 else  

GV. Thiều Quang Trung

56 56

Đánh giá giải thuật Merge Sort

• Số lần lặp của bước 2 và bước 3 là log2n do sau mỗi

lần lặp giá trị của k tăng lên gấp đôi.

• Chi phí thực hiện của giải thuật trộn là nlog2n. • Do không sử dụng thông tin nào về đặc tính của dãy cần sắp xếp, nên trong mọi trường hợp của thuật toán chi phí là không đổi. Đây chính là một trong những nhược điểm lớn của thuật toán.

GV. Thiều Quang Trung

57 57

So sánh các phương pháp sắp xếp

STT Phương pháp Độ phức tạp

1 Chèn trực tiếp – InsertionSort O(n2)

2 Chèn nhị phân – Binary InsertionSort O(n2)

3 Chọn trực tiếp - SelectionSort O(n2)

5 QuickSort

O(nlogn)

4 Nổi bọt – BubbleSort O(n2)

GV. Thiều Quang Trung

58

6 MergeSort O(nlogn)

Bài tập thực hành

• Bài 1: Cho dãy số dùng mảng lưu trữ. Viết chương trình sắp xếp bằng phương pháp chọn trực tiếp (Selection Sort). In ra dãy số trước khi sắp và sau khi sắp.

• Bài 2: Cho dãy số dùng mảng lưu trữ. Viết chương trình sắp xếp bằng phương pháp chèn trực tiếp (Insertion Sort). In ra dãy số trước khi sắp và sau khi sắp.

• Bài 3: Cho dãy số dùng mảng lưu trữ. Viết chương trình

sắp xếp bằng phương pháp đổi chổ trực tiếp (Interchange Sort). In ra dãy số trước khi sắp và sau khi sắp.

GV. Thiều Quang Trung

59 59

Bài tập thực hành (tt)

• Bài 4: Cho dãy số dùng mảng lưu trữ. Viết chương trình sắp xếp bằng phương pháp nổi bọt (Bubble Sort). In ra dãy số trước khi sắp và sau khi sắp. • Bài 5: Cho dãy số dùng mảng lưu trữ. Viết chương

trình sắp xếp bằng phương pháp theo nguyên tắc trộn (Merge Sort). In ra dãy số trước khi sắp và sau khi sắp.

• Bài 6: Cho dãy số dùng mảng lưu trữ. Viết chương

trình sắp xếp bằng phương pháp hiệu quả cao (Quick Sort). In ra dãy số trước khi sắp và sau khi sắp.

GV. Thiều Quang Trung

60 60

GV. Thiều Quang Trung