# Các giải thuật sắp xếp - P2: Insertion
**1. Insertion sort**
Insertion sort hoạt động bằng cách iterate qua mỗi phần tử trong mảng, sau đó tìm vị trí phù hợp cho phần tử đó, và "chèn" phần tử đó vào vị trí.
Mã giả:

function InsertionSort(array):
    n = length(array)

    for i from 1 to n - 1:
        key = array[i]       // Current element to be compared
        j = i - 1            // Index of the previous element

        // Move elements of array[0..i-1], that are greater than key, to one position ahead
        // of their current position
        while j >= 0 and array[j] > key:
            array[j + 1] = array[j] 
            j = j - 1

        array[j + 1] = key   // Place the key element at its correct position

    return array

Độ phức tạp:
Worst time complexity: n^2
Best time complexity: n
Average time complexity: n^2

**2. Binary insertion sort**

Dễ thấy, việc tìm kiếm vị trí phù hợp cho phần tử a[i] có thể được giải quyết bằng cách chặt nhị phân (i.e. tìm ra vị trí của phần tử nhỏ nhất lớn hơn a[i]).

Mã giả:

function BinaryInsertionSort(array):
    n = length(array)

    for i from 1 to n - 1:
        key = array[i]              // Current element to be compared
        left = 0                    // Left pointer for binary search
        right = i - 1               // Right pointer for binary search

        // Binary search to find the correct position for key
        while left <= right:
            mid = (left + right) / 2     // Calculate the middle index
            if array[mid] > key:
                right = mid - 1          // Adjust the right pointer
            else:
                left = mid + 1           // Adjust the left pointer
        
        // Shift elements to the right to make space for key
        for j from i down to left + 1:
            array[j] = array[j - 1]

        array[left] = key           // Place the key element at its correct position

    return array

Việc sử dụng binary search để tìm vị trí cho key giúp độ phức tạp trong việc tìm vị trí từ O(n) giảm xuống O(logn). Tuy nhiên, tổng quát, độ phức tạp của Binary insertion sort vẫn còn cao, nên không áp dụng được với mảng có kích thước lớn.
Độ phức tạp:
Worst time complexity: n^2
Best time complexity: n
Average time complexity: n^2

**3. Shell sort**

Một cách khác để cải tiến insertion sort đó là giảm khoảng cách giữa các phần tử có giá trị gần nhau nhưng ở vị trí xa nhau. Ý tưởng của shell sort là chọn ra một khoảng cách (gap) g. Sau đó, mảng sẽ được chia lại thành các mảng con, mà các phần tử trong mảng con cách xa nhau g đơn vị ở trên mảng gốc. Insertion sort các mảng con đó, sau đó giảm g và tiếp tục lặp lại như trên

Mã giả:

function ShellSort(array):
    n = length(array)
    gap = n / 2   // Initialize the gap size

    // Start with a large gap, then reduce the gap
    while gap > 0:
        // Do a gapped insertion sort for this gap size
        for i from gap to n - 1:
            temp = array[i]
            j = i

            // Shift earlier gap-sorted elements until the correct location for array[i] is found
            while j >= gap and array[j - gap] > temp:
                array[j] = array[j - gap]
                j = j - gap

            // Insert the element at its correct position
            array[j] = temp

        gap = gap / 2  // Reduce the gap size

    return array

Độ phức tạp:
Worst time complexity: n^3/2
Best time complexity: nlogn
Average time complexity: n^4/3