Độ 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 code
private 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; } }
No comments:
Post a Comment