Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - TS. Nguyễn Thị Kim Thoa

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 5: Các giải thuật sắp xếp và tìm kiếm, cung cấp cho người học những kiến thức như Điều kiện bài toán sắp xếp; giải thuật sắp xếp lựa chọn; giải thuật sắp xếp lựa chọn – cài đặt hàm; sắp xếp kiểu thêm dần/chèn;... Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - TS. Nguyễn Thị Kim Thoa Chương 5: CÁC GIẢI THUẬT SẮP XẾP VÀ TÌM KIẾM Data structures and Algorithms2/18/2021 Cấu trúc dữ liệu và giải thuật 1 Bài toán sắp xếp trên cấu trúc mảng• Sắp xếp cơ bản – Sắp xếp kiểu lựa chọn (Selection - sort) – Sắp xếp chèn/thêm dần (Insertion- sort) – Sắp xếp đổi chỗ/nổi bọt (Exchange/Bubble - sort)• Sắp xếp nâng cao (sắp xếp nhanh) – Sắp xếp nhanh (Quick-sort) – Sắp xếp trộn (Merge-sort) – Sắp xếp vun đống (Heap-sort)2/18/2021 Cấu trúc dữ liệu và giải thuật 2 Điều kiện bài toán sắp xếp• Dãy A có n phần tử : A[1], A[2],…,A[n]• Sắp xếp dãy A theo thứ tự tăng dần hoặc giảm dần2/18/2021 Cấu trúc dữ liệu và giải thuật 3 Sắp xếp kiểu lựa chọn (Selection - sort)No. Min A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] 32 51 27 83 66 11 45 751 11 11 51 27 83 66 32 45 752 27 11 27 51 83 66 32 45 753 32 11 27 32 83 66 51 45 754 45 11 27 32 45 66 51 83 755 51 11 27 32 45 51 66 83 756 66 11 27 32 45 51 66 83 757 75 11 27 32 45 51 66 75 83Chiến thuật: Chọn số nhỏ nhất trong dãy chưa được sắp xếp và đổi chỗ với số đangchiếm vị trí đầu tiên của dãy này2/18/2021 Cấu trúc dữ liệu và giải thuật 4 Giải thuật sắp xếp lựa chọn• Bước 1: Thiết lập Min = 1 là vị trí đầu tiên của dãy• Bước 2: Tìm kiếm phần tử nhỏ nhất trong danh sách• Bước 3: Tráo đổi giá trị tại vị trí Min• Bước 4: Tăng Min để trỏ tới vị trí tiếp theo• Bước 5: Lặp lại từ bước 2 cho đến khi danh sách được sắp xếp2/18/2021 Cấu trúc dữ liệu và giải thuật 5 Giải thuật sắp xếp lựa chọnProcedure SELECTION_SORT(A,n) for i:=1 to (n-1) do Min:= i; for j:= i+1 to n do if A[j] < A[Min] then Min:=j; EndFor If (Mini) then temp: = A[Min]; A[Min] = A[i]; A[i] = temp; EndForReturnĐánh giá giải thuật:• Số vòng lặp for cần thực thi là• Ctb = (n-1) + (n-2) + …+1 = (n-1)*(n-1+1)/2• Do đó T(n) = O(n2) 2/18/2021 Cấu trúc dữ liệu và giải thuật 6 Giải thuật sắp xếp lựa chọn – cài đặt hàm void SELECTION_SORT(int A[], int n) { int Min; for (int i=0; i < n-1; i++){ Min=i; for (int j=i+1; j < n; j++) if (A[j] < A[Min]) Min=j; if (Min != i){ int temp= A[Min]; A[Min] = A[i]; A[i] = temp; } } }2/18/2021 Cấu trúc dữ liệu và giải thuật 7 Sắp xếp kiểu thêm dần/chèn (Insertion sort)No. Số so A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] sánh 32 51 27 83 66 11 45 751 51 32 51 27 83 66 11 45 752 27 27 32 51 83 66 11 45 753 83 27 32 51 83 66 11 45 754 66 27 32 51 66 83 11 45 755 11 11 27 32 51 66 83 45 756 45 11 27 32 45 51 66 83 757 75 11 27 32 45 51 66 75 832/18/2021 Cấu trúc dữ liệu và giải thuật 8 Giải thuật sắp xếp chèn• Bước 1: Xét A[1] là dãy con ban đầu đã được sắp xếp• Bước 2: Xét A[2], nếu A[2] < A[1] chèn vào trước A[1], còn lại thì giữ nguyên A[2] tại chỗ• Bước 3: Xét A[1], A[2] là dãy con được sắp xếp• Bước 4: Xét A[3], so sánh với A[1], A[2] và tìm vị trí chèn• Bước 5: Lặp lại với A[4], … đến khi dãy được sắp xếp hết2/18/2021 Cấu trúc dữ liệu và giải thuật 9 Giải thuật sắp xếp chènProcedure INSERT_SORT(A,n) void InsertionSort(int A[], int n) For i = 1 to n-1 { { temp = A[i]; for (int i = 1; i < n; i++) j = i-1; { While temp Sắp xếp đổi chỗ/ ...