Cấu trúc dữ liệu và giải thuật-Đinh Mạnh Tường(chuong 17)

Chia sẻ: vuthithuy11a

Cấu trúc dữ liệu và giải thuật-Cách tiếp cận phương pháp lập trình hướng đối tượng bằng ngôn ngữ lập trình C++.Dùng cho sinh viên năm 2 các trường ĐH,CĐ chuyên ngành công nghệ thông tin

Bạn đang xem 10 trang mẫu tài liệu này, vui lòng download file gốc để xem toàn bộ.

Nội dung Text: Cấu trúc dữ liệu và giải thuật-Đinh Mạnh Tường(chuong 17)

CHƯƠNG 17

SẮP XẾP

Sắp xếp là một quá trình biến đổi một danh sách các đối tượng
thành một danh sách thoả mãn một thứ tự xác định nào đó. Sắp xếp đóng
vai trò quan trọng trong tìm kiếm dữ liệu. Chẳng hạn, nếu danh sách đã
được sắp xếp theo thứ tự tăng dần (hoặc giảm dần), ta có thể sử dụng kỹ
thuật tìm kiếm nhị phân hiệu quả hơn nhiều tìm kiếm tuần tự… Trong
thiết kế thuật toán, ta cũng thường xuyên cần đến sắp xếp, nhiều thuật
toán được thiết kế dựa trên ý tưởng xử lý các đối tượng theo một th ứ tự
xác định.
Các thuật toán sắp xếp được chia làm 2 loại: sắp xếp trong và sắp
xếp ngoài. Sắp xếp trong được thực hiện khi mà các đối tượng cần sắp
xếp được lưu ở bộ nhớ trong của máy tính dưới dạng mảng. Do đó sắp
xếp trong còn được gọi là sắp xếp mảng. Khi các đối tượng c ần s ắp x ếp
quá lớn cần lưu ở bộ nhớ ngoài dưới dạng file, ta cần sử dụng các
phương pháp sắp xếp ngoài, hay còn gọi là sắp xếp file. Trong ch ương
này, chúng ta trình bày các thuật toán sắp xếp đơn giản, các thuật toán này
dòi hỏi thời gian O(n2) để sắp xếp mảng n đối tượng. Sau đó chúng ta đưa
ra các thuật toán phức tạp và tinh vi hơn, nh ưng hiệu quả h ơn, ch ỉ c ần
thời gian O(nlogn).
Mảng cần được sắp xếp có thể là mảng số nguyên, mảng các số
thực, hoặc mảng các xâu ký tự. Trong trường hợp tổng quát, các đối
tượng cần được sắp xếp chứa một số thành phần dữ liệu, và ta cần sắp
xếp mảng các đối tượng đó theo một thành phần dữ liệu nào đó. Thành
phần dữ liệu đó được gọi là khoá sắp xếp. Chẳng hạn, ta có một mảng
các đối tượng sinh viên, mỗi sinh viên gồm các thành phần dữ liệu: tên,
tuổi, chiều cao,…, và ta muốn sắp xếp các sinh viên theo th ứ t ự chi ều cao
tăng, khi đó chiều cao là khoá sắp xếp.


187
Từ đây về sau, ta giả thiết rằng, mảng cần được sắp xếp là mảng
các đối tượng có kiểu Item, trong đó Item là cấu trúc sau:
struct Item
{
key; // Khoá sắp xếp
keyType
// Các trường dữ liệu khác
};
Vấn đề sắp xếp bây giờ được phát biểu chính xác như sau. Cho
mảng A[0..n-1] chứa n Item, chúng ta cần sắp xếp lại các thành ph ần c ủa
mảng A sao cho:
A[0].key A[10] nên A[10] = 3 đ ược chép vào m ảng
B và j = 11. Ta lại có A[5] > A[11], nên A[11] = 5 được chép vào m ảng B
và j = 12. Đến dây A[5] < A[12], ta chép A[5] = 10 vào mảng B và i = 6.
Tiếp tục như thế ta nhận được mảng B như sau:




