Java insertion sort (sắp xếp chèn) đánh giá từng mục trong danh sách. Nếu mục nhỏ hơn mục trước, sort hoán đổi. Ngược lại, mục ở nguyên chỗ và so sánh 2 mục tiếp theo.
Máy tính giỏi sắp xếp danh sách. Dùng loops (vòng lặp), tìm qua tất cả mục và đổi thứ tự cho đến khi xuất hiện theo cách cụ thể.
Trong lập trình, có vài phương pháp chuẩn sắp xếp danh sách. Gọi là sort algorithms (thuật toán sắp xếp). Sort algorithms đọc qua tất cả mục và sắp theo bộ hướng dẫn cụ thể. Insertion sort là một trong các sort algorithms phổ biến nhất.
Hướng dẫn này thảo luận cách triển khai insertion sort algorithm trong Java. Sẽ đi qua ví dụ để học logic đằng sau sort này.
Java Insertion Sort là gì?
Java insertion sort hoạt động giống sắp bài tay trong game bài. Insertion sorts kiểm tra từng mục danh sách và hoán đổi với mục bên trái. Có hoán đổi hay không phụ thuộc mục lớn hơn hay nhỏ hơn các mục trước.
Hãy tưởng tượng chơi game bài – whist, rummy, bất kỳ. Khi sắp bài, bạn làm gì?
Bắt đầu bên trái kiểm tra bài thứ 2 đã sắp chưa. Nếu bài đó lớn hơn bài cuối, giữ nguyên vị trí. Ngược lại, di chuyển lên vị trí trong danh sách.
Bạn duyệt qua mọi bài tay và thực hiện phép toán cho đến khi mọi bài xuất hiện đúng thứ tự.
Khi nào dùng Insertion Sort?
Insertion sorts dùng nhiều khi chỉ vài element bên trái cần sắp xếp.
Có thuật toán hiệu quả hơn cho danh sách lớn, như merge sort. Vì vậy không nên luôn mặc định insertion sort. Có nói insertion sorts hiệu quả hơn bubble sort và selection sort khi sắp xếp element trong list.
Insertion sort là thuật toán sắp xếp đơn giản tốt cho beginner học.
Insertion Sort Walkthrough (Duyệt qua ví dụ)
Hình dung bộ bài không trực quan lắm. Duyệt ví dụ lập trình. Xét list:
| 8 | 6 | 3 | 9 |
Giả sử element đầu đã sorted.
Bước sau so sánh item 2 với item 1. Nếu item 1 lớn hơn item 2, item 2 đặt trước item 1.
Trường hợp này, 6 lớn hơn 8? Không, 6 < 8. Nghĩa là 6 lùi lại 1 vị trí, 8 tiến 1:
| 6 | 8 | 3 | 9 |
Giờ so sánh element 3 với element bên trái: 3 > 8? Không, 8 dịch phải:
| 6 | 3 | 8 | 9 |
3 > 6? Không, dịch 6:
| 3 | 6 | 8 | 9 |
Giờ so sánh item 4 (cuối) với mọi item trước. 9 lớn hơn tất cả: 8, 6, 3.
Algorithm dùng để sắp list:
- Element đầu sorted.
- So sánh item 2 với item bên trái.
- Nếu item lớn hơn giá trị bên trái, giữ nguyên. Ngược lại, dịch giá trị sang trái.
- Lặp cho đến khi mọi item đúng thứ tự.
Giờ đã có mảng sorted. Insertion sorts sắp từng item một. Thảo luận triển khai Java.
Cách thực hiện Insertion Sort trong Java
Giá trị lớn hơn của 2 giá trị so sánh được chèn 1 vị trí bên phải mỗi lần sort function chạy.
Đã nói lý thuyết, nhưng triển khai Java như thế nào? Câu hỏi hay. Viết class sắp xếp insertion sort trên danh sách điểm học sinh.
Chuẩn bị Arrays Library
Import Arrays library vào chương trình Java. Dùng để in list ra console sau khi sắp:
import java.util.Arrays;
Khai báo Sort Method
Khai báo method duyệt list và sắp dữ liệu thứ tự tăng dần (ascending):
class SortGrades {
public static void insertionSort(int [] numbersToSort) {
int itemCount = numbersToSort.length;
for (int value = 1; value < itemCount; value++) {
int key = numbersToSort[value];
int last = value - 1;
while (last >= 0 && key < numbersToSort[last]) {
numbersToSort[last + 1] = numbersToSort[last];
--last;
}
numbersToSort[last + 1] = key;
}
}
}
Bắt đầu tìm số item input array. Tạo loop duyệt mọi item. Khởi tạo for loop lặp cho đến khi sắp xong list.
Trong for loop, khai báo 2 biến: key và last.
Biến "key" theo dõi item đang sắp. Biến "last" theo dõi số item phải sắp bên trái item.
Chương trình so sánh giá trị "key" với từng element bên trái cho đến khi tìm element nhỏ hơn. Xảy ra trong while loop Java.
Định nghĩa Main Function
Chạy code, không gì xảy ra. Vì chưa định nghĩa main function. Định nghĩa main function khai báo int array (mảng số). Main function dùng insertionSort() đã khai báo sắp số. Paste code sau insertionSort method:
public static void main(String args[]) {
int[] numbers = { 8, 6, 3, 9 };
InsertionSort sortNumbers = new InsertionSort();
sortNumbers.insertionSort(numbers);
String arrayToString = Arrays.toString(numbers);
System.out.println("Sorted list: " + arrayToString);
}
Trong main method, khai báo list số muốn sắp. Tạo instance InsertionSort() tên sortNumbers. Dùng method sắp list số tăng dần. Method thay đổi giá trị bên trong array "numbers"; không khai báo array riêng lưu giá trị.
Tiếp theo, dùng Arrays.toString() chuyển numbers array thành string. In sorted list ra console.
Complexity Review (Phân tích độ phức tạp)
Insertion sort average case complexity O(n^2). Xảy ra khi không element nào sorted.
Best case complexity nếu array đã sorted. Time complexity O(n). Vì inner loop insertion sort không chạy trường hợp này.
Worst case insertion sort O(n^2). Xảy ra nếu array tăng/giảm dần và muốn sắp ngược (tăng→giảm). Sẽ so sánh mọi element với tất cả element khác.
Kết luận
Insertion sorts là phương pháp sắp xếp dữ liệu hiệu quả. Insertion sorts so sánh giá trị bắt đầu từ thứ 2 trong list. Nếu giá trị lớn hơn bên trái, list không đổi. Ngược lại, dịch giá trị cho đến khi item bên trái nhỏ hơn nó.
Bây giờ bạn sẵn sàng viết insertion sort algorithm Java riêng! Tìm thêm tài liệu Java, xem How to Learn Java guide.