Độ phức tạp
Trường hợp tốt nhất: O(n)
Trường hợp xấu nhất: O(n2)
Trường hợp trung bình: O(n2)
Thuật toán
- Input: Mảng arr gồm n phần tử không có thứ tự
- Output: Mảng arr gồm n phần tử có thự tự (trong trường hợp này là thứ tự tăng dần)
Mã giả
Function insertion_sort(array arr, integer arr_size)
{
integer i = 2;
while(i <= arr_size)
{
value = arr[i];
integer k = i;
while(k > 1 and arr[k - 1] > value)
{
arr[k] = arr[k - 1];
k = k - 1;
}
arr[k] = value;
i = i + 1;
}
return arr;
}C/C++ code
void insert_sort(int arr[], int arr_size)
{
for(int i = 1; i < arr_size; i++)
{
int value = arr[i];
int k = i;
while(k > 0 && arr[k - 1] > value)
{
arr[k] = arr[k - 1];
k--;
}
arr[k] = value;
}
}Java codeprivate static void insertion_sort(int arr[])
{
int arr_size = arr.length;
for(int i = 1; i < arr_size; i++)
{
int value = arr[i];
int k = i;
while(k > 0 && arr[k - 1] > value)
{
arr[k] = arr[k - 1];
k--;
}
arr[k] = value;
}
}