3 5 10 12 15 20 21 26
B

5 6 7 8 9
0 1 2 3 4

Đến đây j = 15 > b = 14, còn i = 8 < c = 9, do đó ta chép n ốt A[8] = 31 và
A[9] = 35 sang B để nhận được mảng B được sắp. Bây giờ chỉ cần chép
lại mảng B sang mảng A. Hàm Merge được viết như sau:
void Merge( Item A[] , int a , int c , int b)
// a, c, b là các số nguyên không âm, a ≤ c ≤ b.
// Các mảng con A[a…c] và A[c+1…b] đã được sắp.
{
int i = a;
int j = c + 1;


194
int k = 0;
int n = b – a + 1;
Item * B = new Item[n];
(1) while (( i < c +1 ) && ( j < b +1 ))
if ( A [i].key < A[j].key)
B[k ++] = A[i ++];
else B[k ++] = A[j ++];
(2) while ( i < c + 1)
B[k ++] = A[i++];
(3) while ( j < b +1)
B[k ++] = A[ j ++];
i = a;
(4) for ( k = 0 ; k < n ; k ++)
A[i ++] = B [k];
delete [ ] B;
}

Phân tích sắp xếp hoà nhập.
Giả sử mảng cần sắp xếp A[a…b] có độ dài n, n = b – a +1, và T(n)
là thời gian chạy của hàm MergeSort (A, a, b). Khi đó th ời gian th ực hi ện
mỗi lời gọi đệ quy MergeSort (A, a, c) và MergeSort (A, c + 1, b) là T(n/2).
Chúng ta cần đánh gía thời gian chạy của hàm Merge(A, a, c, b). Xem xét
hàm Merge ta thấy rằng, các lệnh lặp (1), (2), (3) cần thực hiện tất cả là n
lần lặp, mỗi lần lặp chỉ cần thực hiện một số cố định các phép toán. Do
đó tổng thời gian của ba lệnh lặp (1), (2), (3) là O(n). Lệnh l ặp (4) c ần
thời gian O(n). Khi thực hiện hàm MergeSort(A, a, b) với a = b, ch ỉ m ột
phép so sánh phải thực hiện, do đó T(1) = O(1). Từ hàm đ ệ quy
MergeSort và các đánh giá trên, ta có quan hệ đệ quy sau
T(1) = O(1)
T(n) = 2T(n/2) + O(n) với n>1
Giả sử thời gian thực hiện các phép toán trong mỗi lần lặp ở hàm Merge
là hằng số d nào đó, ta có :

T(1) ≤ d


195
T(n) ≤ 2T(n/2) + nd
Áp dụng phương pháp thế lặp vào bất đẳng thức trên ta nhận được

T(n) ≤ 2T(n/2) + n d

≤ 22 T(n/22) + 2 (n/2)d + n d
……

≤ (k lần nd)
2k T(n/2k) + n d + …+ n d

Giả sử k là số nguyên dương lớn nhất sao cho 1 ≤ n / 2k. Khi đó, ta có

T(n) ≤ 2k T(1) + n d + … + n d ( k lần n d)

T(n) ≤ (k + 1) n d

T(n) ≤ (1 + log n) n d
Vậy T(n) = O (n log n).

SẮP XẾP NHANH
17.3

