04/2010

Bài toán sắp xếp
• Cho tập N phần tử, mỗi phần
tử có một số thuộc tính
• Dựa vào 1 (hoặc vài) thuộc tính
của các phần tử ñể sắp xếp lại
chúng theo trật tự mới.

KỸ THUẬT LẬP TRÌNH C
Chương 7: Các thuật toán sắp xếp





Kỹ thuật lập trình C - Thuật toán sắp xếp

04/2010

04/2010

Bài toán sắp xếp

Các giải thuật sắp xếp

• Gồm 2 bài toán con:

•
•
•

Quick sort
Merge sort



Kỹ thuật lập trình C - Thuật toán sắp xếp

4


04/2010

04/2010

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

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

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

• Tìm tất cả nghịch thế, triệt tiêu chúng bằng
cách hoán vị 2 phần tử tương ứng trong
nghịch thế

– Xét một mảng các số a0, a1, . an.
– Nếu có i<j và ai > 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ảng đã có thứ tự sẽ không chứa nghịch thế

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



Kỹ thuật lập trình C - Thuật toán sắp xếp

04/2010

7



5

1

6

Kỹ thuật lập trình C - Thuật toán sắp xếp

4

15

8


04/2010


11



Kỹ thuật lập trình C - Thuật toán sắp xếp

12


04/2010

Interchange Sort - Kết quả

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



Kỹ thuật lập trình C - Thuật toán sắp xếp

04/2010

13

12

2

8

5


5

2

6

4

15

1

8

12

5

2

6

4

15

1

5


2

8

12

5

6

4

15

1

2

5

12

8

6

4

15


15

1

2

4

6

12

8

5

15

1

2

4

5

12

8


12

8

15

4 Kỹ thuật lập 5trình C - Thuật6 toán sắp xếp8

12

15
14


1
2

04/2010

04/2010

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

Các giải thuật sắp xếp

void InterchangeSort(int a[], int N )
{
int i, j;
for (i = 0 ; i



Kỹ thuật lập trình C - Thuật toán sắp xếp

16


04/2010

04/2010

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

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

• 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 là ñầu dãy hiện hành
• Xem dãy hiện hành chỉ còn N-1 phần tử của dãy
ban đầu

• Bước 1: i = 1;
• Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện
hành từ a[i] ñến a[N]
• Bước 3 : Nếu min ≠ i thì ðổi chỗ a[min] và a[i]

– Bắt đầu từ vị trí thứ 2;
– Lặp lại quá trình trên cho dãy hiện hành... ñến khi dãy
hiện hành chỉ còn 1 phần tử


Kỹ thuật lập trình C - Thuật toán sắp xếp

18

04/2010

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

15

19



Kỹ thuật lập trình C - Thuật toán sắp xếp

20


04/2010

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



Kỹ thuật lập trình C - Thuật tốn sắp xếp

04/2010

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

{
min = i;
for(int j = i+1; j < N ; j++)
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]);
}
}



22

23

Sắp xếp đổi chỗ trực tiếp - Interchange Sort
Sắp xếp chọn trực tiếp – Selection Sort
Sắp xếp chèn trực tiếp – Insertion Sort
Sắp xếp nổi bọt – Buble Sort
Sắp xếp nổi bọt cải tiến - Shaker Sort
Shell sort
Heap sort
Quick sort
Merge sort



Kỹ thuật lập trình C - Thuật tốn sắp xếp



// có ño n a[1]..a[i] ñã ñ
c s p

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



Kỹ thuật lập trình C - Thuật toán sắp xếp

25



Kỹ thuật lập trình C - Thuật toán sắp xếp

04/2010

Chèn trực tiếp – Insertion Sort
• Cho dãy số :
12 2
8
5



1

6

void InsertionSort(int a[], int N )
{
int pos, i;
int x;//lưu trữ a[i] tránh bò ghi đè khi dời chỗ các phần tử.
for(i=1 ; i0)&&(a[pos-1]>x);pos--)
a[pos] = a[pos-1];
a[pos] = x;// chèn x vào dãy
}
}

Kỹ thuật lập trình C - Thuật tốn sắp xếp



29



Kỹ thuật lập trình C - Thuật tốn sắp xếp

04/2010

Insertion Sort - Kết quả
12

04/2010


15

2

12

8

5

1

6

4

15

2

8

12

5

1

6


6

4

15

1

2

5

6

8

12

4

15

1

2

4

5


Sắp xếp nổi bọt cải tiến - Shaker Sort
Shell sort
Heap sort
Quick sort
Merge sort



Kỹ thuật lập trình C - Thuật tốn sắp xếp

