›
›

Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 5: Sắp xếp - Nguyễn Khánh Phương

Download
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI  
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG  
Cấu trúc dữ liệu và giải thuật  
Nguyễn Khánh Phương  
Computer Science department  
School of Information and Communication technology  
E-mail: [email protected].vn  
Nội dung khóa học  
Chương 1. Các khái niệm cơ bản  
Chương 2. Các sơ đồ thuật toán  
Chương 3. Các cấu trúc dữ liệu cơ bản  
Chương 4. Cây  
Chương 5. Sắp xếp  
Chương 6. Tìm kiếm  
Chương 7. Đồ thị  
2
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI  
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG  
Chương 5. Sắp xếp  
Nguyễn Khánh Phương  
Computer Science department  
School of Information and Communication technology  
E-mail: [email protected].vn  
Bài toán sắp xếp  
• Sắp xếp (Sorting) là quá 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.  
• Dữ liệu cần sắp xếp có thể là:  
– Số nguyên/thực.. (integers/float)  
– Xâu kí tự (character strings)  
– …  
• 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 khoá.  
– Ví dụ: khóa là tong = toan + ly + hoa  
typedef struct{  
char *ma;  
struct{  
float toan, ly, hoa, tong;  
} DT;  
}thisinh;  
typedef struct node{  
thisinh data;  
4
struct node* next;  
}node;  
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 toàn bộ vào bộ nhớ trong của máy tính  
• Ví dụ:  
– insertion sort (sắp xếp chèn), selection sort (sắp xếp lựa chọn), bubble sort (sắp xếp nổi bọt)  
– quick sort (sắp xếp nhanh), merge sort (sắp xếp trộn), heap sort (sắp xếp vun đống), sample  
sort (sắp xếp dựa mẫu), shell sort (vỏ sò)  
Sắp xếp ngoài (external sort):  
• Họ dữ liệu không thể cùng lúc đưa toàn bộ vào bộ nhớ trong, nhưng có thể đọc vào từng bộ phận từ  
bộ nhớ ngoài  
• Ví dụ:Poly-phase mergesort (trộn nhiều đoạn), cascade-merge (thác nước), oscillating sort (dao  
động)  
Sắp xếp song song (Parallel sort):  
• Bitonic sort, Batcher even-odd sort.  
• Smooth sort, cube sort, column sort.  
• GPU sort.  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
5
Các đặc trưng của một thuật toán sắp xếp  
• Tại chỗ (in place): nếu không gian nhớ phụ mà thuật toán đòi hỏi là O(1), nghĩa là  
bị chặn bởi hằng số không phụ thuộc vào độ dài của dãy cần sắp xếp.  
• Ổn định (stable): Nếu các phần tử có cùng giá trị vẫn giữ nguyên thứ tự tương đối  
của chúng như trước khi sắp xếp.  
10  
20  
20  
30  
10  
Trước sắp xếp  
Sắp xếp này ổn định vì thứ tự của các quả bóng có giá trị bằng  
nhau là không thay đổi trước và sau khi sắp xếp:  
• Quả bóng màu xanh với giá trị 10 đứng trước quả bóng màu  
cam giá trị 10.  
• Tương tự với 2 quả bóng xanh và cam cùng giá trị 20  
10  
10  
20  
20  
30  
Sau sắp xếp  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
6
Bài toán sắp xếp  
• Có hai phép toá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)  
void swap( datatype *a, datatype *b){  
datatype *temp = *a; //datatype-kiểu dữ liệu của phần tử  
*a = *b;  
*b = *temp;  
}
– So sánh: 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 trái lại.  
• Phân tích thuật toán sắp xếp: thông thường, các thuật toán sẽ sử dụng phép toán  
so sánh để xác định thứ tự giữa hai phần tử rồi thực hiện đổi chỗ nếu cần.  
Khi phân tích thuật toán sắp xếp, ta sẽ chỉ cần đếm số phép toán so sánh và số lần  
dịch chuyển các phần tử (bỏ qua các phép toán khác không ảnh hưởng đến kết quả).  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
7
Bài toán sắp xếp  
• 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ử  
được gọi là thuật toán sử dụng phép so sánh (Comparison-based sorting algorithm).  
• Nếu có những thông tin bổ sung về dữ liệu đầu vào, ví dụ như:  
– Các số nguyên nằm trong khoảng [0..k] trong đó k = O(n)  
– Các số thực phân bố đều trong khoảng [0, 1)  
ta sẽ có thuật toán tốt hơn thuật toán sắp xếp chỉ dựa vào phép so sánh.  
(Thuật toán thời gian tuyến tính: sắp xếp đếm (couting-sort), sắp xếp theo cơ số (radix-  
sort), sắp xếp đóng gói (bucket-sort))  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
8
Các thuật toán sắp xếp  
Khi so sánh các thuật toán, thông thường quan tâm đến:  
• Thời gian chạy. Đối với các dữ liệu rất lớn, các thuật toán không hiệu quả  
sẽ chạy rất chậm và không thể ứng dụng trong thực tế.  
• Bộ nhớ. Các thuật toán nhanh đòi hỏi đệ quy sẽ có thể phải tạo ra các bản  
copy của dữ liệu đang xử lí. Với những hệ thống mà bộ nhớ có giới hạn (ví  
dụ embedded system), một vài thuật toán sẽ không thể chạy được.  
• Độ ổn định (stability). Độ ổn định được định nghĩa dựa trên điều gì sẽ xảy  
ra với các phần tử có giá trị giống nhau.  
– Đối với thuật toán sắp xếp ổn định, các phần tử với giá trị bằng nhau sẽ  
giữ nguyên thứ tự trong mảng trước và sau khi sắp xếp.  
– Đối với thuật toán sắp xếp không ổn định, các phần tử có giá trị bằng  
nhau sẽ có thể có thứ tự bất kỳ.  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
9
Tiêu chí lựa chọn giải thuật  
Nhiều yếu tố ảnh hưởng:  
• Ổn định  
• Danh sách liên kết hay mảng  
• Đặc trưng của dữ liệu cần sắp xếp:  
– Nhiều khóa ?  
– Các khóa là phân biệt ?  
– Nhiều dạng khóa ?  
– Kích thước bản ghi lớn hay nhỏ ?  
– Dữ liệu được sắp xếp ngẫu nhiên?  
Không thể bao phủ tất cả các yếu tố  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
Nội dung  
1. Sắp xếp chèn (Insertion sort)  
2. Sắp xếp chọn (Selection sort)  
3. Sắp xếp nổi bọt (Bubble sort)  
4. Sắp xếp trộn (Merge sort)  
5. Sắp xếp nhanh (Quick sort)  
6. Sắp xếp vun đống (Heap sort)  
1. Sắp xếp chèn (Insertion sort)  
Phỏng theo cách làm của người chơi  
bài khi cần "chèn" thêm một con bài  
vào bộ bài đã được sắp xếp trên tay.  
Để chèn 12, ta cần tạo chỗ cho nó bởi  
việc dịch chuyển đầu tiên là 36 và sau  
đó là 24.  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
12  
1. Sắp xếp chèn (Insertion sort)  
Phỏng theo cách làm của người  
chơi bài khi cần "chèn" thêm một  
con bài vào bộ bài đã được sắp  
xếp trên tay.  
Để chèn 12, ta cần tạo chỗ cho nó  
bởi việc dịch chuyển đầu tiên là 36  
và sau đó là 24.  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
13  
1. Sắp xếp chèn (Insertion sort)  
Phỏng theo cách làm của người  
chơi bài khi cần "chèn" thêm một  
con bài vào bộ bài đã được sắp  
xếp trên tay.  
Để chèn 12, ta cần tạo chỗ cho nó  
bởi việc dịch chuyển đầu tiên là 36  
và sau đó là 24.  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
14  
1. Sắp xếp chèn (Insertion sort)  
Phỏng theo cách làm của người  
chơi bài khi cần "chèn" thêm một  
con bài vào bộ bài đã được sắp  
xếp trên tay.  
Để chèn 12, ta cần tạo chỗ cho nó  
bởi việc dịch chuyển đầu tiên là 36  
và sau đó là 24.  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
15  
1. Sắp xếp chèn (Insertion sort)  
Thuật toán:  
• Mảng cần sắp xếp được chia làm 2 phần, sorted và unsorted:  
– Những phần tử nằm trong phần sorted: đã được sắp xếp  
– Những phần tử nằm trong phần unsorted: chưa được sắp xếp  
• Mỗi bước lặp: phần tử đầu tiên thuộc phần unsorted sẽ được chuyển sang phần  
sorted.  
Mảng có n phần tử sẽ cần n-1 bước lặp để sắp xếp xong  
16  
1. Sắp xếp chèn (Insertion sort)  
• Thuật toán:  
– Tại bước k =1, 2, ..., n:  
đưa phần tử thứ k trong mảng đã cho vào đúng vị trí trong dãy gồm k phần  
tử đầu tiên.  
Tại mỗi bước lặp k, có thể cần nhiều hơn một lần hoán đổi vị trí các phần tử để có thể đưa phần tử thứ  
k về đúng vị trí của nó trong dãy cần sắp xếp  
Bước lặp k: liên tục đổi chỗ phần tử thứ k với phần tử kề bên trái nó (phần tử ngay  
trước) chừng nào phần tử thứ k còn nhỏ hơn phần tử đó  
Tính chất: Sau bước lặp k, k phần tử đầu tiên a[1], a[2], …, a[k] đã được sắp  
17  
thứ tự.  
Cài đặt: Insertion Sort Algorithm  
k=5: tìm vị trí đúng cho a[5]=14  
void insertionSort(int a[], int size);  
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]  
13  
17  
20  
28  
23  
15  
temp = 14  
13  
17  
17  
17  
20  
20  
17  
28  
20  
20  
42  
28  
28  
28  
42  
42  
42  
42  
23  
23  
23  
23  
15  
15  
15  
15  
13  
13  
for (int k = 1; k < size; k++) {  
int temp = a[k];  
int pos = k;  
/* bước lặp k: liên tục đổi chỗ phần tử thứ k với phần tử kề bên  
trái nó chừng nào phần tử thứ k còn nhỏ hơn phần tử đó */  
while (pos > 0 && a[pos-1] > temp) {  
a[pos] = a[pos–1];  
pos--;  
} // end while  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
}
Cài đặt: Insertion Sort Algorithm  
k=5: tìm vị trí đúng cho a[5]=14  
void insertionSort(int a[], int size);  
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]  
13  
17  
20  
28  
23  
15  
temp = 14  
13  
17  
17  
17  
20  
20  
17  
28  
20  
20  
42  
28  
28  
28  
42  
42  
42  
42  
23  
23  
23  
23  
15  
15  
15  
15  
13  
13  
13  
14  
17  
20  
28  
42  
23  
15  
for (int k = 1; k < size; k++) {  
int temp = a[k];  
int pos = k;  
/* bước lặp k: liên tục đổi chỗ phần tử thứ k với phần tử kề bên  
trái nó chừng nào phần tử thứ k còn nhỏ hơn phần tử đó */  
while (pos > 0 && a[pos-1] > temp) {  
a[pos] = a[pos–1];  
pos--;  
} // end while  
// Chèn giá trị temp (=a[k]) vào đúng vị trí  
a[pos] = temp;  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
}
Cài đặt: Insertion Sort Algorithm  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
20  
Tải về để xem bản đầy đủ
pdf 181 trang yennguyen 17000 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 5: Sắp xếp - Nguyễn Khánh Phương", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_cau_truc_du_lieu_va_thuat_toan_chuong_5_sap_xep_ng.pdf