Sắp xếp chèn

Sắp xếp chèn cũng là một kỹ thuật sắp xếp có độ phức tạp thời gian là O(n²), nhưng được tối ưu hơn một chút so với sắp xếp nổi bọt.

Trong thuật toán này, mảng được chia thành hai phần. Một phần đã được sắp xếp, phần còn lại chưa được sắp xếp. Ta chọn một phần tử từ mảng chưa được sắp xếp và đưa nó vào mảng đã được sắp xếp tại vị trí chính xác.

Ta lặp lại quy trình này cho đến khi tất cả các phần tử được sắp xếp.

1. Giả sử ta có một mảng {8,4,1,5}. Xem phần tử đầu tiên là đã được sắp xếp, còn tất cả phần tử khác chưa được sắp xếp. Ban đầu, phần tử ở chỉ số 0 được xem là đã được sắp xếp.

2. Tạo một biến tạm và gán phần tử thứ (i) vào đó (ở đây là 4). So sánh biến tạm với mảng đã được sắp xếp hiện tại, lúc này chỉ có 8. Vì 4<8, dịch các phần tử của mảng đã được sắp xếp sang phải cho đến khi 4 nằm đúng vị trí. Trong trường hợp này, cần dịch 8 một lần. Lúc này, độ dài của mảng đã được sắp xếp là 2.

3. Ta lặp lại quy trình cho đến khi toàn bộ mảng được sắp xếp.

for(int i=1;i<n;i++){           //Bắt đầu từ phần tử đầu tiên vì ta coi phần tử thứ 0 đã được sắp xếp
    int temp=arr[i];
    
    int j=i-1;                  //Kiểm tra tất cả phần tử ở bên trái nó 
    
    while(arr[j]>temp && j>=0){ //Dịch các phần tử sang phải khi chúng lớn hơn temp, cho đến phần tử đầu tiên
      arr[j+1]=arr[j];          //Dịch phần tử sang phải một vị trí
      j--;                      
    }
    
    arr[j+1]=temp;              //Đặt temp vào đúng vị trí
  
}

Để hình dung cách hoạt động của sắp xếp chèn

Công cụ trực quan hóa sắp xếp chèn