Insertion Sort là thuật toán sắp xếp đơn giản, hoạt động bằng cách duyệt từng phần tử của mảng và "chèn" phần tử đó vào đúng vị trí trong phần đã được sắp xếp phía trước nó. Ý tưởng chính như sau:
- Bắt đầu từ phần tử thứ 2 (chỉ số 1), coi phần tử đầu tiên đã được sắp xếp.
- Với mỗi phần tử hiện tại, so sánh với các phần tử đứng trước nó (phần đã sắp xếp).
- Dịch chuyển các phần tử lớn hơn sang phải để tạo chỗ trống.
- Chèn phần tử hiện tại vào đúng vị trí.
- Lặp lại cho đến hết mảng
- Duyệt từ i = 1 đến hết mảng.
- Lưu giá trị arr[i] vào biến tạm (currentValue).
- Duyệt ngược từ j = i - 1 về 0, nếu arr[j] > currentValue thì dịch arr[j] sang phải (arr[j+1] = arr[j]).
- Khi gặp arr[j] <= currentValue hoặc j < 0, chèn currentValue vào arr[j+1].
- Lặp lại cho đến hết mảng.
- Bước 1: i = 1, currentValue = 3. So sánh với 9, dịch 9 sang phải. Chèn 3 vào đầu mảng → [3, 9,1
- Bước 2: i = 2, currentValue = 6. So sánh với 9, dịch 9 sang phải. So sánh với 3, 6 > 3 nên chèn 6 vào vị trí thứ 2 → [3, 6, 9,1
- Tiếp tục các bước tương tự...
Time and space complexity
- TC: O(n^2) (trong trường hợp xấu nhất và trung bình), O(n) (trường hợp tốt nhất khi mảng đã gần như sắp xếp).
- SC: O(1) (sắp xếp tại chỗ, không dùng thêm bộ nhớ ngoài)
1export default function insertionSort(arr: Array<number>): Array<number> {
2 for (let i = 0; i < arr.length; i++) {
3 let curr_value = arr[i];
4 let j = i - 1;
5 while (j >= 0 && arr[j] > curr_value) {
6 arr[j + 1] = arr[j];
7 j--;
8 }
9 arr[j + 1] = curr_value;
10 }
11 return arr;
12}