32


04/2010

04/2010

Nổi bọt – Bubble Sort

Nổi bọt – Bubble Sort

• Ý tưởng chính của giải thuật là xuất phát từ cuối

• Bước 1 : i = 1;
// l n x lý ñ u tiên
• Bước 2 : j = N;
//Duy t t cu i dãy ng
c v v trí i
Trong khi (j > i) thực hiện:
Nếu a[j]
5

1

34

04/2010

Nổi bọt – Bubble Sort
6

Kỹ thuật lập trình C - Thuật toán sắp xếp

4

15

35



Kỹ thuật lập trình C - Thuật toán sắp xếp

36


04/2010

Nổi bọt – Bubble Sort


Swap(a[j], a[j-1]);
}



Kỹ thuật lập trình C - Thuật toán sắp xếp

39



Kỹ thuật lập trình C - Thuật toán sắp xếp

40


04/2010

Bubble Sort - Kết quả

Các giải thuật sắp xếp

12

2

8

5


1

5

4

6

15

12

2

1

8

5

4

6

15

12

1


12

2

8

4

5

6

15

1

12

2

4

8

5

6

15


15

1

2

4

12

5

8

6

15

1

2

4

12

5

6


6 toán sắp xếp
8

8

15

12

15
41


1
2

04/2010

•
•
•
•
•
•
•
•
•

Sắp xếp đổi chỗ trực tiếp - Interchange Sort
Sắp xếp chọn trực tiếp – Selection Sort

while (left < right) {
for (j = right; j > left; j--)
if (data[j]< data[j-1]){
Doicho(data[j], data[j-1]);
k =j;
}
left = k;
for (j = left; j < right; j++)
if (data[j]> data[j+1]) {
Doicho(data[j],data[j-1]);
k = j;
}
right = k;
}

• Trong mỗi lần sắp xếp, duyệt mảng theo 2 lượt
từ 2 phiá khác nhau :
– Lượt đi: đẩy phần tử nhỏ về ñầu mảng
– Lượt về: đẩy phần tử lớn về cuối mảng

• 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.
}


Kỹ thuật lập trình C - Thuật toán sắp xếp

43




– 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.
– 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 phải đổi chiều các quan hệ.

Kỹ thuật lập trình C - Thuật tốn sắp xếp



Sắp xếp vun đống - Heap sort

04/2010

45

04/2010

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

2




46

Sắp xếp vun đống – Heap sort
a1

a2

a4

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

a3

a5

a6

04/2010

a7

a8






Kỹ thuật lập trình C - Thuật tốn sắp xếp

Heap sort – Giai đoạn 1

– Giai đoạn 1: hiệu chỉnh dãy ban đầu thành heap
– Giai đoạn 2: sắp xếp heap có được sau giai đoạn
1 thành dãy tăng dần

49

04/2010

Tạo heap
1

2

3

4

5

6

7


4

5

12
12

15

8

2

1

6

4

5

15

8

5

1

6

•
•
•
•

//Lưu ý: đoạn aleft+1, …, aN đã là heap
• Bước 21: Hiệu chỉnh đoạn aleft, …, aN thành heap
• Bước 22: left = left - 1;

//Hết lặp
Kỹ thuật lập trình C - Thuật tốn sắp xếp

50

04/2010

//input: dãy (a, N)
//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 heap
• Bước 2: Trong khi left > 0



Kỹ thuật lập trình C - Thuật tốn sắp xếp



51


• Bước 2.2: right := right -1;
• Bước 2.3: Hiệu chỉnh đoạn a1, a2, …, aright thành heap

Ł Đổi chổ (a1, aright) Ł được thêm một phần tử ở đúng vò trí

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

//Hết lặp

Kỹ thuật lập trình C - Thuật tốn sắp xếp



53



Kỹ thuật lập trình C - Thuật tốn sắp xếp

04/2010

Hiệu chỉnh heap

04/2010

Các giải thuật sắp xếp

1


2

12

8

5

1

6

4

15

12

2

8

5

1

6

4


12

15

• Đỗi chổ a[1] ↔ a[8]
có 1 phần tử đã đúng vị trí
• Tiến hành tương tự cho dãy n-1 phần tử
Lưu ý: Chỉ cần xét phần tử a[1]



54

Kỹ thuật lập trình C - Thuật tốn sắp xếp

55

•
•
•
•
•
•
•
•
•

Sắp xếp đổi chỗ trực tiếp - Interchange Sort
Sắp xếp chọn trực tiếp – Selection Sort



Kỹ thuật lập trình C - Thuật tốn sắp xếp

