DAA - Sắp xếp chèn

Sắp xếp chèn là một phương pháp rất đơn giản để sắp xếp các số theo thứ tự tăng dần hoặc giảm dần. Phương pháp này thực hiện theo phương pháp cộng dồn. Nó có thể được so sánh với kỹ thuật làm thế nào các thẻ được sắp xếp tại thời điểm chơi một trò chơi.

Các số, cần được sắp xếp, được gọi là keys. Đây là thuật toán của phương pháp sắp xếp chèn.

Algorithm: Insertion-Sort(A) 
for j = 2 to A.length 
   key = A[j] 
   i = j – 1 
   while i > 0 and A[i] > key 
      A[i + 1] = A[i] 
      i = i -1 
   A[i + 1] = key

Phân tích

Thời gian chạy của thuật toán này phụ thuộc rất nhiều vào đầu vào nhất định.

Nếu các số nhất định được sắp xếp, thuật toán này chạy trong O(n)thời gian. Nếu các số đã cho có thứ tự ngược lại, thuật toán sẽ chạy theoO(n²) thời gian.

Thí dụ

Unsorted list:

2 13 5 18 14

1^st iteration:

Khóa = a [2] = 13

a [1] = 2 <13

Hoán đổi, không hoán đổi

2 13 5 18 14

2^nd iteration:

Khóa = a [3] = 5

a [2] = 13> 5

Hoán đổi 5 và 13

2 5 13 18 14

Tiếp theo, a [1] = 2 <13

Hoán đổi, không hoán đổi

2 5 13 18 14

3^rd iteration:

Khóa = a [4] = 18

a [3] = 13 <18,

a [2] = 5 <18,

a [1] = 2 <18

Hoán đổi, không hoán đổi

2 5 13 18 14

4^th iteration:

Khóa = a [5] = 14

a [4] = 18> 14

Hoán đổi 18 và 14

2 5 13 14 18

Tiếp theo, a [3] = 13 <14,

a [2] = 5 <14,

a [1] = 2 <14

Vì vậy, không có hoán đổi

2 5 13 14 18

Cuối cùng,

the sorted list is

2 5 13 14 18