Sắp xếp chèn

Sắp xếp chèn (insertion sort) là một thuật toán sắp xếp bắt chước cách sắp xếp quân bài của những người chơi bài. Muốn sắp một bộ bài theo trật tự người chơi bài rút lần lượt từ quân thứ 2, so với các quân đứng trước nó để chèn vào vị trí thích hợp.

Thuật toán

Cơ sở lập luận của sắp xếp chèn có thể mô tả như sau:
Xét danh sách con gồm k phần tử đầu . Với k = 1, danh sách gồm một phần tử đã được sắp. 
Giả sử trong danh sách k-1 phần tử đầu  đã được sắp. Để sắp xếp phần tử  ta tìm vị trí thích hợp của nó trong dãy . Vị trí thích hợp đó là đứng trước phần tử lớn hơn nó và sau phần tử nhỏ hơn hoặc bằng nó.

Ví dụ
Cho danh sách

Danh sách con gồm 3 phần tử bên trái 1,3,7 đã được sắp. Để tiếp tục sắp xếp phần tử thứ tư  vào danh sách con đó, ta tìm vị trí thích hợp của nó là sau 3 và trước 7.

Làm tiếp theo với  ta được

Làm tiếp theo với  ta được

Cuối cùng chèn

Giải thuật
 Danh sách a bắt đầu từ chỉ số 1 tới length
 Procedure insert (array a, int k, value) {
    int i:= k-1;
   while (i > 0 and a[i] > value) {
     a[i+1]:= a[i];
     i:= i - 1;
   }
   a[i+1]:= value;
 }

 Procedure InsertSort (array a, int length) {
   int k:= 2;
   while (k < length) {
     insert(a, k, a[k]);
     k:= k + 1;
   }
 }
// Mã giả viết bằng ngôn ngữ C++

 void InsertSort (int a[],int n)
 {
     int t,j;
     for(int i=1;i<n;i++)
     {
        j=i-1;
        t=a[i];
        while(j >= 0 && t < a[j])
        {
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=t; // Chèn
     }  
 }

Đánh giá 
 Thuật toán sử dụng trung bình n2/4 phép so sánh và n2/4 lần hoán vị, n2/2 phép so sánh và n2/2 lần hoán vị trong trường hợp xấu nhất, n-1 phép so sánh và 0 lần hoán vị trong trường hợp tốt nhất.
 Thuật toán thích hợp đối với mảng đã được sắp xếp một phần hoặc mảng có kích thước nhỏ.

Xem thêm
Sắp xếp nổi bọt
Sắp xếp chọn
Sắp xếp vun đống
Sắp xếp nhanh
Sắp xếp trộn

Tham khảo

 ; also http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.3758; republished? in Theory of Computing Systems Volume 39 Issue 3, June 2006 http://dl.acm.org/citation.cfm?id=1132705
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 2.1: Insertion sort, pp. 15–21.
 Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.2.1: Sorting by Insertion, pp. 80–105.
 , Chapter 8, pp. 95–??

Liên kết

 Binary Insertion Sort - Scoreboard  – Complete Investigation and C Implementation – By JohnPaul Adamovsky
 Insertion Sort in C with demo  - Insertion Sort in C with demo
 Insertion Sort - a comparison with other O(n^2) sorting algorithms
 Animated Sorting Algorithms: Insertion Sort – graphical demonstration and discussion of insertion sort
 Category:Insertion Sort - LiteratePrograms – implementations of insertion sort in various programming languages
 InsertionSort – colored, graphical Java applet that allows experimentation with the initial input and provides statistics
 Sorting Algorithms Demo  – visual demonstrations of sorting algorithms (implemented in Java)
 Insertion sort illustrated explanation. Java and C++ implementations. 

Thuật toán sắp xếp

no:Sorteringsalgoritme#Innstikksortering