Trong mục này chúng ta trình bày thuật toán sắp xếp được đưa ra
bởi Hoare, nổi tiếng với tên gọi là sắp xếp nhanh (QuickSort). Thời gian
chạy của thuật toán này trong trường hợp xấu nhất là O(n 2). Tuy nhiên
thời gian chạy trung bình là O(n logn).
Thuật toán sắp xếp nhanh được thiết kế bởi kỹ thuật chia-để-trị
như thuật toán sắp xếp hòa nhập. Nhưng trong thuật toán s ắp x ếp hòa
nhập, mảng A[a…b] cần sắp được chia đơn giản thành hai mảng con
A[a..c] và A[c+1..b] bởi điểm chia ở giữa mảng, c = (a+b)/2 . Còn trong
thuật toán sắp xếp nhanh, việc “chia mảng thành hai mảng con” là một
quá trình biến đổi phức tạp để từ mảng A[a..b] ta thu được hai mảng con
A[a..k-1] và A[k+1..b] thỏa mãn các tính chất sau :
A[i].key ≤ A[k].key với mọi i, a ≤ i ≤ k-1.
A[j].key > A[k].key với mọi j, k+1 ≤ j ≤ b.


196
Nếu thực hiện được sự phân hoạch mảng A[a..b] thành hai mảng
con A[a..k-1] và A[k+1..b] thỏa mãn các tính chất trên, thì n ếu s ắp x ếp
được các mảng con đó ta sẽ có toàn bộ mảng A[a..b] được sắp xếp. Giả
sử Partition(A, a, b, k) là hàm phân hoạch mảng A[a..b] thành hai m ảng
con A[a..k-1] và A[k+1..b]. Thuật toán sắp xếp nhanh là thu ật toán đ ệ quy
được biểu diễn bởi hàm đệ quy như sau :
void QuickSort(Item A[] , int a , int b)
//Sắp xếp mảng A[a..b] với a ≤ b.
{
if (a < b)
{
int k;
Partition(A, a, b, k);
if (a right. Lúc này ta
dễ thấy rằng, mọi thành phần trong mảng A[a..right] có khóa nhỏ hơn hay
bằng mốc, còn mọi thành phần trong mảng A[left..b] có khóa lớn hơn
mốc. Cuối cùng ta trao đổi A[a] và A[right] để đặt mốc vào vị trí k = right.
Hàm phân hoạch được viết như sau :
void Partition( Item A[] , int a , int b , int & k)
{
keyType pivot = A[a].key;
int left = a + 1;
int right = b;
do {
while (( left 8. A[right] = 14 > 8 nên right được giảm đi và dừng lại tại right =
4, vì A[4] < 8. Ta có hoàn cảnh sau :
8 3 5 7 6 14 12 1 13 15
7


right left


199
Đến đây right < left, ta dừng lại, trao đổi A[0] với A[4] ta thu được phân
hoạch với k = right = 4.

6 3 5 7 8 14 12 1 13 15
7


k




Phân tích sắp xếp nhanh
Chúng ta cần đánh giá thời gian chạy T(n) của thuật toán s ắp xếp
nhanh trên mảng A[a..b] có n phần tử, n = b – a + 1. Trước hết ta cần đánh
giá thời gian thực hiện hàm phân hoạch. Thời gian phân hoạch là th ời gian
đi qua mảng (hai biến left và right chạy từ hai đầu mảng cho tới khi chúng
gặp nhau), tại mỗi vị trí mà left và right ch ạy qua ta c ần so sánh thành
phần ở vị trí đó với mốc và các trao đổi khi cần thiết. Do đó khi phân
hoạch một mảng n phần tử ta chỉ cần thời gian O(n).
Thời gian trong trường hợp tốt nhất . Trường hợp tốt nhất xảy
ra khi mà sau mỗi lần phân hoạch ta nhận đ ược hai mảng con bằng nhau.
Trong trường hợp này, từ hàm đệ quy QuickSort, ta suy ra quan h ệ đ ệ quy
sau :
T(1) = O(1)
T(n) = 2 T(n/2) + O(n) với n > 1.
Đây là quan hệ đệ quy mà ta đã gặp khi phân tích s ắp x ếp hòa nh ập. Nh ư
vậy trong trường hợp tốt nhất thời gian chạy của QuickSort là O(n logn).
Thời gian trong trường hợp xấu nhất. Trường hợp xấu nhất là
trường hợp mà sau mỗi lần phân hoạch mảng n ph ần tử ta nh ận đ ược
mảng con n – 1 phần tử ở một phía của mốc, còn phía kia không có ph ần



200
tử nào. (Dễ thấy rằng trường hợp này xẩy ra khi ta phân hoạch một
mảng đã được sắp). Khi đó ta có quan hệ đệ quy sau :
T(1) = O(1)
T(n) = T(n – 1) + O(n) với n > 1
Ta có :
T(1) = C
T(n) = T(n – 1) + nC với n > 1
Trong đó C là hằng số nào đó. Bằng cách thế lặp ta có :
T(n) = T(1) + 2C + 3C + … + nC
n
i = Cn(n+1)/2
=C
i =1




Do đó trong trường hợp xấu nhất, thời gian chạy của s ắp xếp nhanh là
O(n2).
Thời gian trung bình. Bây giờ ta đánh giá thời gian trung bình T tb(n)
mà QuickSort đòi hòi để sắp xếp một mảng có n phần tử. Giả sử mảng
A[a..b] chứa n phần tử được đưa vào mảng một cách ngẫu nhiên. Khi đó
hàm phân hoạch Partition(A, a, b, k) sẽ cho ra hai m ảng con A[a..k – 1] và
A[k + 1..b] với k là một trong các chỉ số từ a đến b v ới xác su ất nh ư nhau
và bằng 1/n. Vì thời gian thực hiện hàm phân hoạch là O(n), t ừ hàm
QuickSort ta suy ra quan hệ đệ quy sau :
n
1
Ttb(n) = [ Ttb(k - 1) + Ttb(n - k)] + O(n)
n
k =1


Hay
n
1
Ttb(n) = [ Ttb(k - 1) + Ttb(n - k)] + nC (1)
n
k =1




201
Trong đó C là hằng số nào đó. Chú ý rằng
n n
Ttb(k - 1) = Ttb(n - k)
k =1
k =1

Do đó có thể viết lại (1) như sau :
n
2
Ttb(n) = Ttb(k - 1) + nC (2)
n
k =1

Trong (2) thay n bới n – 1 ta có :


n −1
2
Ttb(n - 1) = Ttb(k - 1) + (n – 1)C (3)
n −1
k =1


Nhân (2) với n, nhân (3) với n – 1 và trừ cho nhau ta nhận được
n Ttb(n) = (n + 1) Ttb(n - 1) + (2n – 1)C
Chia đẳng thức trên cho n(n + 1) ta nhận được quan hệ đệ quy sau :


2n - 1
Ttb (n) Ttb (n - 1)
= + C (4)
n ( n +1)
n +1 n

Sử dụng phép thế lặp, từ (4) ta có
2n - 1
Ttb (n) Ttb (n - 1)
= + C
n ( n +1)
n +1 n

2n - 1
2n - 3
Ttb (n - 2)
= + + n ( n +1) C
( n −1) n
n −1

...
2i − 1
n
Ttb (n) Ttb (1)
= +c (5)
i (i + 1)
n +1 2 i =1


Ta có đánh giá


202
2i − 1 n
n n
2 dx
≤ ≤2 ≤ 2logn
k =1 i (i + 1) i x
i =1 1


Do đó từ (5) ta suy ra
Ttb (n)
= O(logn)
n +1

hay Ttb(n) = O(n logn).
Trong trường hợp xấu nhất, QuickSort đòi hỏi thời gian O(n 2),
nhưng trường hợp này rất ít khi xảy ra. Thời gian trung bình c ủa
QuickSort là O(n logn), và thời gian trong trường hợp xấu nhất của
MergeSort cũng là O(n logn). Tuy nhiên thực tiễn cho thấy rằng, trong
phần lớn các trường hợp QuickSort chạy nhanh hơn các thuật toán sắp
xếp khác.

SẮP XẾP SỬ DỤNG CÂY THỨ TỰ BỘ PHẬN
17.4

Trong mục này chúng ta trình bày phương pháp sắp xếp sử d ụng
cây thứ tự bộ phận (heapsort). Trong mục 10.3, chúng ta biết rằng m ột
cây thứ tự bộ phận n đỉnh có thể biểu diễn bởi mảng A[0..n-1], trong đó
gốc cây được lưu trong A[0], và nếu một đỉnh được lưu trong A[i], thì
đỉnh con trái (nếu có) của nó được lưu trong A[2*i + 1], còn đ ỉnh con ph ải
nếu có của nó được lưu trong A[2*i + 2]. Mảng A thoả mãn tính ch ất sau
(ta sẽ gọi là tính chất heap):
A[i].key = A[n-1].key
Trong quá trình trên, sau mỗi lần trao đổi A[0] với A[m] (với m=n-1,
…,1), ta sẽ nhận được mảng A[0…m-1] thoả mãn tính chất heap v ới m ọi
i >= 1, trừ i = 0. Điều này có nghĩa là cây nh ị phân được bi ểu di ễn b ởi
mảng A[0..m-1] đã thoả mãn tính chất thứ tự bộ phận, chỉ trừ gốc. Đ ể nó
trở thành cây thứ tự bộ phận, ta chỉ cần đẩy dữ liệu lưu ở gốc xuống vị
trí thích hợp trong cây, bằng cách sử dụng hàm ShiftDown (Xem mục
10.3.3).
Còn một vấn đề cần giải quyết, đó là biến đổi mảng cần sắp xếp
A[0..n-1] thành mảng thoả mãn tính chất heap. Điều này có nghĩa là ta
phải biến đổi cây nhị phân được biểu diễn bởi mảng A[0..n-1] thành cây
thứ tự bộ phận. Muốn vậy, với i chạy từ n/2-1 giảm xuống 0, ta chỉ cần
sử dụng hàm SiftDown để đẩy dữ liệu lưu ở đỉnh i xuống vị trí thíc hợp
trong cây. Đây là cách xây dựng cây thứ tự bộ phận mà chúng ta đã trình
bày trong 10.3.2.
Bây giờ ta viết lại hàm ShiftDown cho thích hợp v ới s ự s ử dụng nó
trong thuật toán. Giả sử mảng A[a..b] (a < b) đã thoả mãn tính chất heap
với mọi i >= a+1. Hàm ShiftDown(a,b) sau đây th ực hiện việc đẩy A[a]
xuống vị trí thích hợp trong mảng A[a..b] để mảng thoả mãn tính ch ất
heap với mọi i >= a.
void ShiftDown(int a, int b)
{
int i = a;
int j = 2 * i + 1;
while (j 1
{
for (int i = n / 2 – 1 ; i >= 0 ; i--)
//Biến đổi mảng A[0..n-1]
ShiftDown(i,n-1);
// thành m ảng tho ả mãn tính ch ất
heap
for (int i = n – 1 ; i >= 1 ; i--)
{
swap(A[0],A[i]);
ShiftDown(0,i - 1);
}

}

Phân tích HeapSort.
Thời gian thực hiện lệnh lặp (1) là thời gian xây dựng cây thứ tự bộ
phận mà chúng ta đã xét trong mục 10.3.2. Theo ch ứng minh đã đ ưa ra
trong 10.3.2, lệnh lặp (1) chỉ đòi hỏi thời gian O(n). Trong l ệnh lặp (2), s ố
lần lặp là n-1. Thân vòng lặp (2), với i = n-1 là


205
swap(A[0],A[n - 1]);
ShiftDown(0,n - 2);
Đây là các lệnh thực hiện DeleteMin trên cây thứ tự bộ phận được biểu
diễn bởi mảng A[0..n-1], và dữ liêụ có khoá nhỏ nhất được lưu vào A[n-
1]. Trong mục 10.3.1, ta đã chứng tỏ rằng DeleteMin chỉ cần thời gian
O(logn). Như vậy thân của lệnh lặp (2) cần th ời gian nhi ều nh ất là
O(logn). Do đó lệnh (2) cần thời gian O(nlogn). Vì vậy, th ời gian th ực
hiện HeapSort là O(nlogn).




BÀI TẬP.

1. Cho mảng các số nguyên (8, 1, 4, 1, 5, 2, 6, 5). Hãy sắp xếp mảng
này bằng cách sử dụng:
a. Sắp xếp lựa chọn.
b. Sắp xếp xen vào.
c. Sắp xếp nổi bọt.
d. Sắp xếp nhanh.
e. Sắp xếp hoà nhập.
f. Sắp xếp sử dụng cây thứ tự bộ phận.

Cần đưa ra kết quả thực hiện mỗi bước của thuật toán.

2. Hãy đánh giá thời gian chạy của các thuật toán sắp xếp:
a. Sắp xếp lựa chọn.
b. Sắp xếp xen vào.
c. Sắp xếp nhanh.
d. Sắp xếp hoà nhập.
Trong các trường hợp sau:
a. Mảng đầu vào có tất cả các phần tử có khoá bằng nhau.
b. Mảng đầu vào đã được sắp.

3. Viết hàm phân hoạch mảng A[a …b] với phần tử được chọn làm
mốc là phần tử đứng giữa mảng, tức là phần tử A[(a + b) / 2].

206
4. Một thuật toán sắp xếp được xem là ổn định, nếu trật tự của các
phần tử có khoá bằng nhau trong mảng đầu vào và trong mảng kết
quả là như nhau. Trong các thuật toán sắp xếp, thuật toán nào là ổn
định, thuật toán nào là không ổn định?

5. Cho mảng chứa n số nguyên và một số nguyên k. Ta muốn biết
trong mảng có chứa 2 số nguyên có tổng bằng k hay không. Chẳng
hạn, với mảng (8, 4, 1, 5, 6, 3) và k = 10 thì c ầu tr ả l ời là có, vì 4 +
6 = 10.
a. Hãy đưa ra thuật toán không sử dụng sắp xếp mảng. Đánh
giá thời gian chạy của thuật toán.
b. Hãy đưa ra thuật toán sử dụng sắp xếp mảng, thuật toán chỉ
đòi hỏi thời gian O(nlogn).

6. Phần tử nhỏ nhất thứ k (k = 1, 2, …) trong mảng chứa n ph ần t ử
A[1…n] là phần tử p trong mảng sao cho s ố phần t ử < p là < k, và
số phần tử ≤ p là ≥ k. Ví dụ, trong mảng A = (5, 7, 5, 9, 3, 5) thì
phần tử nhỏ nhất là 3, còn phần tử nhỏ nhất thứ 2, 3, 4 đ ều là 5, vì
số phần tử < 5 là 1, còn số phần tử ≤ 5 là 4. Hãy đưa ra thuật toán
tìm phần tử nhỏ nhất thứ k trong mảng. (Gợi ý: sử dụng ph ương
pháp phân hoạch như trong QuickSort để biến đổi mảng đã cho
thành mảng A[1 …n] sao cho phần tử nhỏ nhất th ứ k là A[k], t ức là
với 1 ≤ i < k thì A[i] < A[k], còn với k < j ≤ n thì A[j] ≥ A[k] )




207
Đề thi vào lớp 10 môn Toán |  Đáp án đề thi tốt nghiệp |  Đề thi Đại học |  Đề thi thử đại học môn Hóa |  Mẫu đơn xin việc |  Bài tiểu luận mẫu |  Ôn thi cao học 2014 |  Nghiên cứu khoa học |  Lập kế hoạch kinh doanh |  Bảng cân đối kế toán |  Đề thi chứng chỉ Tin học |  Tư tưởng Hồ Chí Minh |  Đề thi chứng chỉ Tiếng anh
Theo dõi chúng tôi
Đồng bộ tài khoản