Cấu trúc liệu Giải thuật Cấu trúc liệu Giải thuật Chương VI: Sắp xếp 2⏐9 → 7⏐2 → 7→7 9⏐4 → 2→2 9→9 4→4 Đỗ Bích Diệp - Khoa CNTT Chương VI: Sắp xếp z Nội dung Bài toán xếp Ba phương pháp xếp Lựa chọn, thêm dần đổi chỗ Phân tích, đánh giá Sắp xếp kiểu hòa nhập Sắp xếp nhanh Sắp xếp kiểu vun đống Một số phương pháp xếp đặc biệt Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN CuuDuongThanCong.com https://fb.com/tailieudientucntt Cấu trúc liệu Giải thuật Bài toán Sắp xếp – Sắp xếp lại tập phần tử liệu theo chiều tăng dần giảm dần 23 78 45 32 56 23 32 45 78 56 Đỗ Bích Diệp - Khoa CNTT Bài tốn Sắp xếp – Khóa xếp z z – Một phận ghi biểu diễn đối tượng Khóa sử dụng để xác định thứ tự xếp ghi tập ghi Bảng khóa: z z Sử dụng xếp muốn hạn chế việc di chuyển ghi liệu Một tập ghi chứa hai trường – – z Khóa: chứa khóa xếp Link: Con trỏ ghi địa ghi đối tượng liệu tương ứng Thứ tự ghi bảng khóa cho phép xác định thứ tự ghi liệu Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN CuuDuongThanCong.com https://fb.com/tailieudientucntt Cấu trúc liệu Giải thuật Các loại thuật toán Sắp xếp Sorts Internal External Insertion Selection • Natural • Balanced • Polyphase • Insertion • Shell • Selection • Heap Exchange • Bubble • Quick Đỗ Bích Diệp - Khoa CNTT Bài toán Sắp xếp – Các đặc trưng thuật tốn xếp z Tính ổn định thuật tốn xếp – Các phần tử có khóa giữ nguyên thứ tự tương đối chúng trước xếp 78 45 z 32 56 8 32 45 56 78 Tính chỗ – Thuật tốn địi hỏi khơng gian nhớ phụ số (không phụ thuộc vào số lượng phần tử dãy cần sắp) Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN CuuDuongThanCong.com https://fb.com/tailieudientucntt Cấu trúc liệu Giải thuật Bài toán Sắp xếp – Trong chương này, toán xếp đơn giản hóa dạng sau z z Đầu vào: Một dãy số nguyên a1, a2, …, an Đầu : Một hoán vị dãy số cho giá trị xếp theo chiều tăng dần Đỗ Bích Diệp - Khoa CNTT Ba phương pháp xếp Sắp xếp kiểu lựa chọn (Selection Sort) Sắp xếp kiểu thêm dần (Insertion Sort) Sắp xếp kiểu đổi chỗ - Sắp xếp kiểu bọt (Buble Sort) Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN CuuDuongThanCong.com https://fb.com/tailieudientucntt Cấu trúc liệu Giải thuật Sắp xếp kiểu lựa chọn – Selection Sort – Ý tưởng: z z Tại lượt, chọn phần tử nhỏ số phần tử chưa Đưa phần tử chọn vào vị trí phép đổi chỗ Sau lượt thứ i (i = n-1) , dãy cần coi chia thành phần – – Phần sắp: từ vị trí đến i Phần chưa sắp: từ vị trí i +1 đến n Đỗ Bích Diệp - Khoa CNTT Sắp xếp kiểu lựa chọn – Ví dụ: Sắp xếp dãy sau theo thứ tự tăng dần: z A = {12, 5, 3, 10, 18, 4, 9, 16} Lượt Lượt Lượt Lượt Lượt Lượt Lượt 12 3 3 3 5 4 4 4 12 12 5 5 10 10 10 10 9 9 18 18 18 18 18 10 10 10 4 12 12 12 12 12 9 9 10 18 18 16 16 16 16 16 16 16 16 18 Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN CuuDuongThanCong.com https://fb.com/tailieudientucntt Cấu trúc liệu Giải thuật Sắp xếp kiểu lựa chọn Procedure –SELECTION-SORT(A,n) Giải thuật for i = to n-1 begin {Duyệt từ đỉnh} = i; {Chọn phần tử nhỏ nhất} for j = i+1 to n if A[j] < A[min] then = j ; {Đổi chổ phần tử i phần tử nhỏ nhất} T = A[i]; A[i] = A[min]; A[min] = T; end; End Đỗ Bích Diệp - Khoa CNTT Sắp xếp kiểu lựa chọn – Thời gian thực thuật toán z Trường hợp tốt nhất: – – z Trường hợp xấu – – Dãy ban đầu xếp phép đổi chỗ, thực n(n-1)/2 phép so sánh n-1 phép đổi chỗ, n(n-1)/2 phép so sánh Độ phức tạp thời gian trung bình O(n2) Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN CuuDuongThanCong.com https://fb.com/tailieudientucntt Cấu trúc liệu Giải thuật Sắp xếp kiểu thêm dần – Insertion sort zÝ tưởng: – – Dãy cần chia thành phần: phần sắp, lại phần chưa Tại lượt, phần tử phần chưa “thêm” vào vị trí phần Đỗ Bích Diệp - Khoa CNTT Sắp xếp kiểu thêm dần – Ví dụ: Sắp xếp dãy sau theo thứ tự tăng dần: z A = {12, 5, 3, 10, 18, 4, 9, 16} Lượt Lượt Lượt Lượt Lượt Lượt Lượt 12 3 3 3 12 5 4 3 12 10 10 5 10 10 10 12 12 10 9 18 18 18 18 18 12 10 10 4 4 18 12 12 9 9 9 18 16 16 16 16 16 16 16 16 18 Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN CuuDuongThanCong.com https://fb.com/tailieudientucntt Cấu trúc liệu Giải thuật Sắp xếp kiểu thêm dần Procedure INSERTION-SORT(A,n) – Giải thuật for i := to n begin {Chọn phần tử phần chưa xếp} val := A[i]; j := i; {Tìm vị trí thích hợp đề chèn phần tử A[i] phần sắp- chứa phần tử từ vị trí đến i-1} while ( j > 1) and (A[j-1] > val) begin A[j] := A[j-1]; j := j -1; end; {Chèn phần tử A[i] vào vị trí thích hợp} A[j] := val; end; End Đỗ Bích Diệp - Khoa CNTT Sắp xếp kiểu thêm dần – – Sắp xếp thêm dần chỗ ổn định Thời gian thực giải thuật z Trường hợp tốt nhất: – – z Trường hợp xấu – – Dãy ban đầu xếp thực phép đổi chỗ, n-1 phép so sánh n(n-1)/2 phép đổi chỗ so sánh Độ phức tạp thời gian trung bình O(n2) Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN CuuDuongThanCong.com https://fb.com/tailieudientucntt Cấu trúc liệu Giải thuật Sắp xếp kiểu bọt – Ví dụ z A = {12, 5, 3, 10, 18, 4, 9, 16} Lượt Lượt Lượt Lượt Lượt Lượt Lượt 12 3 3 3 12 4 4 4 12 5 5 10 12 9 9 18 10 9 12 10 10 10 18 10 10 10 12 12 12 9 18 16 16 16 16 16 16 16 16 18 18 18 18 18 Đỗ Bích Diệp - Khoa CNTT Sắp xếp kiểu bọt zÝ tưởng: – – Dãy cần chia thành phần: phần sắp, cịn lại phần chưa Thơng qua phép đổi chỗ, lượt phần tử nhỏ phần chưa “đẩy dần” lên trước cuối nhập vào phần Phần chưa Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN CuuDuongThanCong.com https://fb.com/tailieudientucntt Cấu trúc liệu Giải thuật Sắp xếp kiểu bọt Procedure BUBBLE-SORT(A,n) – Giải thuật for i := to n-1 {Duyệt từ đáy} for j:= n down to i+1 {Kiểm tra phần tử kề cận nhau, ngược thứ tự đổi chỗ } if A[j] < A[j-1] then begin X:= A[j]; A[j] := A[j-1]; A[j-1] := X; end return Đỗ Bích Diệp - Khoa CNTT Sắp xếp kiểu bọt – Thời gian thực giải thuật z Trường hợp tốt nhất: – – z Trường hợp xấu – – Dãy ban đầu xếp thực phép đổi chỗ, n(n-1)/2 phép so sánh n(n-1)/2 phép đổi chỗ so sánh Độ phức tạp thời gian trung bình O(n2) Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN CuuDuongThanCong.com 10 https://fb.com/tailieudientucntt Cấu trúc liệu Giải thuật Sắp xếp kiểu hòa nhập - Ví dụ minh họa z Lời gọi đệ qui – Trường hợp sở 4⏐3 → 2⏐9 4→ 7⏐2→2 7→7 2→2 → → 9→9 4→4 → 3→3 8→8 → 6→6 1→1 Đỗ Bích Diệp - Khoa CNTT Sắp xếp kiểu hịa nhập - Ví dụ minh họa z Lời gọi đệ qui – Trường hợp sở 4⏐3 → 2⏐9 4→ 7⏐2→2 7→7 2→2 → → 9→9 4→4 → 3→3 8→8 → 6→6 1→1 Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN CuuDuongThanCong.com 19 https://fb.com/tailieudientucntt Cấu trúc liệu Giải thuật Sắp xếp kiểu hịa nhập - Ví dụ minh họa z Hịa nhập 4⏐3 → 2⏐9 4→ 7⏐2→2 7→7 2→2 → → 9→9 4→4 → 3→3 8→8 → 6→6 1→1 Đỗ Bích Diệp - Khoa CNTT Sắp xếp kiểu hòa nhập - Ví dụ minh họa z Lời gọi đệ qui … Trường hợp sở , Hòa nhập 4⏐3 → 2⏐9 4→ 7⏐2→2 7→7 2→2 → → 9→9 4→4 → 3→3 8→8 → 6→6 1→1 Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN CuuDuongThanCong.com 20 https://fb.com/tailieudientucntt ... 9 10 18 18 16 16 16 16 16 16 16 16 18 Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN CuuDuongThanCong.com https://fb.com/tailieudientucntt Cấu trúc liệu Giải thuật Sắp xếp kiểu lựa.. .Cấu trúc liệu Giải thuật Bài toán Sắp xếp – Sắp xếp lại tập phần tử liệu theo chiều tăng dần giảm dần 23 78 45 32 56 23 32 45 78 56 Đỗ Bích Diệp - Khoa CNTT Bài tốn Sắp xếp – Khóa xếp z... 10 10 18 10 10 10 12 12 12 9 18 16 16 16 16 16 16 16 16 18 18 18 18 18 Đỗ Bích Diệp - Khoa CNTT Sắp xếp kiểu bọt zÝ tưởng: – – Dãy cần chia thành phần: phần sắp, lại phần chưa Thông qua phép