Ứng dụng các thuật toán sắp xếp
Tài li
ệ
u hư
ớ
ng d
ẫ
n th
ự
c hành môn
C
ấ
u trúc d
ữ
li
ệ
u và gi
ả
i thu
ậ
t
Trang
1
CÁC THUẬT TOÁN SẮP XẾP
MỤC TIÊU
Hoàn tất bài thực hành này, sinh viên có thể:
- Hiểu được các thuật toán sắp xếp: Selection Sort, Heap Sort, Quick Sort, Merge Sort.
- Áp dụng các thuật toán sắp xếp để giải quyết các bài toán sắp xếp đơn giản.
- Áp dụng các thuật toán sắp xếp để giải quyết các bài toán sắp xếp trên danh sách các cấu
trúc theo từng khóa.
- So sánh, đánh giá thời gian chạy của thuật toán với số lượng phần tử lớn.
Thời gian thực hành: từ 120 phút đến 400 phút
TÓM TẮ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 tin lưu giữ tại mỗi phần tử.
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 đến.
Có nhiều giải thuật sắp xếp: Selection sort, Insertion sort, Interchange sort, Bubble sort, Shaker
sort, Binary Insertion sort, Shell sort, Heap sort, Quick sort, Merge sort, Radix sort…
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ắ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ử.
Heap sort
Heap là một dãy các phần tử a
left
, a
left+1
,... , a
right
sao cho: a
i
≥ a
2i
và a
i
≥ a
2i+1,
∀i ∈ [left, right].
(a
i
, a
2i
), (a
i
,a
2i+1
): 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ệ.
Ví dụ 1: Dãy số 5 2 6 4 8 1 được bố trí theo quan hệ so sánh và tạo thành cấu trúc như sau:
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
Ví dụ 2: Loại bỏ 8 ra khỏi cây.
Tài li
ệ
u hư
ớ
ng d
ẫ
n th
ự
c hành môn
Tiến hành nhiều lần việc loại bỏ ph
ầ
∞, khi đó xếp các phần tử theo thứ t
ự
Quick sort
Phân chia dãy thành các đoạn con
như sau:
• Đoạn thứ 2 đã có thứ tự.
• Nếu các đoạn 1 và 3 chỉ
có 1 ph
đã được sắp.
• Ngược lại, nếu các đoạ
n 1 và 3 có nhi
khi các đoạn 1, 3 được sắp.
• Để sắp xếp các đoạ
n 1 và 3, ta l
phương pháp phân hoạ
ch dãy ban
Với x là một phần tử
tùy ý trong dãy và
Merge sort
• Phân hoạch dãy ban đầ
u thành các dãy con
• Làm giảm số dãy con bằ
ng cách tr
của dãy ban đầu.
NỘI DUNG THỰC HÀNH
Cơ bản
Sinh viên đọc kỹ phát biểu bài tậ
p và th
Sử dụng các thuật toán
Selection Sort, Heap Sort, Quick Sort, Merge Sort
số nguyên theo thứ tự tăng dần.
Người dùng sẽ lần lượt nhập chiề
u dài n và các ph
bộ dãy A được lưu trữ trong một m
ả
Lần lượt sử dụng các thuật toán
Selection Sort, Heap Sort, Quick Sort, Merge Sort
A. Chương trình sẽ in các kết quả s
ắ
Phân tích
Selection sort
Phân tích
- Dùng vòng lặp để tìm phầ
n t
- Đảo phần tử đó ra đầu mảng
Chương trình mẫu
(CacThuatToanSapXep)
c hành môn
C
ấ
u trúc d
ữ
li
ệ
u và gi
ả
i thu
ậ
t
ầ
n tử gốc của cây cho đến khi tất cả các phần t
ử
ự
loại bỏ trên cây sẽ có dãy đã sắp xếp.
như sau:
có 1 ph
ần tử thì chúng cũng đã có thứ tự
, khi đó d
n 1 và 3 có nhi
ều hơn 1 phần tử thì dãy con ban
đ
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
ch dãy ban
đầu vừa trình bày …
tùy ý trong dãy và
thường được chọn là vị trí chính giữa dã
y ban đ
u thành các dãy con
liên tiếp mà mỗi dãy con đều đ
ã có th
ng cách tr
ộn từng cặp dãy con của hai dãy phụ
thành m
p và th
ực hiện theo hướng dẫn:
Selection Sort, Heap Sort, Quick Sort, Merge Sort
để sắ
p x
u dài n và các ph
ần tử của dãy các nguyên A từ
ả
ng số nguyên.
Selection Sort, Heap Sort, Quick Sort, Merge Sort
ắ
p xếp theo từng thuật toán ra màn hình.
n t
ử nhỏ nhất trong dãy hiện hành.
(CacThuatToanSapXep)
Trang
2
ử
của cây đều là -
, khi đó d
ãy con ban đầu
đ
ầu chỉ có thứ tự
ng dãy con theo cùng
y ban đ
ầu.
ã có th
ứ tự..
thành m
ột dãy con
p x
ếp một dãy các
bàn phím. Toàn
Selection Sort, Heap Sort, Quick Sort, Merge Sort
để sắp xếp dãy
Tài liệu hướng dẫn thực hành môn Cấu trúc dữ liệu và giải thuật
HCMUS 2010
Trang
3
#include <stdio.h>
void Swap(int &a, int &b)
{
int c = a;
a = b;
b = c;
}
void SelectionSort(int a[],int N ){ //Ghi chú: tại sao không sử dụng kí hiệu & trong hàm này?
int min; //chỉ số phần tử nhỏ nhất trong dãy hiện hành
for (int i=0; i<N-1 ; i++){ //Ghi chu: vòng lặp này dùng để làm gì?
min = i;
for(int j = i+1; j < N ; j++){ //Ghi chu: vòng lặp này dùng để làm gì?
if (a[j] < a[min]){
min = j; //Ghi chu: thao tác này dùng để làm gì?
}
}
if (min != i){
Swap(a[min], a[i]); //Ghi chu: thao tác này dùng để làm gì?
}
}
}
void main()
{
int x[10] = {12, 2, 8, 5, 1, 6, 4, 15}; // khởi tạo các giá trị trong mảng
int n = 8; // số phần tử của mảng
SelectionSort(x, n);
for (int i=0; i<n ; i++){
printf("%d ", x[i]);
}
}
Yêu cầu
1. Biên dịch đoạn chương trình nêu trên.
2. Tại sao trong hàm SelectionSort, vòng lặp thứ nhất có điều kiện là i < N-1?
3. Trả lời các dòng lệnh có yêu cầu ghi chú.
4. Sửa lại chương trình để nhập dãy số nguyên từ file input.txt có nội dung như sau:
5 1 2 3 8 6 23 10
Sau đó dùng thuật toán Selection Sort sắp xếp dãy số nguyên trên tăng dần.
5. Sửa hàm SelectionSort trên để sắp xếp dãy số nguyên ở câu 4 giảm dần.
Tài liệu hướng dẫn thực hành môn Cấu trúc dữ liệu và giải thuật
HCMUS 2010
Trang
4
Heap Sort
Phân tích
- Hiệu chỉnh dãy số ban đầu về dạng heap được định nghĩa trên mảng (hay list).
- Áp dụng thuật toán Heap Sort trên cấu trúc này.
Chương trình mẫu
void Shift (int a[], int left, int right){
int x, curr, joint;
curr = left; joint =2*curr+1; // a
joint
: Phần tử liên đới
x = a[curr];
while (joint <= right){
if (joint < right){ // Ghi chú: điều kiện này có ý nghĩa gì?
if (a[joint] < a[joint+1]){
joint = joint+1;
}
}
if (a[joint]<x){
break; // Thỏa quan hệ liên đới
}
a[curr] = a[joint];
curr = joint; // Xét khả năng hiệu chỉnh lan truyền
joint = 2*curr+1;
}
a[curr] = x;
}
Yêu cầu
1. Trả lời các dòng lệnh có yêu cầu ghi chú.
2. Cho biết chức năng của đoạn chương trình trên.
3. Viết hàm void CreateHeap(int a[], int N); để chuyển đổi dãy a
0
, a
1
, …, a
N-1
thành heap.
Gợi ý: Sử dụng hàm Shift bên trên với left hiện hành là phần tử ở giữa dãy ((N-1)/2). Lặp lại
quá trình trên với left giảm dần về đầu dãy.
4. Viết hàm void HeapSort(int a[], int N); để sắp xếp một dãy số nguyên tăng dần.
Gợi ý: Giai đoạn 1: Hiệu chỉnh dãy ban đầu thành heap
Giai đoạn 2: Sắp xếp dãy số dựa trên heap.
• Xét dãy hiện hành là dãy nhập
• Hoán vị phần tử lớn nhất (a
0
) về vị trí cuối.
• Xét dãy hiện hành loại đã trừ phần tử cuối.
• Hiệu chỉnh lại dãy hiện hành thành heap
• Lặp lại quá trình trên tới hết dãy ban đầu.
5. Bổ sung các hàm trên vào chương trình mẫu (CacThuatToanSapXep) đồng thời thay đổi hàm
main và file input để sắp xếp dãy số nguyên sau tăng dần:
Tài liệu hướng dẫn thực hành môn Cấu trúc dữ liệu và giải thuật
HCMUS 2010
Trang
5
44 55 12 42 94 18 6 67
6. Viết lại thuật toán Heap Sort để sắp xếp dãy số ở câu 3 giảm dần.
Quick Sort
Phân tích
- Chọn phần tử làm mốc.
- Tiến hành phân hoạch dãy ban đầu thành 3 phần a
k
<x (1), a
k
=x (2) và a
k
>x (3) theo thứ tự.
- Lặp lại thao tác trên trên 2 đoạn (1) và (3)
Chương trình mẫu
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 <= j) {
Swap(a[i], a[j]);
i++ ;
j--;
}
}
QuickSort(a, left, j);
QuickSort(a, i, right);
}
Yêu cầu
1. Bổ sung các hàm trên vào chương trình mẫu (CacThuatToanSapXep) đồng thời thay đổi hàm
main và file input để sắp xếp dãy số nguyên sau tăng dần:
42 23 74 11 65 58 94 36 99 87
2. Sửa lại chương trình để đếm số phép gán và số phép so sánh sự dụng trong hàm QuickSort.
Tài liệu hướng dẫn thực hành môn Cấu trúc dữ liệu và giải thuật
HCMUS 2010
Trang
6
Merge Sort
Phân tích
- 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.
- Trộn mảng b và mảng c vào mảng a.
- Lặp lại quá trình trên với k tăng gấp đôi đến khi k lớn hơn hay bằng chiều dài của dãy.
Chương trình mẫu
int b[MAX], c[MAX], nb, nc;
/
//
/ Ghi chú: 2 mảng này dùng để làm gì?
void Distribute(int a[], int N, int &nb, int &nc, int k){
int i, pa, pb, pc; //Ghi chú: các biến này có ý nghĩa gì?
pa = pb = pc = 0;
while (pa < N){
for (i=0; (pa<N) && (i<k); i++, pa++, pb++){ //Ghi chú: vòng lặp này có ý nghĩa gì?
b[pb] = a[pa];
}
for (i=0; (pa<N) && (i<k); i++, pa++, pc++){ //Ghi chú: vòng lặp này có ý nghĩa gì?
c[pc] = a[pa];
}
}
nb = pb; nc = pc;
}
void Merge(int a[], int nb, int nc, int k){
int pa, pb, pc;
pa = pb = pc = 0;
while ((pb < nb) && (pc < nc)){
MergeSubarr(a, nb, nc, pa, pb, pc, k);
}
while (pb < nb){
a[pa ++] = b[pb ++]; //Ghi chú: câu lệnh này có ý nghĩa gì?
}
while (pc < nc){
a[pa ++] = c[pc ++]; //Ghi chú: câu lệnh này có ý nghĩa gì?
}
}
có thể bạn quan tâm
Khái niệm phân tập và kỹ thuật phân tập đa người dùng, kỹ thuật OFDM,...
62
817
599
Kỹ thuật
62
(New)
Nghiên cứu về chữ kí số và ứng dụng trong hóa đơn điện tử tại VNPT Hà...
23
726
481
Thạc sĩ cao học
23
(New)
Một số thuật toán cơ bản trong Pascal và ứng dụng
57
681
296
Cơ sở dữ liệu
57
(New)
Nghiên cứu, đánh giá các giải thuật đối sánh chuỗi. Trên cơ sở đó lựa...
25
1.075
555
Thạc sĩ cao học
25
(New)
Luận văn thạc sĩ: Một số thuật toán mã hóa khác ứng dụng trong bảo mật...
26
1.165
296
Thạc sĩ cao học
26
(New)
Kỹ thuật giải thuật trong lập trình và ứng dụng
0
760
317
Lập trình
(New)
Tìm hiểu về thuật toán và thuật giải
97
2.150
442
Cơ sở dữ liệu
97
(New)
THIẾT KẾ HỆ TRUYỀN ĐỘNG ĐIỆN VÀ TRANG BỊ ĐIỆN TRẠM LẠNH CÔNG NGHIỆP VÀ...
85
1.076
316
Kỹ thuật
85
(New)
thông tin tài liệu
Một số bài tập ứng dụng thuật toán sắp xếp
Mở rộng để xem thêm
từ khóa liên quan
tài liệu mới trong mục này
tài liệu hot trong mục này
tài liệu giúp tôi
Nếu bạn không tìm thấy tài liệu mình cần có thể gửi yêu cầu ở đây để chúng tôi tìm giúp bạn!
xem nhiều trong tuần
Giáo trình Quản trị học của Đại học kinh tế quốc dân
Tâm lý xã hội VÀ Hệ tư tưởng
Mẫu slide chủ đề âm nhạc
4 đề thi học sinh giỏi Toán lớp 2, có đáp án kèm theo
Tham khảo 12 bài tập nguyên lý thống kê có lời giải
Các hiệu ứng HTML cho trang web
yêu cầu tài liệu
Giúp bạn tìm tài liệu chưa có
×
