Sắp xếp chèn (Insertion Sort) sắp xếp dữ liệu bằng cách chèn phần tử như bài tay. Tất cả phần tử sắp xếp từ trái sang phải, coi phần tử đầu đã sắp xếp, chèn các phần tử còn lại vào danh sách đã sắp xếp bên trái. Mỗi phần tử so sánh với các phần tử bên trái cho đến khi chèn vào đúng vị trí.
Thuật toán Insertion Sort
int arr[5] = {5,4,2,1,3};
int i, j;
Duyệt j=i+1 đến size-1
Với mỗi arr[j] so sánh với arr[0..i] cho đến khi arr[i] < arr[j] và arr[i+1] >= arr[j].
Chèn arr[j] vào danh sách, dời các phần tử lớn hơn sang phải.
Kết thúc.
Insertion Sort đệ quy
Nếu độ dài mảng = 1 thì trả về.
Đệ quy sắp xếp phần tử chỉ số 0 đến size-2.
Chèn phần tử cuối vào mảng đã sắp xếp.
Ví dụ
Đầu vào - Arr[] = {5,7,2,3,1,4}, length=6
Đầu ra - Mảng đã sắp xếp: 1 2 3 4 5 7
Giải thích -
5 7 2 3 1 4 → 5 đã sắp xếp 5 7 2 3 1 4 → 7 đúng vị trí 2 5 7 3 1 4 → 2 so sánh 5,7 chèn 2 3 5 7 1 4 → 3 so sánh 5,7 chèn 1 2 3 5 7 4 → 1 so sánh 2,3,5,7 chèn 1 2 3 4 5 7 → 4 so sánh 5,7 chèn
Đầu vào - Arr[] = {1, 2, 3, 3, 2}
Đầu ra - Mảng đã sắp xếp: 1 2 2 3 3
Giải thích -
1, 2, 3, 3, 2 → 1 đã sắp xếp 1, 2, 3, 3, 2 → 2 đúng vị trí 1, 2, 3, 3, 2 → 3 đúng vị trí 1, 2, 3, 3, 2 → 3 đúng vị trí 1, 2, 2, 3, 3 → 2 so sánh 3,3 chèn
Phương pháp sử dụng trong chương trình dưới đây
Trong đệ quy Bubble Sort (lưu ý: mã thực hiện Bubble Sort đệ quy, không phải Insertion Sort), điều kiện dừng là độ dài mảng = 1. Ngược lại duyệt mảng bằng một vòng for, hoán đổi phần tử nếu arr[i] > arr[i+1]. Giảm length 1 vì vòng lặp trước đặt phần tử lớn nhất về cuối. Gọi đệ quy recurbublSort(arr, len).
Nhập mảng Arr[] và length.
Hàm recurbublSort(int arr[], int len) sắp xếp mảng đệ quy bằng Bubble Sort.
Biến temp.
Nếu len == 1 trả về.
Ngược lại for i=0 đến len-2: nếu arr[i] > arr[i+1] hoán đổi.
len = len - 1; đệ quy recurbublSort(arr, len).
Khi len = 1 thoát đệ quy, mảng đã sắp xếp.
In mảng đã sắp xếp trong main.
Ví dụ mã
#include <bits/stdc++.h> using namespace std; void recurbublSort(int arr[], int len){ int temp; if (len == 1){ return; } for (int i=0; i<len-1; i++){ if (arr[i] > arr[i+1]){ temp=arr[i]; arr[i]=arr[i+1]; arr[i+1]=temp; } } len=len-1; recurbublSort(arr, len); } int main(){ int Arr[] = {21, 34, 20, 31, 78, 43, 66}; int length = sizeof(Arr)/sizeof(Arr[0]); recurbublSort(Arr, length); cout<<"Mảng đã sắp xếp : "; for(int i=0;i<length;i++){ cout<<Arr[i]<<" "; } return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Mảng đã sắp xếp : 20 21 31 34 43 66 78