Thuật toán Insertion Sort (lý thuyết)

Ý tưởng thuật toán: xét dãy n phần tử a[0], a[1], a[2] ,..., a[n-1].
- Xem dãy gồm 1 phần tử a[0] là dãy có thứ tự.

- Thêm a[1] vào dãy có thứ tự a[0] sao cho dãy mới a[0], a[1] là dãy có thứ tự. Nếu a[1] < a[0] ta đổi chỗ a[1] với a[0].
- Thêm a[2] vào dãy có thứ tự a[0], a[1] sao cho dãy mới a[0], a[1], a[2] là dãy có thứ tự.
- Tương tự, tiếp tục như thế đến n – 1 bước ta sẽ có dãy có thứ tự.

Ví dụ: sử dụng thuật toán Insertion Sort sắp xếp dãy {3,7,22,3,1,5,8,4,3,9} theo thứ tự tăng dần.

Kết quả sau khi đã thực hiện thuật toán: {1,3,3,3,4,5,7,9,22}

Tải Code sắp xếp xen được viết bằng ngôn ngữ C++ trên Code::Blocks 10.05:  
CODE SẮP XẾP XEN DẠNG CHẠY RA KẾT QUẢ
CODE SẮP XẾP XEN DẠNG CHẠY RA TỪNG BƯỚC