QuickSort, HeapSort và MergeSort
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (274.2 KB, 20 trang )
THỰC TẬP CƠ SỞ
Đề : Viết một chương trình minh họa thuật toán sắp xếp
QuickSort, HeapSort và MergeSort
1
LỜI CẢM ƠN
Trong quá trình thực hiện thực tập cơ sở, chúng em xin gửi lời cảm ơn đến giáo viên
hướng dẫn cơ Hà Thị Thanh Ngà đã tận tình hướng dẫn trong suốt quá trình chúng em thực
hiện và hoàn thành thực tập cơ sở này.
Chúng em cũng xin chân thành cảm ơn quý Thầy, Cô trong khoa Công nghệ thơng tin
đã tận tình truyền đạt kiến thức trong quá trình học tập. Với vốn kiến thức được tiếp thu
trong q trình học khơng chỉ là nền tảng cho q trình nghiên cứu khóa luận mà cịn là hành
trang quí báu để em bước vào đời một cách vững chắc và tự tin.
Cuối cùng, chúng em xin kính chúc q Thầy, Cơ và gia đình dồi dào sức khỏe và
thành công trong sự nghiệp giảng dạy cao.
2
Mục Lục
Table of Contents
I. CÁC THUẬT TOÁN SẮP XẾP.......................................................................................................................3
1. BÀI TỐN SẮP XẾP...................................................................................................................................3
1.1. Bài tốn sắp xếp......................................................................................................................................3
1.2 Ứng dụng của sắp xếp..............................................................................................................................3
1.3 Các loại thuật toán sắp xếp......................................................................................................................4
1. Sơ đồ tổng quát.............................................................................................................................................6
2.Các bước của Quick Sort..............................................................................................................................6
3. Ý tưởng thuật toán Quick Sort...................................................................................................................8
4. Độ phức tạp của thuật toán.........................................................................................................................8
5. Ưu điểm và nhược điểm...............................................................................................................................9
III. SẮP XẾP HEAP SORT (Vun đống).............................................................................................................9
1. Tổng quát.......................................................................................................................................................9
1.1 Định nghĩ Heap........................................................................................................................................9
1.2 Tính chất của Heap.................................................................................................................................10
1.3 Heap Sort................................................................................................................................................10
Sắp xếp bằng heapsort :.............................................................................................................................10
2. Các bước của Heapsort..............................................................................................................................10
3. Độ phức tạp của thuật toán.......................................................................................................................14
4. Ưu điểm và nhược điểm của thuật toán..................................................................................................15
III. SẮP XẾP MERGE SORT (Trộn)...............................................................................................................15
1. Tổng quát.....................................................................................................................................................15
2. Các bước thực hiện....................................................................................................................................16
3. Độ phức tạp của thuật toán.......................................................................................................................17
3
4. Ý tưởng thuật toán.....................................................................................................................................18
5. Ưu điểm và nhược điểm.............................................................................................................................18
4
I. CÁC THUẬT TOÁN SẮP XẾP
1. BÀI TOÁN SẮP XẾP
1.1. Bài tốn sắp xếp
Sắp xếp (Sorting) là q trình tổ chức lại họ các dữ liệu theo thứ tự giảm dần hoặc tăng dần
(ascending or descending order).
Dữ liệu cần sắp xếp có thể là:
-
Số nguyên (Integers);
Xâu ký tự (Character strings);
Đối tượng (Objects).
Khóa sắp xếp (Sort key) là bộ phận của bản ghi xác định thứ tự sắp xếp của bản ghi trong họ các bản
ghi. Ta cần sắp xếp các bản ghi theo thứ tự của các khóa.
Chú ý:
- Việc sắp xếp tiến hành trực tiếp trên bản ghi đòi hỏi di chuyển vị trí bản ghi. có thể là thao tác rất
tốn kém.
- Vì vậy, người ta thường xây dựng bảng khóa gồm các bản ghi chỉ có hai trường là (khóa, con trỏ):
+ Trường "khóa" chứa giá trị khóa;
+ Trường "con trỏ" để ghi địa chỉ của bản ghi tương ứng.
- Việc sắp xếp theo khóa trên bảng khóa khơng làm thay đổi bảng chính, nhưng trình tự các bản ghi
trong bảng khóa cho phép xác định trình tự các bản ghi trong bảng chính.
Ta có thể hạn chế xét bài toán sắp xếp dưới dạng sau đây:
Input: Dãy n số A = (a1, a2, ..., an),
Output: Một hoán vị (sắp xếp lại) (a1, a2,..., a') của dãy số đã cho thỏa mãn:
a’1 a’2 … a’n
1.2 Ứng dụng của sắp xếp
- Quản trị cơ sở dữ liệu (Database management);
- Khoa học và kỹ thuật (Science and engineering);
- Các thuật toán lập lịch (Scheduling algorithms), chẳng hạn, thiết kế chương
mpiler design), truyền thơng (telecommunication),..., ;
-Máy tìm kiếm web (Web search engine);
Và nhiều ứng dụng khác…
5
1.3 Các loại thuật toán sắp xếp
-Sắp xếp trong (internal sort): địi hỏi họ dữ liệu được đưa tồn bộ vào bộ nhớ trong máy tính.
- Sắp xếp ngồi (external sort): họ dữ liệu khơng thể cùng lúc đưa tồn bộ vào bộ nhớ trong, nhưng
có thể đọc vào từng bộ phận từ bộ nhớ ngồi.
1.3.1 Có hai phép tốn cơ bản mà thuật toán sắp xếp thường phải sử dụng
- Đổi chỗ (Swap): thời gian thực hiện là O(1), chẳng hạn sử dụng cài đặt trên C sau đây:
void swap( datatype &a, datatype &b) {
data type temp = a; // data type-kiểu dữ liệu của phần tử
a = b;
b = temp;
}
So sánh: hàm Compare(a,b) trả lại true nếu a đi trước b trong thứ tự cần sắp xếp và false nếu ngược
lại.
Các thuật toán chỉ sử dụng phép toán so sánh để xác định thứ tự giữa hai phần tử giữa hai phần tử
được gọi là thuật toán sử dựng phép so sánh (Comparison-based sorting algorithm).
1.3.2 Phân loại các thuật toán sắp xếp
Thuật toán
Thuật toán
đơn giản:
hiệu quả:
Cận dưới cho sắp Thuật toán
xếp so sánh:
đặc biệt:
O(n2)
O(n log n)
(n log n)
Xử lý các tập dữ
liệu lớn
O(n)
Sắp xếp chèn
Sắp xếp vun đống
Sắp xếp phân cụm
Sắp xếp chọn
Sắp xếp trộn
Sắp xếp cơ số
Sắp xếp nỗi bọt
Sắp xếp nhanh
…
Sắp xếp ngoài
1.4 Độ phức tạp của thuật toán
1.4.1 Bậc O-lớn
Gọi n là độ lớn đầu vào. Tùy thuộc từng bài tốn mà n có thể nhận những giá trị khác nhau.
Chẳng hạn, bài tốn tính giai thừa thì n chính là số cần tính giai thừa. Nhiều bài toán số trị, chẳng
6
hạn tính sai phân thì n là số chữ số có nghĩa cần đạt được. Trong các phép tính đối với ma trận thì n
là số hàng hoặc cột của ma trận.
Độ phức tạp của bài toán phụ thuộc vào n. Ở đây ta không chỉ đặc trưng độ phức tạp bởi số
lượng phép tính, mà dùng một đại lượng tổng quát là tài nguyên cần dùng R(n). Đó có thể là số
lượng phép tính (có thể tính cả số lần truy nhập bộ nhớ, hoặc ghi vào bộ nhớ); nhưng cũng có thể là
thời gian thực hiện chương trình (độ phức tạp về thời gian) hoặc dung lượng bộ nhớ cần phải cấp để
chạy chương trình (độ phức tạp về không gian).
Xét quan hệ giữa tài nguyên và độ lớn đầu vào, nếu như tìm được hằng số C>0, C không phụ
thuộc vào n, sao cho với n đủ lớn, các hàm R(n),g(n) đều dương và
R(n) ≤ C.g(n)
thì ta nói thuật tốn có độ phức tạp cỡ O(g(n)).
1.4.2 Diễn giải
Độ phức tạp khơng phải là độ đo chính xác lượng tài nguyên máy cần dùng, mà đặc trưng
cho động thái của hệ thống khi kích thước đầu vào tăng lên. Chẳng hạn với thuật tốn có độ phức
tạp tuyến tính O(n) (xem phần dưới), nếu kích thước đầu vào tăng gấp đơi thì có thể ước tính rằng
tài ngun cần dùng cũng tăng khoảng gấp đôi. Nhưng với thuật tốn có độ phức tạp bình phương
O(n2) thì tài ngun sẽ tăng gấp bốn. Mặt khác, với thuật tốn có độ phức tạp hàm mũ O(2n) thì chỉ
cần cơng thêm 2 đơn vị vào độ lớn đầu vào cũng đã làm tài nguyên tăng gấp 4 lần (tức là theo cấp số
nhân) rồi.
Các độ phức tạp thường gặp đối với các thuật tốn thơng thường gồm có:
Độ phức tạp hằng số, O(1). Số phép tính/thời gian chạy/dung lượng bộ nhớ không phụ thuộc
vào độ lớn đầu vào. Chẳng hạn như các thao tác hệ thống: đóng, mở Tập tin.
Độ phức tạp tuyến tính, O(n). Số phép tính/thời gian chạy/dung lượng bộ nhớ có xu hướng tỉ
lệ thuận với độ lớn đầu vào. Chẳng hạn như tính tổng các phần tử của một mảng một chiều.
Độ phức tạp đa thức, O(P(n)), với P là đa thức bậc cao (từ 2 trở lên). Chẳng hạn như các
thao tác tính tốn với mảng nhiều chiều (tính định thức ma trận).
Độ phức tạp logarit, O(log n) (chú ý: bậc của nó thấp hơn so với O(n)). Chẳng hạn thuật tốn
Euclid để tìm ước số chung lớn nhất.
Độ phức tạp hàm mũ, O(2n). Trường hợp này bất lợi nhất và sẽ rất phi thực tế nếu thực hiện
thuật toán với độ phức tạp này.
7
II. SẮP XẾP QUICK SORT (Nhanh)
1. Sơ đồ tổng quát
Thuật toán sắp xếp nhanh được phát triển bởi Hoare năm 1960 khi ơng đang làm việc cho
hàng máy tính nhỏ Elliott Brothers ở Anh. Theo thống kê tính tốn, Quick Sort (viết tắt là
QS) là thuật toán sắp xếp nhanh nhất hiện nay. QS có thời gian tính trung bình là On log n),
tuy nhiên thời gian tính tốt nhất của nó lại là O(n2). QS là thuật tốn sắp xếp tại chỗ, nhưng
nó khơng có tính ổn định. QS khá đơn giản về lý thuyết, nhưng lại không dễ cài đặt.
Quick Sort là thuật toán sắp xếp được phát triển dựa trên kỹ thuật chia để trị. Thuật toán có
thể mơ tả đệ quy như sau :
a) Neo đệ quy (Base case): nếu dãy chỉ cịn khơng q một phần tử thì nó là đây được sắp và trả
lại ngay dãy này mà khơng phải làm gì cả.
b) Chia (Divide):
Chọn một phần tử trong dãy và gọi nó là phần tử chốt p (pivot).
Chia dãy đã cho ra thành hai dãy con: dãy con trái (L) gồm những phần tử khơng
lớn hơn phần tử chốt, cịn dãy con phải (R ) gồm các phần tử không nhỏ hơn
phân tử chốt. Thao tác này được gọi là “Phân đoạn”(Partition)
c) Trị (Conquer) : Lặp lại một cách đệ quy thuật toán đối với hai dãy con L và R
d) Tổng hợp (Combine): Dãy được sắp xếp là L p R
2.Các bước của Quick Sort
Bước 1: Chọn phần tử chốt.
3
5
33
11
8
12
4
23
8
Select piovot
Việc chọn phần tử chốt có vai trị quyết định đối với hiệu quả của thuật toán. Tốt nhất nếu chọn
được phần tử chốt là phần tử đứng giữa trong danh sách được sắp xếp (ta gọi phần tử như vậy là
trung vị/median). Khi đó, sau log2n lần phân đoạn, ta sẽ đạt tới danh sách với kích thước bằng 1.
Tuy nhiên, điều đó rất khó thực hiện. Người ta thường sử dụng các cách chọn phần tử chốt sau đây:
-
Chọn phần tử trái nhất (đứng đầu làm phần tử chốt.
Chọn phần tử phải nhất (đứng cuối) làm phần tử chốt.
Chọn phần tử đứng giữa danh sách làm phần tử chốt.
Chọn phần tử trung vị trong ba phần tử đứng đầu, đứng giữa và đứng cuối làm phần tử chốt
(Knuth).
Chọn ngẫu nhiên một phần tử làm phần tử chốt.
Bước 2: Sắp xếp
8
- Các phần tử trong dãy sẽ được so sánh với phần tử chốt và sẽ đổi vị trí cho nhau, hoặc cho phần tử
chốt. Nếu nó lớn hơn chốt mà lại năm trước chốt hoặc nhỏ hơn chốt mà lại nằm sau chốt.
- Khi việc đổi chỗ đã được thực hiện xong thì dãy khố lúc đó được phân làm hai đoạn: một đoạn
gồm các khoá nhỏ hơn phân tử chốt, một đoạn gồm các khoá lớn hơn phần tử chốt cịn khố chốt thì
ở giữa hai đoạn nói trên, đó cũng chính là vị trí thực của nó trong dãy khi đã được sắp xếp, tới đây
coi như kết thúc một lượt sắp xếp.
- Ở các lượt tiếp theo cũng áp dụng một kỹ thuật tương tự đối với các phân đoạn cịn lại. Lẽ tất
nhiên chỉ có một phân đoạn được xử lý ngay sau đó, cịn một phân phải để lúc khác, nghĩa là phải
được “ghi nhớ”lại.
9
Bước 3: Tổng hợp
Dãy được sắp xếp là :
1
3
4
5
8
8
12
23
33
3. Ý tưởng thuật toán Quick Sort
Chọn phần tử chốt.
Khai báo 2 biến con trỏ để trỏ để duyệt 2 phía của phần tử chốt.
Biến bên trái trỏ đến từng phần tử mảng con bên trái của phần tử chốt.
Biến bên phải trỏ đến từng phần tử mảng con bên phải của phần tử chốt.
Khi biến bên trái nhỏ hơn phần tử chốt thì di chuyển sang phải.
Khi biến bên phải nhỏ hơn phần tử chốt thì di chuyển sang trái.
Nếu khơng xảy ra trưởng hợp 5 và 6 thì tráo đổi giá trị 2 biến trái và phải.
Nếu trái lơn hơn phải thì đây là giá trị chốt mới.
4. Độ phức tạp của thuật tốn.
Thời gian tính của Quick Sort phụ thuộc vào việc phép nhân chia là cân bằng hay không cân
bằng và điều đó phải phụ thuộc vịa việc phần tử nào được chọn là chốt.
Phân đoạn không cân bằng: thực sự khơng có phần nào cả do đó một bài tốn con có kích
thước n -1 cịn bài tốn kia có kích thước 0.
Cơng thức đệ quy cho thời gian tính trong tình huống này là:
Ta có:
10
…
Cộng vế theo vế các đẳng thức trên, sau khi đơn giản biểu thức ta thu được:
Phân đoạn hoàn hảo (Perefect partition): việc phân đoạn luôn được thực hiện dưới dàng
phân đơi, như vậy mỗi bài tốn có kích thước cỡ n/2
…..
…..
…..
Phân đoạn cân bằng: việc phân đoạn được thực hiện ở đâu đó quanh điểm giữa, nghĩa là
một bài tốn con có kích thước n – k cịn bài tốn kia có kích thước k.
5. Ưu điểm và nhược điểm
Ưu điểm: Tuỳ cách chọn pivot mà tốc độ của thuật toán nhanh hay chậm
Nhược điểm: Code khá phức tạp
III. SẮP XẾP HEAP SORT (Vun đống)
1. Tổng quát
1.1 Định nghĩ Heap
Giả sử xét trường hợp sắp xếp tăng dần, khi đó Heap được định nghĩa là một dãy các phần tử
al,..,ar thỗ các quan hệ sau với mọi iỴ [l,r]
ai ³ a2i
ai ³ a2i+1
(ai,a2i), (ai,a2i+1) là các cặp phần tử liên đới
11
1.2 Tính chất của Heap
Tính chất 1: Nếu al,.,ar là một Heap thì khi cắt bỏ một số phần tử ở hai đầu của Heap thì dãy
con cịn lại vẫn là một Heap .
Tính chất 2: Nếu các phần tử a1,..,an là một Heap thì phần tử a1 (đầu heap) ln là phần tử
lớn nhất trong Heap.
Tính chất 3: Mọi dãy al,al+1,…,ar với 2l > r là một Heap
1.3 Heap Sort
Vun đống chia làm hai giai đoạn:
Giai đoan một : Một dãy khóa k1,k2,....,kn biểu diễn của một cây nhị phân hoàn chỉnh mà ki
là giá trị lưu trong nút thứ i, nút con của nút i là 2i và nút 2i+1, nút cha của nút thứ j là nút thứ j div
2. Đầu tiên cây nhị phân biểu diễn bằng khóa được biến đổi lại dãy khóa đã cho để nó biểu diễn một
đống.
Như vậy khóa ở nút gốc của đống chính là khóa lớn nhất( khóa trội) so với mọi khóa trên
cây.
Gia đoạn hai: là giai đoạn sắp xếp, nhiều lượt xử lý được thực hiện, mỗi lượt ứng với hai
phép:
- Đưa khóa trội về vị trí thực của nó bằng cách đổi chỗ cho khóa hiện đang ở vị trí đó.
- “Vun lại thành đống” đối với cây gồm các khóa cịn lại ( sau khi đã loại khóa trội ra ngồi).
Sắp xếp bằng heapsort :
1. Đổi chỗ (Swap): Sau khi mảng a[1..n] đã là đống, lấy phần tử a[1] trên đỉnh của đống ra khỏi
đống đặt vào vị trí cuối cùng n, và chuyển phần tử thứ cuối cùng a[n] lên đỉnh đống thì phần
tử a[n] đã được đứng đúng vị trí.
2. Vun lại: Phần cịn lại của mảng a[1..n-1] chỉ khác cấu trúc đống ở phần tử a[1]. Vun lại mảng
này thành đống với n-1 phần tử.
3. Lặp: Tiếp tục với mảng a[1..n-1]. Quá trình dừng lại khi đống chỉ còn lại một phần tử.
2. Các bước của Heapsort
2.1 Hiệu chỉnh dãy số ban đầu thành Heap
2.2 Sắp xếp dãy số dựa trên Heap
Bước 1: Đưa phần tử lớn nhất về vị trí đúng ở cuối dãy:
r = n; Hoán vị (a1, ar);
Bước 2: Loại bỏ phần tử lớn nhất ra khỏi heap: r = r – 1;
12
Hiệu chỉnh phần còn lại của dãy a1, a2,…, ar thành một Heap.
Bước 3: Nếu r > 1 (heap còn phần tử): Lặp lại bước 2
Ngược lại: Dừng.
Dựa trên tính chất 3 của Heap, ta có thể thực hiện giai đoạn 1 bằng cách bắt đầu từ heap mặc
nhiên an/2+1, an/2+1, …., an, lần lượt thêm vào các phần tử an/2, an/2-1, …., a1 ta sẽ nhận được
heap theo mong muốn.
13
14
15
3. Độ phức tạp của thuật toán
Mỗi cây nhị phân đầy đủ có n nút, chiều cao h
Q trình chỉnh heap từ nút giá trị thứ i giá trị nút i dịch chuyển nhiều nhất là h lần ( h chiều cao của
cây)
Từ nút thứ i nút thứ n
h=
Thời gian chỉnh heap từ nút thứ i đến nút thứ n
O
16
Thời gian tạp heap
T(n)=
Áp dụng tính chất: =
Từ
đến có số hạng
4. Ưu điểm và nhược điểm của thuật toán
Ưu điểm:
-
Trong trường hợp xấu nhất tốt hơn QuickSort
- Thời gian sắp xếp 0(nlog2n) trong mọi trường hợp
- Không sài đệ quy
- Trong trường hợp xấu nhất tốt hơn QuickSort
- Mảng đã được sắp xếp 1 phần : Heap nhanh hơn Quick
Nhược điểm:
-
Trường hợp trung bình chạy chậm so với QuickSort
Chạy chậm hơn QuickSort-Merge Sort.
III. SẮP XẾP MERGE SORT (Trộn)
1. Tổng quát
Giả sử có hai danh sách đã được sắp xếp a[1..m] và b[1..n]. Ta có thể trộn chúng lại thành
một danh sách mới c[1...m + n] được sắp xếp theo cách sau:
So sánh hai phần tử đứng đầu của hai danh sách, lấy phần tử nhỏ hơn cho vào danh sách
mới. Tiếp tục như vậy cho tới khi một trong hai danh sách là rỗng.
Khi một trong hai danh sách là rỗng ta lấy phần còn lại của danh sách kia cho vào cuối danh
sách mới.
17
2. Các bước thực hiện
Giải thuật trộn chia danh sách thành hai danh sách con và tiến hành 4 bước:
0
1
2
3
4
5
6
7
78
53
62
59
89
11
29
50
Bước 1: Chia danh sách
Danh sách trái
78
53
62
Danh sách phải
59
89
11
29
50
Bước 2: Sắp xếp trộn danh sách trái
78
53
62
59
53
78
59
62
53
59
62
78
Bước 3: Sắp xếp trộn danh sách phải
89
11
29
50
11
89
29
50
11
29
50
89
Bước 4: Sắp xếp trộn danh sách trái và phải lại với nhau
78
53
62
59
89
11
29
50
Kết quả là :
11
29
50
53
59
62
78
89
18
3. Độ phức tạp của thuật toán
Trường hợp tốt nhất : dãy đã được sắp xếp sẵn=> độ phức tạp là O(1)
Trường hợp xấu nhất : O(nlog2n)
Chứng minh :
Sắp xếp mảng a với n phần tử
T(n) = t(k) + t(n-k) + cn
+ t(k): thời gian sắp xếp mảng với k phần tử
+ t(n-k): thời gian sắp xếp mảng với n - k phần tử
+ cn : tổng thời gian sắp xếp lại mảng a
Ta sẽ sắp xếp 2 mảng:
+ Mảng 1: có n/2 phần tử
+ Mảng 2: có n/2 phần tử
T(n) = t (n / 2) + t (n / 2) + cn
= 2t( n / 2) + cn
= 2[2t(n / 4) + c*(n / 2)] + cn
= 22t(n / 4) + 2cn
= 22[2t(n / 8) + c*(n/4)] + 2cn
= 23t(n / 8) + 3cn
...
= 2kt(n / 2k) + kcn (1)
(1) Sẽ dừng khi đạt được t(1)
Ta sẽ đạt được t(1) n=2k log2n = k
T(n) = 2log2nt(1) + cn*(log2n)
T(n) = nt(1) + cn*log2n
=A+B
+ (A): độ phức tạp 0(n)
+ (B): độ phức tạp 0(nlog2n)
19
Chi phí cho trường hợp tốt nhất là 0(nlog2n).
4. Ý tưởng thuật tốn
- Thuật tốn Merge cho khơng gian cần sắp xếp thành 2 không gian con
- Nếu không gian con thứ 1 có nhiều hơn 1 phần tử thì sắp xếp khơng gian con này bằng thuật tốn
Merge Sort
- Nếu khơng gian con thứ 2 có nhiều hơn 1 phần tử thì sắp xếp khơng gian này bằng thuật tốn
Merge Sort
- Trộn 2 khơng gian cịn đã được sắp xếp lại với nhau.
5. Ưu điểm và nhược điểm
Thuật toán trộn tự nhiên khác thuật toán trộn trực tiếp ở chỗ thay vì ln cứng nhắc phân hoạch
theo dãy con có chiều dài k, việc phân hoạch sẽ theo đơn vị là đường chạy. ta chỉ cần 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 thuật tốn vì dãy đã có
thứ tự là dãy chi có một đường chạy.
Một nhược điểm lớn nữa của thuật toán trộn là khi cài đặt thuật tố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ì 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 để 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.
20