04/2010

57

• 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 = 1 .. j
– 2. ak = x , với k = j+1 .. i-1
– 3. ak > x , với k = i..N



Kỹ thuật lập trình C - Thuật tốn sắp xếp

04/2010

Quick sort – Ý tưởng

Kỹ thuật lập trình C - Thuật tốn sắp xếp

04/2010

Quick sort – Ý tưởng

• Đoạn thứ 2 đã có thứ tự.
• Nếu các đoạn 1 và 3 có nhiều hơn 1 phần tử


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

• Bước 1: Nếu left ≥ right //dãy có ít hơn 2 phần tử

//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:

Kết thúc;

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

x = a[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

• 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] vi phạm điều kiện
–
–
–
–

Đoạn 1 ≤ x
Đoạn 2: aj+1.. ai-1 = x
Đoạn 3: ai.. aright ≥ x

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

2 8

5

62

04/2010

Quick sort – Ví dụ
1

6

4

15

Phân hoạch đoạn l =1, r = 8: x = A[4] = 5



Kỹ thuật lập trình C - Thuật tốn sắp xếp

63



Kỹ thuật lập trình C - Thuật tốn sắp xếp

64

66

04/2010

Quick sort – Cài đặt
• Phân hoạch đoạn l = 7, r = 8:



Kỹ thuật lập trình C - Thuật tốn sắp xếp

x = A[7] = 6

67

void QuickSort(int a[], int left, int right)
{
int i, j, x;
if (left ≥ right)
return;
x = a[(left+right)/2]; // chọn phần tử giữa làm giá trò mốc
i = left; j = right;
while(i < j) {
while(a[i] < x) i++;
while(a[j] > x) j--;
if(i
Sắp xếp đổi chỗ trực tiếp - Interchange Sort
Sắp xếp chọn trực tiếp – Selection Sort
Sắp xếp chèn trực tiếp – Insertion Sort
Sắp xếp nổi bọt – Buble Sort
Sắp xếp nổi bọt cải tiến - Shaker Sort
Shell sort
Heap sort
Quick sort
Merge sort



Kỹ thuật lập trình C - Thuật tốn sắp xếp

04/2010

– Mỗi dãy a1, a2, ..., an bất kỳ 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.

Ł 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.
69

4

5

6

7

8

12

2

8

5

1

6

4

15

//b = a1, …, ak, a2k+1, …, a3k, …
//c = ak+1, …, a2k, a3k+1, …, a4k, …

Phân phối đều luân phiên

4

5

6

7

8

12

2

8

5

1

6

4

15

Kỹ thuật lập trình C - Thuật tốn sắp xếp




5

6

15

5

6

7

Kỹ thuật lập trình C - Thuật tốn sắp xếp



74

04/2010

Merge sort – Ví dụ

1

2

3

4


Kỹ thuật lập trình C - Thuật tốn sắp xếp

6

7

8

75

k = 2;

Phân phối đều luân phiên

1

2

3

4

5

6

7

8



k = 2;
1

2

3

4

2

12

1

5

8

4

5

6

7

8



Kỹ thuật lập trình C - Thuật tốn sắp xếp



04/2010

77

5

6

7

Kỹ thuật lập trình C - Thuật tốn sắp xếp



78

04/2010

Merge sort – Ví dụ
k = 4;

04/2010

Merge sort – Ví dụ


6

15



8

Kỹ thuật lập trình C - Thuật tốn sắp xếp

79

Trộn từng cặp đường chạy

k = 4;
1

2

3

4

2

5

8

12


k = 4;
1

Merge sort – Ví dụ

2

3

4

5

6

7

k = 8;

8

1

2

3

4


12

STOP

1

4

6

15

Only one
subarray

Kỹ thuật lập trình C - Thuật tốn sắp xếp





81

Kỹ thuật lập trình C - Thuật tốn sắp xếp

04/2010

04/2010

Merge Sort – Cài đặt

12

8
15

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

– Merge: Trộn mảng b và mảng c vào mảng a
void Merge(int a[], int nb, int nc, int k);

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



Kỹ thuật lập trình C - Thuật tốn sắp xếp

83




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



Kỹ thuật lập trình C - Thuật tốn sắp xếp

04/2010

85



Kỹ thuật lập trình C - Thuật tốn sắp xếp

04/2010

Merge sort – Cài đặt

Kỹ thuật lập trình C - Thuật tốn sắp xếp




86

87



Kỹ thuật lập trình C - Thuật tốn sắp xếp

88


04/2010



Kỹ thuật lập trình C - Thuật toán sắp xếp

89