Insertion sort
June 24, 2025
04:33 AM
No headings found
Loading content...
Related Posts
Theory Data Structure And Algorithms
No headings found
Related Posts
Theory Data Structure And Algorithms
Approach
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:
Các bước cụ thể:
Ví dụ minh họa:
Giả sử mảng: [9, 3,1
Time and space complexity
Solution
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}