tailieunhanh - Cấu trúc dữ liệu và giải thuật - chương 8

Chương 8 của bộ slide bài giảng đầy đủ (gồm 11 chương) về môn CTDL & GT của trường ĐHBK . Trình bày ngắn gọn dễ hiểu với những hiệu ứng minh họa sinh động. Hướng dẫn các bạn sắp xếp thứ tự trong một lập trình dễ dàng hơn. | CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (501040) Chương 8: Sắp thứ tự Khái niệm Sắp thứ tự: Đầu vào: một danh sách Đầu ra: danh sách có thứ tự tăng (hoặc giảm) trên khóa Phân loại: Sắp thứ tự ngoại (external sort): tập tin Sắp thứ tự nội (internal sort): bộ nhớ Giả thiết: Sắp thứ tự nội Sắp tăng dần Insertion sort Insertion sort - Danh sách liên tục Giải thuật insertion sort – Danh sách liên tục Algorithm Insertion_sort Input: danh sách cần sắp thứ tự Output: danh sách đã được sắp thứ tự 1. for first_unsorted = 1 to size //Tìm vị trí hợp lý để chèn giá trị đang có vào . current = list[first_unsorted] . position = first_unsorted . while (position>0 and list[position - 1] > current) //Dời chỗ các phần tử lớn về sau . list[position] = list[position - 1] . position = position - 1 //Chép phần tử trước đó vào đúng vị trí của nó . list[position - 1] = current End Insertion_sort Mã C++ Insertion sort – Danh sách liên tục template void Sortable_list :: insertion_sort( ) { int first_unsorted; // position of first unsorted entry int position; // searches sorted part of list Record current; // holds the entry temporarily removed from list for (first_unsorted = 1; first_unsorted 0 && entry[position − 1] > current); entry[position] = current; } } Insertion sort – DSLK Giải thuật Insertion sort - DSLK Algorithm Insertion_sort Input: danh sách cần sắp thứ tự và có ít nhất 1 phần tử Output: danh sách đã được sắp thứ tự 1. last_sorted = head //Đi dọc danh sách liên kết 2. while (last_sorted chưa là phần tử cuối) . first_unsorted là phần tử kế của last_sorted //Chèn vào đầu? . if (dữ liệu của first_unsorted 0 and list[position - 1] > current) //Dời chỗ các phần tử lớn về sau . list[position] = list[position - 1] . position = position - 1 //Chép phần tử trước đó vào đúng vị trí của nó . list[position - 1] = current End Insertion_sort Mã C++ Insertion sort – Danh sách liên tục template void Sortable_list :: .