TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 6 - Ngô Công Thắng
Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 6: Giải thuật sắp xếp" cung cấp cho người học các kiến thức: Sắp xếp chọn, sắp xếp chèn, sắp xếp nổi bọt, sắp xếp nhanh, sắp xếp vun đống, sắp xếp hòa nhập. | 1. Sắp xếp chọn (Selection Sort) . Phương pháp • Giả sử cần sắp xếp tăng dần một dãy khoá a1, a2,., an. • Ý tưởng của thuật toán như sau: CHƯƠNG 6 GIẢI THUẬT SẮP XẾP – Chọn phần tử có khoá nhỏ nhất . – Đổi chỗ nó với phần tử a1. – Sau đó lặp lại thao tác trên với n-1 phần tử còn lại, rồi lại lặp lại như trên với n-2 phần tử còn lại,., cho tới khi chỉ còn 1 phần tử. GV. Ngô Công Thắng Bộ môn Công nghệ phần mềm Khoa Công nghệ thông tin Website: Email: ncthang@ Ngô Công Thắng Chương 6: Giải thuật sắp xếp Bài giàng CTDL> - Chương 06 . Phương pháp (tiếp) 1. Sắp xếp chọn (Selection Sort) 2. Sắp xếp chèn (Insert Sort) 3. Sắp xếp nổi bọt (Bubble Sort) 4. Sắp xếp nhanh (Quick Sort) 5. Sắp xếp vun đống (Heap Sort) 6. Sắp xếp hòa nhập (Merge Sort) Ngô Công Thắng Bài giàng CTDL> - Chương 06 • Ví dụ: Cho dãy khoá ban đầu là: 6, 10, 1, 8, 9 với n=5. i=1 1, 10, 6, 8, 9 i=2 1, 6, 10, 8, 9 i=3 1, 6, 8, 10, 9 i=4 1, 6, 8, 9, 10 Ngô Công Thắng Bài giàng CTDL> - Chương 06 . Phương pháp (tiếp) 2. Sắp xếp chèn (Insert Sort) Procedure Selection_sort(a,n); For i:= 1 to n-1 Do Begin {Tìm phần tử nhỏ nhất ở vị trí k } k:=i; For j:=i+1 To n Do If a[j] a[j-1]; Return Ngô Công Thắng Ngô Công Thắng – Chọn ngẫu nhiên một phần tử x. – Duyệt từ bên trái mảng cho tới khi có một phần tử ai>=x – Sau đó duyệt từ bên phải mảng cho tới khi có một phần tử aj= x. • Người ta đã chứng minh được thời gian trung bình thực hiện giải thuật là: Ttb= O(nlog2n) • Như vậy, với n khá lớn Quick sort có hiệu lực hơn 3 thuật giải trên. Ngô Công Thắng Ngô Công Thắng Bài giàng CTDL> - Chương 06 Thủ tục sắp xếp nhanh Bài giàng CTDL> - Chương 06 5. Sắp xếp vun đống (Heap Sort) Procedure Q_sort(L,R); 1) If L>=R then return; 2) i:=L; j:=R ; k:=(L+R) div 2; 3) x:=a[k]; 4) Repeat While a[i] x Do j:=j-1; If ix } Return Ngô Công Thắng Bài giàng CTDL> - Chương 06 . Phương pháp • Một cây nhị phân có chiều cao h .
đang nạp các trang xem trước
