Sắp xếp chèn (Insertion sort)

Ý tưởng:Duyệt mảng n phần tử. Với mỗi phần tử được duyệt, chuyển nó sang trái cho đến khi nó lớn hơn phần tử bên trái.
Độ phức tạp
    Trường hợp tốt nhất: O(n)
    Trường hợp xấu nhất: O(n²)
    Trường hợp trung bình: O(n²)
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;
  }
}