Sắp xếp là quá trình xử lý một danh sách các phần tử để đặt chúng theo một thứ tự thỏa mãn tiêu chuẩn nào đó dựa trên nội dung thông tin lưu trữ tại mỗi phần tử.  Câu hỏi: Nêu ý tưởng của Selection Sort (Phương pháp chọn trực tiếp) Trả lời: B1: i = 0; B2: Tìm phần tử min từ a[i] đến a[N] B3: Hoán vị a[i] và a[min] B4: Nếu i < N - 1 thì i = i + 1. Lặp lại B2. Ngược lại thì dừng. Câu hỏi: Nêu ý tưởng của Insertion Sort (Chèn trực tiếp) Trả lời: B1: i = 1; B2: x = a[i]; Tìm vị trí pos thích hợp trong đoạn từ a[0] đến a[i - 1] để chèn a[i] vào B3: Dời các phần tử từ a[pos] đến a[i - 1] sang phải 1 vị trí B4: a[pos] = x B5: i = i + 1; Nếu i < n lặp lại bước 2. Ngược lại: dừng Câu hỏi: Thuật toán Shell Sort cải tiến từ thuật toán nào? Trả lời: Thuật toán Shell Sort cải tiến từ Insertion Sort. Shell sort là thuật toán hiệu quả nhất trong nhóm các thuật toán sắp xếp có độ phức tạp O(n2). Shell sort là sự cải tiến của Insertion sort dựa vào hai nhận xét sau đây:
Câu hỏi: Nêu ý tưởng của Shell Sort Trả lời: B1: Thiết lập mảng các khoảng cách (giảm dần): h[1], h[2],...,h[k]; i = 1; B2: Phân chia dãy ban đầu thành các dãy con cách nhau h[i] khoảng cách. Sắp xếp từng dãy con bằng Insertion Sort B3: i = i + 1; Nếu i > k: dừng. Ngược lại: lặp lại B2 Câu hỏi: Nêu ý tưởng của Interchange Sort (Đổi chỗ trực tiếp) Trả lời: B1: i = 0; B2: j = i + 1; B3: While j < N do: Nếu a[j] < a[i] thì đổi chỗ a[j] với a[i] j = j + 1; B4: i = i + 1; Nếu i < n - 1: lặp lại bước 2. Ngược lại: dừng Câu hỏi: Nêu ý tưởng của Bubble Sort (Nổi bọt) Trả lời: B1: i = 0; B2: j = N - 1; While (j > i) do: Nếu a[j] < a[j - 1] thì đổi chỗ a[j] và a[j - 1] j = j - 1; B3: i = i + 1; Nếu i = N - 1 Dừng. Ngược lại: lặp lại bước 2 Câu hỏi: Giải thuật Shaker Sort cải tiến thuật toán nào? Và nó cải tiến những gì? Trả lời: Giải thuật Shaker Sort cải tiến thuật toán Bubble Sort. Ý tưởng cải tiến như sau: - Trong mỗi lần sắp xếp, duyệt mảng theo cả lượt đi và lượt về + Lượt đi: đẩy phần tử nhỏ về đầu mảng + Lượt về: đẩy phần tử lớn về cuối mảng - Ghi nhận lại những đoạn đã sắp xếp nhằm tiết kiệm các phép so sánh thừa. Tham khảo Câu hỏi: Nêu ý tưởng của Shaker Sort Trả lời: B1: l = 0; r = n - 1; k = n - 1; // k để ghi nhận vị trí xảy ra hoán vị cuối cùng trong lần duyệt B2: j = r; while (j > l): if (a[j] < a[j - 1]) đổi chỗ a[j] và a[j - 1]; và k = j; j = j - 1; endwhile; l = k; j = l; while (j < r): if (a[j] > a[j + 1]) đổi chỗ a[j] và a[j + 1]; và k = j; j = j + 1; endwhile; r = k; B3: Nếu l < r. Lặp lại B2. Câu hỏi: Nêu ý tưởng Heap Sort Trả lời: Giải thuật trải qua 2 giai đoạn: GD1: Hiệu chỉnh dãy số ban đầu thành Heap B1: l = floor(N - 2) B2: Xét cặp phần tử liên đới của l (là cặp 2*l và 2*l + 1) Nếu a[l] >= a[2*l] và a[l] >= a[2*l+1] Sang bước 3 Ngược lại: chọn max(a[2*l] và a[2*l + 1]) để thay thế vào phần tử a[l], sau đó gọi để quy để kiểm tra tình trạng của phần tử là max bị đổi (phần tử 2*l hoặc 2*l + 1) B3: l = l - 1; Nếu l < 0: Dừng. Ngược lại: lặp bước 2 GD2: Sắp xếp dãy số dựa trên Heap B1: Đưa phần tử lớn nhất của Heap vào cuối B2: Xét heap con chỉ bao gồm từ đầu đến vị trí trước vị trí cuối của heap đang xét Nếu chỉ gồm 1 phần tử: Dừng B3: Hiệu chỉnh lại heap con. Câu hỏi: Nêu ý tưởng Quick Sort Trả lời: B1: Phân hoạch Chọn giá trị nằm giữa: chuyển hết các số nhỏ hơn số này về bên trái, lớn hơn về bên phải B2: Tiếp tục phân hoạch đoạn bên trái (Nhỏ hơn) và đoạn bên phải (Lớn hơn) nếu có nhiều hơn 1 phần tử. Câu hỏi: Nêu ý tưởng Merge Sort Trả lời: B1: k = 1. B2: Tách dãy ban đầu thành 2 dãy con xen kẽ nhau Ví dụ: dãy 1 là: a[0], a[2], ... a[i], a[i + k + 1],... dãy 2 là: a[1], a[3], ....a[i + 1], a[i + k + 2]... B3: Cứ xét từng cặp trong 2 dãy, chẳng hạn a[0] và a[1], lưu lại vào dãy ban đầu với thứ tự là giá trị nhỏ đứng trước, lớn đứng sau. B4: k = k * 2. Nếu k < n thì trở lại B2. Ngược lại: dừng Câu hỏi: Nêu ý tưởng của thuật toán Counting Sort Trả lời: B1: Tạo một mảng có h + 1 phần tử (f[0 ..h] = 0) Với h là số lớn nhất trong mảng cần sắp B2: Duyệt mảng cần sắp: gán f[a[i]] += 1; // Mảng f lưu số lần số hiện giá trị a[i] B3: Cập nhật vị trí chính xác của các số trong f bằng cách: Duyệt mảng f từ i = 1 đến h: f[i] += f[i = 1]; // lúc này f[i] là vị trí tận cùng bên phải của i trong mảng a B4: Sắp xếp mảng Duyệt i từ n về 1: b[f[a[i]]] = a[i]; // b là mảng kết quả, có cùng kích thước với a f[a[i]] -= 1; Câu hỏi: Nêu ý tưởng của thuật toán Radix Sort Trả lời: Gọi m là số chữ số của số dài nhất trong mảng cần sắp xếp. Duyệt m lần: Mỗi lần duyệt: ta sắp xếp các số trong mảng với tiêu chí chỉ quan tâm đến 1 chữ số duy nhất: chữ số đơn vị, hàng chục, hàng trăm... (Nếu không có giá trị ở chữ số nào thì đó là 0) Câu hỏi: Nêu ý tưởng thuật toán Flash Sort Trả lời: Ý tưởng chính của thuật toán là phân lớp các phần tửTham khảo Câu hỏi: Tóm tắt các bước thực hiện của thuật toán Radix Sort Trả lời: Gọi m là chữ số tối đa của mỗi phần tử B1: k = 0; // k cho biết chữ số dùng để phân loại, k = 0 là hàng đơn vị, 1 là hàng chục... B2: Khởi tạo 10 lô B0, B1, B2...B9 rỗng B3: for i = 1...n do: Đặt a[i] vào lô Bt với t là chữ số hàng thứ k của a[i] B3: Nối B0....B9 lại theo đúng trình tự thành a B4: k = k + 1; Nếu k < m thì trở lại B2; Ngược lại: Dừng Câu hỏi: Cho biết độ phức tạp của các thuật toán sắp xếp Trả lời: - Selection Sort: O(n2) - Insertion Sort: O(n2) - Shell Sort: O(n2) - Interchange Sort: O(n2) - Bubble Sort: O(n2) - Shaker Sort: O(n2) - Heap Sort: Ω(nlogn) - Quick Sort: trung bình là O(nlogn), xấu nhất là O(n - Merge Sort: O(nlogn) - Counting Sort: O(n) - Radix Sort: O(n) |
