Bài giảng Lập trình cơ bản với C - Bài 7: Tìm kiếm và sắp xếp

Nội dung text: Bài giảng Lập trình cơ bản với C - Bài 7: Tìm kiếm và sắp xếp

1. Tìm kiếm và sắp xếp Bài 7
2. Nội dung chính  Giải thích sự cần thiết việc tìm kiếm và sắp xếp  Thảo luận về các thuật toán sắp xếp cơ bản:  Sắp xếp nổi bọt (Bubble Sort)  Sắp xếp chèn (Insertion Sort)  Thảo luận về các thuật toán tìm kiếm:  Tìm kiếm tuyến tính (Linear Search)  Tìm kiếm nhị phân (Binary Search)
3. Sắp xếp .Sắp xếp dữ liệu liên quan đến việc sắp xếp mảng theo một thứ tự nào đó chẳng hạn như tăng dần hoặc giảm dần. .Dữ liệu trong mảng dễ dàng tìm kiếm khi được sắp xếp. .Có hai cách thức dùng sắp xếp mảng Sắp xếp lựa chọn (Selection Sort) và Sắp xếp nổi bọt (Bubble Sort )
4. Sắp xếp (tiếp) .Trong cách sắp xếp lựa chọn giá trị của phần tử hiện tại được so sánh với các phần tử tiếp theo trong mảng để thu được giá trị lớn/nhỏ nhất. .Có 2 phương pháp trong sắp xếp nổi bọt được triển khai: . Từ dưới lên (Bottom-up): So sánh các giá trị lần lượt từ cuối mảng nếu nhỏ hơn thì dẫn dần cho lên trên (xem chương 19, Sgk) . Từ trên xuống: So sánh bắt đầu từ phần tử trên cùng, nếu phần tử lớn hơn sẽ bị chìm xuống dưới.
5. Sắp xếp nổi bọt 126 126 2214 14228 17228 1722 6 12 148 148 17 22  Cho một mảng có n phần tử  Lặp lại các bước sau n-1 lần:  Với a[i] và a[i+1]:  Nếu a[i] lớn hơn a[i+1] thì đổi vị trí cho nhau.
6. Sắp xếp nổi bọt #include void main() { int i,j,temp,arr[5]={23,90,9,25,16}; for (int i=0; i arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } Contd
7. Sắp xếp nổi bọt ( tiếp) printf("\nThe sorted array"); for(i=0;i<5;i++) printf("\n%d", arr[i]); getch(); }
8. Sắp xếp chèn  Những ý tưởng chính được dùng trong Sắp xếp chèn:  Đối với mỗi phần tử của mảng, đặt nó vào đúng vị trí giữa các phần tử khác được sắp xếp.  Khi phần tử cuối cùng được đặt vào vị trí, mảng được sắp xếp xong.
9. Sắp xếp chèn 23 17 45 18 12 22
10. Sắp xếp chèn 23 17 45 18 12 22 1 2 3 4 5 6
11. Sắp xếp chèn 23 17 45 18 12 22 1 2 3 4 5 6 1 2 3 4 5 6
12. Sắp xếp chèn 17 45 18 12 22 1 2 3 4 5 6 23 1 2 3 4 5 6
13. Sắp xếp chèn 45 18 12 22 1 2 3 4 5 6 17 23 1 2 3 4 5 6
14. Sắp xếp chèn 18 12 22 1 2 3 4 5 6 17 23 45 1 2 3 4 5 6
15. Sắp xếp chèn 12 22 1 2 3 4 5 6 17 18 23 45 1 2 3 4 5 6
16. Sắp xếp chèn 1 2 3 4 5 6 12 17 18 22 23 45 1 2 3 4 5 6
17. Sắp xếp chèn void main(){ int data[5] = { 23, 90, 9, 25, 16 }; int tmp,i,j; //perform insertion sorting for (j=1; j =0 && tmp < data[i] ) { data[i+1] = data[i]; i ; } data[i+1] = tmp; } //display sorted array for(int i=0;i<5;i++) printf("%d\t",data[i]); }
18. Tìm kiếm .Trong bài học này, chúng ta sẽ thảo luận hai cách tìm kiếm: .Tìm kiếm tuyến tính .Tìm kiếm nhị phân
19. Tìm kiếm tuyến tính .Đây là cách đơn giản nhất để tìm kiếm một phần tử trong mảng, bằng cách duyệt tất cả các phần tử của mảng cho tới khi tìm thấy phần tử cần tìm. .Còn được gọi là tìm kiếm tuần tự (Sequential searching)
20. Tìm kiếm tuyến tính #include #include void main(){ int data[] = {5,2,9,7,6,10}; int a = 7; int i; for(i = 0; i<6;i++){ if(a == data[i]) break; } printf(“Number %d found at position %d”,a,i); getch(); }
21. Tìm kiếm nhị phân . Tìm kiếm nhị phân được thực hiện trên mảng đã được sắp xếp . Thuật toán này sử dụng đệ quy để thực hiện tìm kiếm: . Bước 1: So sánh phần tử tìm kiếm với phần tử ở vị trí giữa mảng. Nếu kết quả so sánh là bằng nhau, kết thúc tìm kiếm. . Bước 2: Nếu kết quả so sánh là nhỏ hơn thì lặp lại bước 1 với phần bên trái của mảng. . Bước 3: Nếu kết quả so sánh là lớn hơn lặp lại bước 1 với phần bên phải của mảng.
22. Tìm kiếm nhị phân – Ví dụ Ví dụ: Tìm số 33 trong mảng được sắp xếp dưới đây: 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 lo hi
23. Tìm kiếm nhị phân – Ví dụ Ví dụ: Tìm số 33 trong mảng được sắp xếp dưới đây: 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 lo mid hi
24. Tìm kiếm nhị phân – Ví dụ Ví dụ: Tìm số 33 trong mảng được sắp xếp dưới đây: 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 lo hi
25. Tìm kiếm nhị phân – Ví dụ Ví dụ: Tìm số 33 trong mảng được sắp xếp dưới đây: 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 lo mid hi
26. Tìm kiếm nhị phân – Ví dụ Ví dụ: Tìm số 33 trong mảng được sắp xếp dưới đây: 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 lo hi
27. Tìm kiếm nhị phân – Ví dụ Ví dụ: Tìm số 33 trong mảng được sắp xếp dưới đây: 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 lo mid hi
28. Tìm kiếm nhị phân – ví dụ Ví dụ: Tìm số 33 trong mảng được sắp xếp dưới đây: 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 lo hi
29. Tìm kiếm nhị phân – Ví dụ Ví dụ: Tìm số 33 trong mảng được sắp xếp dưới đây: 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 lo hi mid
30. Tìm kiếm nhị phân – Ví dụ Ví dụ: Tìm số 33 trong mảng được sắp xếp dưới đây: 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 lo hi mid
31. Tìm kiếm nhị phân #include #include void main( ) { int data[] = {0,11,13,14,15,17,18}; int low =0; int high = 6; int searchValue = 15; int flag =0; Continue
32. Tìm kiếm nhị phân while(low data[mid]){ low = mid +1; } } if(flag ==0){ printf("Element not found in the array"); } }
33. Ôn tập  Biến và hằng  Nhận dạng và và nguyên tắc đặt tên định danh  Kiểu dữ liệu  Kiểu cơ bản: char, int, float, double, void  Kiểu dữ liệu dẫn xuất: unsigned, short, long  Toán tử:  Số học  Quan hệ  Logical  Dịch bit
34. Ôn tập (tiếp)  Nhập xuất trong C:  Có định dạng  Không định dạng  Câu lệnh điều kiện: if else, switch.  Vòng lặp: for, while, do while.  Mảng Array .  Xâu/mảng ký tự.
35. Tham khảo  Sách giáo khoa, Chương 19  Sort Animation