[Wiki] Sort cơ bản 1 - Insert Sort - Sắp xếp chèn

Ngồi rảnh rảnh nghiên cứu lại giải thuật đã bỏ từ lâu. Bắt đầu với Insert sort.

Hình ảnh minh họa:

Coi video này để lấy ý tưởng về Insert sort
Video 1:

Video 2:

Code lại bằng C

#include <stdio.h>

int main()
{
    int length = 5;
    int array[] = {5,2,4,3,1};
    for(int unsorted_id = 1; unsorted_id < length; unsorted_id++) {
        int element = array[unsorted_id];
        int sorted_id = unsorted_id - 1;
        while(sorted_id >= 0 && element > array[sorted_id]) {
            array[sorted_id+1] = array[sorted_id]; // shift
            sorted_id--;
        }
        array[sorted_id+1] = element; // insert
    }

    //output
for(int i = 0; i < length; ++i)
    printf("%d ", array[i]);
return 0;
}

Độ phức tạp O(n2)