Bài giảng Kỹ thuật lập trình - Bài 10: Tìm kiếm sắp xếp - Lê Gia Minh

Nội dung text: Bài giảng Kỹ thuật lập trình - Bài 10: Tìm kiếm sắp xếp - Lê Gia Minh

1. Trang 0 l Selection sort : chọn trực tiếp Interchange sort - đổi chỗ trực tiếp Insertion sort - chèn trực tiếp Bubble sort - nổi bọt Shaker sort - nổi bọt cải tiến Heap sort - sắp xếp vun đống Shell sort - sắp xếp: độ dài bước giảm dần Merge sort - sắp xếp trộn Quick sort - (ko bít dịch ) 1
2. l 1> Sắp xếp nổi bọt Sắp xếp nổi bọt (bubble sort) là phương pháp sắp xếp đơn giản, dễ hiểu thường được dạy trong khoa học máy tính. Giải thuật bắt đầu từ đầu của tập dữ liệu. Nó so sánh hai phần tử đầu, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ chúng cho nhau. Tiếp tục làm như vậy với cặp phần tử tiếp theo cho đến cuối tập hợp dữ liệu. Sau đó nó quay lại với hai phần tử đầu cho đến khi không còn cần phải đổi chỗ nữa. 2
3. l 2> Sắp xếp chèn Sắp xếp chèn (insertion sort) là một thuật toán sắp xếp rất hiệu quả với các danh sách nhỏ. Nó lần lượt lấy các phần tử của danh sách chèn vào vị trí thích hợp trong một danh sách mới đã được sắp. 3
4. l 3> Sắp xếp chọn Săp xếp chọn (select sort) là phương pháp sắp xếp bằng cách chọn phần tử bé nhất xếp vào vị trí thứ nhất, tương tự với các phần tử nhỏ thứ hai, thứ ba, cấu trúc thuật toán 4
5. l 4> Sắp xếp trộn Sắp xếp trộn (merge sort) cùng với sắp xếp nhanh là hai thuật toán sắp xếp dựa vào tư tưởng "chia để trị" (divide and conquer). Thủ tục cơ bản là việc trộn hai danh sách đã được sắp xếp vào một danh sách mới theo thứ tự. Nó có thể bắt đầu trộn bằng cách so sánh hai phần tử một (chẳng hạn phần tử thứ nhất với phần tử thứ hai, sau đó thứ ba với thứ tư ) và sau khi kết thúc bước 1 nó chuyển sang bước 2. Ở bước 2 nó trộn các danh sách hai phần tử thành các danh sách bốn phần tử. Cứ như vậy cho đến khi hai danh sách cuối cùng được trộn thành một. 5
6. l 5> Sắp xếp vun đống Sắp xếp vun đống (heapsort) là một trong các phương pháp sắp xếp chọn. Ở mỗi bươc của sắp xếp chọn ta chọn phần tử lớn nhất (hoặc nhỏ nhất) đặt vào cuối (hoặc đầu) danh sách, sau đó tiếp tục với phần còn lại của danh sách. Thông thường sắp xếp chọn chạy trong thời gian O(n2). Nhưng heapsort đã giảm độ phức tạp này bằng cách sử dụng một cấu trúc dữ liệu đặc biệt được gọi là đống (heap). Đống là cây nhị phân mà trọng số ở mỗi đỉnh cha lớn hơn hoặc bằng trọng số các đỉnh con của nó. Một khi danh sách dữ liệu đã được vun thành đống, gốc của nó là phần tử lớn nhất, thuật toán sẽ giải phóng nó khỏi đống để đặt vào cuối danh sách. Sắp xếp vun đống chạy trong thời gian O(n log n). 6
7. l 6> Sắp xếp nhanh Sắp xếp nhanh (quicksort) là một thuật toán theo tư tưởng chia để trị, nó dựa trên thủ tục phân chia như sau: để chia một dãy ta chọn một phần tử được gọi là "chốt" (pivot), chuyển tất cả các phần tử nhỏ hơn chốt về trước chốt, chuyển tất cả các phần tử lớn hơn chốt về sau nó. Thủ tục này có thể thực hiện trong thời gian tuyến tính. Tiếp tục phân chia các dãy con đó như trên cho đến khi các dãy con chỉ còn một phần tử. 7
8. l Điểm khác biệt giữa sắp xếp nhanh và sắp xếp trộn là trong sắp xếp trộn việc xác định thứ tự được xác định khi "trộn", tức là trong khâu tổng hợp lời giải sau khi các bài toán con đã được giải, còn sắp xếp nhanh đã quan tâm đến thứ tự các phần tử khi phân chia một danh sách thành hai danh sách con. Ngoài ra còn nhiều giải thuật sắp xếp khác, trong đó nhiều giải thuật sắp xếp được cải tiến từ các giải thuật trên. Trong sáu giải thuật liệt kê trên, ta thường coi các giải thuật chèn, chọn, nổi bọt là các giải thuật cơ bản, độ phức tạp trong trường hợp trung bình của chúng là O(n2). Ba giải thuật còn lại thường được coi là giải thuật cao cấp, độ phức tạp tính toán trung bình của chúng là n.lnn. 8
9. Kỹ thuật tìm kiếm và Sắp xếp
10. Nội dung l Độ phức tạp thuật toán l Giải thuật tìm kiếm tuyến tính. l Giải thuật tìm kiếm nhị phân. l Giải thích được một số thuật toán sắp thứ tự: Selection sort, Bubble sort, Insertion sort 10
11. Lựa chọn một giải thuật tốt l Giải thuật đúng đắn ¡ Test trên nhiều tập dữ liệu ¡ Chính xác là cần chứng minh bằng toán học l Giải thuật đơn giản l Giải thuật thực hiện nhanh ¡ Tập dữ liệu đầu vào mà khá lớn phải xem xét yếu tố này. 11
12. Thời gian thực hiện của giải thuật l Lập trình và đo lường thời gian thực hiện trên một máy tính cụ thể và với một tập dữ liệu cụ thể. Rất khó đo lường để kết luận giải thuật nào tốt hơn. l Thời gian thực hiện của một chương trình là một hàm phụ thuộc vào kích thước của dữ liệu đầu vào, ký hiệu T(n) 12
13. Thời gian thực hiện trong trường hợp xấu nhất l Thời gian chạy phụ thuộc vào : ¡ Kích thước dữ liệu ¡ Tính chất của dữ liệu l T(n) là thời gian thực hiện chương trình trong trường hợp xấu nhất. l Ta ký hiệu độ phức tạp thuật toán là O ¡ Thí dụ : O(n2) sẽ chạy chậm hơn O(n) ¡ Có thể nói : T(n) = O(f(n)) 13
14. Một số phương pháp xác định O l Tuần tự : Quy tắc Cộng ¡ statement 1; ¡ statement 2; ¡ ¡ statement k; total time = time(statement 1) + time(statement 2) + + time(statement k) Nếu mỗi statement là một lện đơn giản: gán hay so sánh thì O(1) 14
15. Big O l if-then-else statements ¡ if (cond) { sequence of statements 1 } ¡ else { sequence of statements 2 } l Chỉ có statement 1 hay statement 2 chạy l max(time(sequence 1), time(sequence 2)). 15
16. Big O for loops l for (i = 0; i < N; i++) { sequence of statements } l N * O(1) O(n) Nested loops l for (i = 0; i < N; i++) { for (j = 0; j < M; j++) { sequence of statements } } O(N*M) 16
17. Demo l for(int I = 0 ; i<3 ; i++) l for(int j = 0 ; j<n ; j++) l sum++ ; l for(i = 0 ; i<n*n ; i++) sum++; 17
18. Tìm Kiếm l Hầu hết các dữ liệu của các bài toán là nhóm trị mà một phần tử có thể có cấu trúc mô tả khác nhau . l Nhu cầu tìm kiếm/sắp xếp thông tin là nhu cầu tự nhiên của con người. 18
19. Tìm Kiếm(tt) l Các điều kiện của qúa trình tìm kiếm: ¡ Đã có một nhóm trị. ¡ Một chút thông tin đã biết về nội dung cần tìm (dữ liệu khóa- Key ). l Thí dụ 1: Lấy lý lịch (tìm) của nhân viên có mã số “NV008” l Thí dụ 2: Lấy lý lịch (tìm) của nhân viên có tên “Nguyễn Văn X”. l Khi Key tìm kiếm là duy nhất, qúa trình tìm kiếm cho tối đa một kết qủa . l Khi Key tìm kiếm không duy nhất, qúa trình tìm kiếm có thể cho nhiều kết qủa (thí dụ , trong tổ chức có thể có nhiều người tên “Nguyễn Văn X”). 19
20. Tìm Kiếm(tt) l Kết qủa tìm kiếm là vị trí có thông tin cần tìm. l Vấn đề mô tả kết qủa của qúa trình tìm kiếm : ¡ Nếu chỉ số nhận diện phần tử là 1 số nguyên: thì kết qủa là 1 số nguyên ( trị -1 mô tả cho kết qủa “không tìm thấy”, kết quả là tập các số int nếu là tìm kiếm đa trị). ¡ Nếu chỉ số nhận diện phần tử là 1 pointer: thì kết qủa là 1 pointer ( pointer NULL mô tả cho kết qủa “không tìm thấy”, kết qủa là tập các pointer nếu là tìm kiếm đa trị) l Đếm số lần xuất hiện của một dữ liệu là một “biến thể” của tác vụ tìm kiếm. 20
21. Kỹ thuật tìm kiếm l Bài toán tìm kiếm tổng quát: Cho tập record R0, R1, R2, , Rn-1. Mỗi Ri được kết hợp với một khóa Ki (field thứ i của mô tả record). Tìm (các) vị trí record có khoá là X đã biết. l Hai thuật toán tìm kiếm: ¡ Tìm kiếm tuần tự (tuyến tính, Sequential Searching). ¡ Tìm kiếm nhị phân (Binary Searching). 21
22. Kỹ thuật tìm kiếm tuần tự l Bài toán: Có mảng a chứa 6 số int. Tìm vị trí đầu có mặt trị x=3 trong mảng này. Phát hiện a[4]=x , ngưng tìm , Kết qủa: 4 l Trường hợp tốt nhất (x=8): Chỉ tốn 1 lần so sánh. l Trường hợp xấu nhất: x ở cuối mảng hoặc x không có trong mảng: Tốn 6 lần so sánh. l Độ phức tạp O(n) l Kỹ thuật cổ điển nhưng hay dùng. 22
23. Kỹ thuật tìm kiếm (tt) l Thuật toán chung cho việc tìm tới Đi từ phần tử đầu mảng a đến phần tử cuối Nếu (a[i].K == x) return i; return -1; // trường hợp không tìm thấy l Thuật toán chung cho việc tìm lui Đi ngược từ phần tử cuối mảng a đến phần tử đầu Nếu (a[i].K == x) return i; return -1; // trường hợp không tìm thấy 23
24. Cài đặt l Tìm vị trí đầu có int x trong mảng int*a đang có int n phần tử int IndexOf (int x, int*a, int n) { for (register int i = 0; i =0 ; i ) if (a[i]==x) return i; return -1; } 24
25. Cài đặt(tt) l Mô tả 1 nhân viên: Employee: l Cài đặt: Tìm vị trí đầu có nhân viên mang mã số aCode trong danh sách List đang có int n nhân viên struct Employee { char Code[6], Name[40], long Salary; }; int Search (char* aCode , Employee List[], int n) { for (register int i=0; i<n; ++i) if (strcmp(List[i].Code, aCode)==0) return i; return -1; } 25
26. Cài đặt(tt) l Đếm số lần có int x trong mảng int *a, int n int Count (int x, int*a, int n) { register int Result=0; for (register int i=0; i<n; ++i) if (a[i]== x) Result++; return Result; } Bài tập làm tại chỗ: Đếm số nhân viên có lương trên 1000000 26
27. Cài đặt(tt) l Đếm số lần có int x trong ma trận int m, có int d, c dóng cột int Count (int x, int m, int d, int c) { register int Result=0 , i, j; for (i=0; i<d; i++) for (j=0; j<c; j++) if (m[i][j]== x) Result++; return Result; } 27
28. Search Algorithm- Tuyến tính l Vét cạn(Exhautive) – đơn giản for(I = 1 to N) if (A[i] == X ) return i ; l Tìm kiếm có phần tử cầm canh(sentinel) Làm giảm số lần so sánh trong vòng lặp bằng cách thêm phần tử lính canh H K A I S D E A G S Phần tử cần28 tìm S N
29. Compare Sentinel and Not START START 1 i 1 i No Yes= i Not Found A[i]== X (i+1) i = <> No (i+1) i N+1 i < N N*2 lần so Yes lần so sánh Found Found Not Found sánh 29 END END
30. Bài tập l Viết chương trình: Nhập 1 ma trận các số int, Nhập trị int x. Hãy cho biết x xuất hiện trong ma trận bao nhiều lần, Hãy cho biết dòng cột đầu tiên có x. l Viết chương trình nhập 1 danh sách nhân viên . Hãy xuất danh sách của các nhân viên có Salary trên 1000000 30
31. Kỹ thuật tìm kiếm nhị phân l Nhóm trị nguồn đã có thứ tự, giả sử tăng dần. l Tại 1 thời điểm giảm ½ số phần tử trong tập trị cần tìm. l Thí dụ bên đây chỉ tốn 4 lần so sánh đã xác định được kết qủa là 7 31
32. Kỹ thuật tìm kiếm nhị phân l Thí dụ bên đây chỉ mất 5 lần đã xác định được x không có trong mảng 32
33. Kỹ thuật tìm kiếm nhị phân l Số lần so sánh tối đa log2n + 1 l Nếu n = 2m thì l Lần Số phần tử được xét Số phép so sánh l 1 2m 1 l 2 2m-1 1 l 3 2m-2 1 l 4 2m-3 1 l i 2m-i+1 1 l m+1 2m-m = 1 1 l Độ phức tạp của tìm kiếm nhị phân O (log2n) 33
34. Cài đặt Kỹ thuật tìm kiếm nhị phân l int BinarySearch (int x, int*a, int n) { register int i=0,j=n-1,c; while (i<j) { c= (i+j)/2; // lấy chỉ số giữa tập trị if (a[c]==x) return c; else if (a[c] <x) i= c+1; else j = c-1; } return -1; // cho trường hợp tìm không thấy } Bài tập: Viết hàm tìm một nhân viên với mã số đã biết. Biết rằng danh sách nhân viên đã có thứ tự theo mã số tăng dần. 34
35. Tóm tắt về Kỹ thuật tìm kiếm l Tìm kiếm tuần tự được dùng khi tập trị không có thứ tự. l Tìm kiếm nhị phân thường được dùng khi tập trị đã có thứ tự. l Có một chút khác biệt trong giải thuật tìm kiếm nhị phân trên tập trị có thứ tự giảm dần (bài tập). l Độ phức tạp của tìm kiếm tuần tự: O(n) l Độ phức tạp của tìm kiếm nhị phân: O(log2n) 35
36. Một số kỹ thuật sắp thứ tự l Có nhiều giải thuật sắp thứ tự. l Các yếu tố đánh gía một giải thuật sắp xếp: ¡ Dung lượng bộ nhớ bị chiếm dụng. ¡ Thời gian thực thi giải thuật trong các tình huống: xấu nhất / tốt nhất / trung bình l Cách đánh gía thường dùng: C số lần so sánh, M: số lần dịch chuyển dữ liệu l Các giải thuật được đề cập ¡ Giải thuật Selection sort ¡ Giải thuật Bubble sort ¡ Giải thuật Insertion Sort l Các giải thuật khác được đề cập trong môn Cấu trúc dữ liệu. l Các giải thuật được đề cập theo hướng sắp xếp khóa tăng dần. 36
37. Selection Sort(Sắp xếp Chọn) l Ý tưởng : ¡ Duyệt nhiều lần qua danh sách , mỗi lần duyệt sẽ tìm ra phần tử nhỏ nhất (lớn nhất) và chuyển đến đúng vị trí của nó. l Độ phức tạp : ¡ O(n2) l Thí dụ : ¡ 67 , 33 , 21 , 84 , 49 , 50 , 75 ¡ 67 , 33 , 21 , 84 , 49 , 50 , 75 ¡ 21 , 33 , 67, 84 , 49 , 50 , 75 ¡ 21 , 33 , 67 , 84 , 49 , 50 , 75 làm tiếp cho phần còn lại 37
38. Giải thuật Selection Sort l Sử dụng giải thuật tìm kiếm trong việc sắp xếp. Số phép so sánh: Cavg = n(n-1)/2 38
39. Selection Sort- Cài đặt l Sắp xếp mảng int*a, int n tăng dần void SelectAscSort ( int * a, int n) { int i, j, minIndex, t ; for ( i = 0; i a[j] ) minIndex=j; t= a[i]; // hoán vị a[i] với a [minIndex] a[i] = a[minIndex]; a[minIndex] = t ; } } 39
40. BubleSort( Nổi bọt ) l Ý tưởng : ¡ Duyệt nhiều lần qua danh sách, so sánh và hóan vị những cặp phần tử kế cận nhau, sau một lần duyệt thì phần tử nhỏ nhất sẽ “nổi lên trên” l Thí dụ : 4 , 2 , 6 , 9 ,3 4 , 2 , 6 , 3 , 9 4 , 2 , 3 , 6 , 9 4 , 2 , 3 , 6 , 9 2 , 4 , 6 , 3 , 9 40
41. Giải thuật Bubble Sort l Cho phần tử mang trị nhỏ trồi lên phía trên 41
42. Cài đặt giải thuật Bubble Sort l Sắp xếp mảng int*a, int n tăng dần void BubbleAscSort (int*a, int n ) { int i,j, t ; for (i=0; i i ; j ) if (a[j] < a[j-1]) Bài tập: { t = a[j]; Viết hàm sắp xếp mảng số thực a[j]= a[j-1]; giảm dần bằng giải thuật Bubble sort a[j-1] = t; } } 42
43. Độ phức tạp O(n2) – Bubble Sort l Trường hợp xấu nhất khi các phần tử có thứ tự ngược. Lần đầu có (n-1) lần so sánh và hóan vị với danh sách có n phần tử - Lần kế có (n-2) lần so sánh và hóan vị với danh sách có (n-1) phần tử l Vậy có tất cả : (n-1) + (n-2) + + 2 + 1 = n(n-1)/2 43
44. Giải thuật Insertion Sort l Phép sắp xếp tương tự như xếp sách theo độ cao hay xếp bài. l Lấy 1 phần tử phía sau chèn vào nhóm phần tử đã có thứ tự trước đó. 44
45. Cài đặt giải thuật Insertion Sort 45
46. Độ phức tạp O(n2) - InsertionSort l Trường hợp xấu nhất khi danh sách bị sắp thứ tự ngược. l Việc chèn A[1] đòi hỏi so sánh với A[0] l Việc chèn A[2] so sánh với A[0] , A[1] l l 1 + 2 + . + n-1 = n(n-1)/2 O(n2) 46
47. Tóm tắt Tìm kiếm là qua trình dựa trên một chút thông tin (khoá tìm kiếm) đã có để xác định vị trí có thông tin cần tìm trong một nhóm trị. Hai giải thuật tìm kiếm: Tìm kiếm tuyến tính và tìm kiếm nhị phân. Tìm kiếm tuần tự có thể dùng cho một nhóm trị bất kỳ. Tìm kiếm nhị phân chỉ dùng cho nhóm trị đã có thứ tự. 47
48. Tóm tắt l Sắp xếp là qúa trình tái bố trí các phần tử trong một nhóm trị theo một cơ chế so sánh nào đó. l Cơ chế selection sort: tìm 1 trị nhỏ nhất trong nhóm trị còn phải sắp xếp để đưa về đầu nhóm này. l Cơ chế Bubble sort: Hoán chuyển dần các trị nhỏ ở dưới lên phía trên. l Cơ chế Insertion sort: Lấy 1 trị phía sau chèn vào vị trí thích hợp trong nhóm trị đã có thứ tự ở phía trước. l Ma trận thường được dùng trong các bài toán khoa học và có rất nhiều cách thao tác trên ma trận. 48
49. Bài tập l Hiện thực các giải thuật Selection Sort, Bubble Sort, Insertion Sort -Viết hàm sắp xếp mảng int*a, int n giảm dần -Viết hàm sắp xếp danh sách học sinh theo điểmT giảm dần trung diemT thi sap tang dan theo diemV 49