Sắp xếp được dữ liệu theo các trật tự và tiêu chí khác nhau
4. Thuật toán sắp xếp chèn
Ý tưởng
Sắp xếp chèn (insertion sort) thực hiện sắp xếp một dãy số bằng cách duyệt từng phần tử và chèn phần tử đó vào vị trí thích hợp trong một danh sách con mới sao cho danh sách con luôn luôn được duy trì dưới dạng đã qua sắp xếp.
Ví dụ: Để sắp xếp một danh sách các số (2 9 5 4 8 1 6) theo trật tự tăng dần. Bước đầu tiên, danh sách con mới chỉ chứa phần tử đầu tiên đó là số 2. Tiếp theo, chúng ta sẽ chèn số 9 vào trong danh sách con đó, vì số 9 lớn hơn 2 cho nên số chỉ phải được “chèn” vào phía sau 2. Sau đó, chúng ta sẽ chèn số 5 vào trong danh sách con, vì số 5 lớn hơn 2 nhưng lại nhỏ hơn 9 cho nên sẽ được chèn vào giữa hai số này. Tương tự như vậy cho các số còn lại cho đến khi tất cả các số đều được chèn vào danh sách con.
Quá trình “chèn” được diễn ra bằng cách dịch chuyển các phần tử ở phía sau vị trí muốn chèn để tạo một chỗ trống cho phần tử mới. Chẳng hạn như ở Bước 3 ở trên, để chèn số 4 vào vị trí trước số 5 thì chúng ta phải dịch chuyển số 9 và số 9 về phía sau để tạo một khoảng trống trước số 5.
Giải thuật
Từ mô tả trên ta đã có một bức tranh khái quát cho giải thuật sắp xếp chèn, chúng ta sẽ có các bước cơ bản cho giải thuật như sau:
for (let i = 1; i < list.length; i++) {
chèn phần tử list[i] vào danh sách con list[0..i-1] sao cho danh sách list[0..i] luôn được sắp xếp
}
Cài đặt thuật toán sắp xếp chèn
Hàm insertSort()
1. function insertionSort(items) {
2. for (let i = 1; i < items.length; i++) {
3. let value = arr[i];
4. let j = i-1;
5.
6. while (j >= 0 && items[j] > items[i]) {
7. items[j+1] = items[j];
8. j--;
9. }
10. items[j+1] = items[i];
11. }
12. return items;
13. }
5. Thuật toán sắp xếp chọn
Ý tưởng
Chẳng hạn, nếu chúng ta muốn sắp xếp một danh sách theo trật tự tăng dần. Chúng ta sẽ tìm ra phần tử nhỏ nhất trong danh sách, rồi đưa phần tử đó về vị trí đầu tiên. Sau đó, chúng ta tìm phần tử nhỏ nhất trong danh sách còn lại (trừ phần tử đầu tiên trước đó) và đưa nó về vị trí đầu tiên trong danh sách còn lại đó, cứ như thế cho đến phần tử cuối cùng.
Ví dụ: Để sắp xếp danh sách các số {2, 9, 5, 4, 8, 1, 6} sử dụng thuật toán sắp xếp chọn, chúng ta sẽ tiến hành các bước như sau:
Giải thuật
Từ mô tả ở trên, chúng ta có thể có một giải thuật cho thuật toán sắp xếp chọn như sau:
for (int i = 0; i < list.length – 1; i++) {
tìm phần tử nhỏ nhất trong danh sách list[i..list.length-1];
hoán đổi phần tử nhỏ nhất với phần tử list[i] nếu cần thiết
// list[i] đã nằm đúng vị trí của nó.
// lần lặp tiếp theo được thực hiện trong danh sách còn lại list[i+1..list.length-1]
}
Cài đặt thuật toán sắp xếp chọn
Hàm selectionSort()
1. function selectionSort(arr) {
2. let minIndex, temp, len = arr.length;
3. for (let i = 0; i < len; i++) {
4. minIndex = i;
5. // tìm index của giá trị nhỏ nhất
6. for (let j = i+1; j < len; j++) {
7. if(arr[j] < arr[minIndex]) {
8. minIndex = j;
9. }
10. }
11.
12. // Đổi chỗ
13. temp = arr[i];
14. arr[i] = arr[minIndex];
15. arr[minIndex] = temp;
16. }
17. return arr;
18. }
6. Bài thực hành
Bài 1: Triển khai thuật toán sắp xếp nổi bọt
Mục tiêu:
Luyện tập triển khai thuật toán sắp xếp nổi bọt.
Mô tả:
Hãy viết một hàm triển khai thuật toán sắp xếp nổi bọt. Hàm này có mô tả như sau:
function bubbleSort(arr, asc);
Trong đó:
- arr là một mảng bất kỳ
- asc là trật tự mà chúng ta muốn sắp xếp, nêu asc có giá trị true thì sắp xếp theo trật tự tăng dần, còn nến asc có giá trị false thì sắp xếp theo trật tự giảm dần.
Hướng dẫn:
- Hãy tham khảo thuật toán và mã nguồn trong Mục 3 – Thuật toán sắp xếp nổi bọt để viết một hàm triển khai thuật toán sắp xếp nổi bọt
- Hãy thử nghiệm với một mảng số nguyên theo trật tự giảm dần
- Hãy thử nghiệm với một mảng chuỗi theo trật tự tăng dần
Bài 2: Triển khai thuật toán sắp xếp chèn
Mục tiêu:
Luyện tập triển khai thuật toán sắp xếp chèn.
Mô tả:
Hãy viết một hàm triển khai thuật toán sắp xếp chèn. Hàm này có mô tả như sau:
function insertionSort(arr, asc);
Trong đó:
- arr là một mảng bất kỳ
- asc là trật tự mà chúng ta muốn sắp xếp, nêu asc có giá trị true thì sắp xếp theo trật tự tăng dần, còn nến asc có giá trị false thì sắp xếp theo trật tự giảm dần.
Hướng dẫn:
- Hãy tham khảo thuật toán và mã nguồn trong Mục 4 – Thuật toán sắp xếp chèn để viết một hàm triển khai thuật toán sắp xếp chèn
- Hãy thử nghiệm với một mảng số nguyên theo trật tự giảm dần
- Hãy thử nghiệm với một mảng chuỗi theo trật tự tăng dần
Bài 3: Triển khai thuật toán sắp xếp chọn
Mục tiêu:
Luyện tập triển khai thuật toán sắp xếp chọn.
Mô tả:
Hãy viết một hàm triển khai thuật toán sắp xếp chọn. Hàm này có mô tả như sau:
function selectionSort(arr, asc);
Trong đó:
- arr là một mảng bất kỳ
- asc là trật tự mà chúng ta muốn sắp xếp, nêu asc có giá trị true thì sắp xếp theo trật tự tăng dần, còn nến asc có giá trị false thì sắp xếp theo trật tự giảm dần.
Hướng dẫn:
- Hãy tham khảo thuật toán và mã nguồn trong Mục 3 – Thuật toán sắp xếp chọn để viết một hàm triển khai thuật toán sắp xếp chọn
- Hãy thử nghiệm với một mảng số nguyên theo trật tự giảm dần
- Hãy thử nghiệm với một mảng chuỗi theo trật tự tăng dần
Xem tiếp>> Chuong 8 Bai tap
Có thể bạn quan tâm>> Cam nang lap trinh co ban danh cho nguoi moi bat dau
