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.
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 6 - Ngô Công Thắng1. Sắp xếp chọn (Selection Sort)1.1. 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 6GIẢ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ắngBộ môn Công nghệ phần mềmKhoa Công nghệ thông tinWebsite: dse.vnua.edu.vn/ncthangEmail: ncthang@vnua.edu.vnNgô Công ThắngChương 6: Giải thuật sắp xếpBài giàng CTDL> - Chương 066.31.1. 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ắngBài giàng CTDL> - Chương 06• Ví dụ:Cho dãy khoá ban đầu là: 6, 10, 1, 8, 9với n=5.i=1 1, 10, 6, 8, 9i=2 1, 6, 10, 8, 9i=3 1, 6, 8, 10, 9i=4 1, 6, 8, 9, 106.2Ngô Công ThắngBài giàng CTDL> - Chương 066.41.1. 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 DoBegin{Tìm phần tử nhỏ nhất ở vị trí k }k:=i;For j:=i+1 To n DoIf a[j] < a[k] then k:=j{Đổi chỗ phần tử nhỏ nhất k cho phần tử i}If k ≠ i then a[k]↔a[i];EndReturnNgô Công ThắngBài giàng CTDL> - Chương 062.1. Phương pháp• Phương pháp này được những người chơi bài haydùng.• Giả sử cần sắp xếp tăng dần dãy khoá a1, a2,..., an. Ýtưởng thuật toán như sau:– Các phần tử được chia thành dãy đích: a1,..., ai-1 (kết quả)và dãy nguồn ai,..., an.– Bắt đầu với i=2, ở mỗi bước phần tử thứ i của dãy nguồnđược lấy ra và chèn vào vị trí thích hợp trong dãy đích saocho dãy đích vẫn tăng dần. Sau đó i tăng lên 1 và lặp lại.6.5Ngô Công Thắng• Với giải thuật trình bày ở trên thì phép toán tích cựclà phép so sánh (a[j]