NỘI DUNG BÀI VIẾT
Hôm nay chúng ta sẽ tìm hiểu về Insertion Sort trong Java. Insertion sort tương tự như Bubble sort và trong bài này, chúng ta sẽ tìm hiểu thuật toán sắp xếp chèn, ví dụ và sau đó viết code java sắp xếp chèn để sắp xếp mảng số nguyên.
Insertion Sort trong Java
- Sắp xếp chèn trong Java, chúng ta so sánh giá trị tại bất kỳ chỉ mục nào từ tất cả các phần tử trước đó cho đến khi tất cả các giá trị nhỏ hơn được tìm thấy.
- Sau đó, chúng ta đặt giá trị tại chỉ mục mà trước đó không có giá trị nào nhỏ hơn.
- Hai bước trên được thực hiện lặp đi lặp lại đến chỉ mục cuối cùng, cuối cùng chúng ta có một mảng số nguyên đã được sắp xếp.
Ví dụ về thuật toán sắp xếp chèn
Hãy cùng tìm hiểu thuật toán sắp xếp chèn bằng một ví dụ. Giả sử chúng ta có một mảng chưa được sắp xếp [5, 4, 14, 2, 8].
- Lặp lại chỉ mục thứ nhất: giá trị ở chỉ số thứ nhất = 4, nhỏ hơn 5, vì vậy mảng trở thành [5, 5, 14, 2, 8], khi chúng ta bắt đầu, chúng ta đặt giá trị ở chỉ số thứ 0 và mảng trở thành [4, 5, 14, 2, 8]
- Lặp lại chỉ mục thứ 2: giá trị tại chỉ mục thứ 2 = 14 lớn hơn 5, vì vậy hãy để nguyên mảng. Bây giờ mảng = [4, 5, 14, 2, 8]
- Lặp lại chỉ mục thứ 3: giá trị tại chỉ mục thứ 3 = 2 nhỏ hơn 14, vì vậy mảng trở thành [4, 5, 14, 14, 8], một lần nữa 2 nhỏ hơn 5, vì vậy mảng trở thành [4, 5, 5, 14, 8]. Một lần nữa 2 nhỏ hơn 4, do đó mảng trở thành [4, 4, 5, 14, 8]. Khi chúng ta đến đầu mảng, chúng ta đặt 2 ở chỉ số 0 và mảng trở thành [2, 4, 5, 14, 8]
- Lần lặp chỉ mục thứ 4: giá trị ở chỉ số thứ 4 = 8, vì vậy mảng trở thành [2, 4, 5, 14, 14], sau đó 8 lớn hơn 5, vì vậy hãy đặt 8 ở vị trí thứ 14 và mảng trở thành [2, 4, 5, 8, 14]. Và mảng của chúng ta đã được sắp xếp.
Các điểm chính cần nhớ khi thực thi sắp xếp chèn trong chương trình Java:
- Bắt đầu với phần tử thứ 2 đến phần tử cuối cùng của mảng, vì vậy hãy sử dụng vòng lặp for.
- Lưu trữ giá trị vào một biến khác để tránh nó bị mất khi chúng ta thay đổi giá trị chỉ mục ở giữa.
- Chúng ta cần tiếp tục thay đổi các giá trị cho đến khi chúng ta ở chỉ mục thứ 0 hoặc chúng ta thấy giá trị trước đó lớn hơn, vì vậy chúng ta có thể sử dụng vòng lặp while cho việc này.
Ví dụ:
import java.util.Arrays;
public class InsertionSort {
public static void main(String[] args) {
int A[] = new int[10];
populateArray(A);
System.out.println("Before Sorting: ");
printArray(A);
// sort the array
insertionSort(A);
System.out.println("\nAfter Sorting: ");
printArray(A);
}
/**
* This method will sort the integer array using insertion sort in java algorithm
*
* @param arr
*/
private static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int valueToSort = arr[i];
int j = i;
while (j > 0 && arr[j - 1] > valueToSort) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = valueToSort;
}
}
public static void printArray(int[] B) {
System.out.println(Arrays.toString(B));
}
public static void populateArray(int[] B) {
for (int i = 0; i < B.length; i++) {
B[i] = (int) (Math.random() * 100);
}
}
}
Code language: JavaScript (javascript)Output
Before Sorting:
[57, 90, 80, 48, 35, 91, 1, 83, 32, 53]
After Sorting:
[1, 32, 35, 48, 53, 57, 80, 83, 90, 91]Code language: CSS (css)Độ phức tạp của thuật toán Insertion Sort
Độ phức tạp của sắp xếp chèn là O (n) cho trường hợp tốt nhất (mảng đã được sắp xếp) và O (n2) cho trường hợp xấu nhất (sắp xếp theo thứ tự ngược lại).
Insertion Sort trong Java là một lựa chọn tốt cho mảng có kích thước nhỏ và khi bạn biết rằng các giá trị sẽ được sắp xếp chủ yếu. Ví dụ: sắp xếp một mảng có kích thước 100 trong đó bạn biết rằng tất cả các giá trị sẽ nằm trong khoảng từ 1 đến 10.
Trên đây là tất cả những gì về Insertion sort trong Java.
Happy learning!!!
