Insertion Sort (Sắp xếp chèn)
Thuật toán so sánh đơn giản: duyệt trái sang phải, lấy key = phần tử hiện tại, tìm vị trí phù hợp bên trái để chèn. Hiệu quả với mảng nhỏ (low hidden constant), kém hơn heap/merge/quick sort với mảng lớn.
Thuật toán (mảng: 0,-3,5,8,2,7,6)
- Iteration 0: [0,-3,5,8,2,7,6]
- Iteration 1: key=-3 (index 1) < 0 → chèn trước 0 → [-3,0,5,8,2,7,6]
- Iteration 2: key=5, so sánh với -3,0 → đúng vị trí → [-3,0,5,8,2,7,6]
- Iteration 3: key=8, so sánh bên trái → đúng vị trí
- Iteration 4: key=2, chèn giữa 0 và 5 → [-3,0,2,5,8,7,6]
- Cuối cùng: [-3,0,2,5,6,7,8]
Ví dụ code
<html> <head> <script> function iSort(array) { for (var p = 1; p < array.length; p++) { if (array[p] < array[0]){ array.unshift(array.splice(p,1)[0]); } else if (array[p] > array[p-1]){ continue; } else { for (var q = 1; q < p; q++) { if (array[p] > array[q-1] && array[p] < array[q]){ array.splice(q,0,array.splice(p,1)[0]); } } } } return array; } document.write(iSort([0,-3,5,8,2,7,6])); </script> </body> </html>
Kết quả
-3,0,2,5,6,7,8