Insertion Sort là một trong những thuật toán sắp xếp được sử dụng để sắp xếp dữ liệu bằng cách chèn các phần tử giống như một bộ bài. Tất cả các phần tử được sắp xếp từ trái sang phải, sau đó xem xét phần tử đầu tiên là đã được sắp xếp, hãy chèn phần còn lại vào danh sách đã sắp xếp ở bên trái. Mỗi phần tử được so sánh với mỗi phần tử trong danh sách bên trái cho đến khi nó được chèn vào đúng vị trí của nó.
Thuật toán sắp xếp chèn
-
int arr [5] ={5,4,2,1,3};
-
int i, j;
-
Chuyển từ chỉ mục j =i + 1 sang j
-
Đối với mỗi phần tử arr [j], hãy so sánh nó với các phần tử trong danh sách arr [0 đến i] cho đến khi tìm thấy phần tử sao cho arr [i]
=arr [j]. -
Đặt arr [j] trong danh sách và di chuyển tất cả các phần tử lớn hơn sang phải một vị trí.
-
Kết thúc
Sắp xếp chèn đệ quy
-
Nếu độ dài mảng là 1 thì trả về.
-
Sắp xếp đệ quy các phần tử ở chỉ số 0 đến kích thước mảng-1
-
Chèn phần tử cuối cùng vào mảng đã sắp xếp
Ví dụ
Đầu vào - Arr [] ={5,7,2,3,1,4}; chiều dài =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 already sorted 5 7 2 3 1 4 → 7 at correct place 2 5 7 3 1 4 → 2 compared with 5,7 and inserted 2 3 5 7 1 4 → 3 compared with 5,7 and inserted 1 2 3 5 7 4 → 1 compared with 2,3,5,7 and inserted 1 2 3 4 5 7 → 4 compared with 5,7 and inserted
Đầ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 already sorted 1, 2, 3, 3, 2 → 2 at correct place 1, 2, 3, 3, 2 → 3 at correct place 1, 2, 3, 3, 2 → 3 at correct place 1, 2, 2, 3, 3 → 2 compared with 3,3 and inserted
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Trong cách tiếp cận đệ quy của sắp xếp bong bóng, trường hợp cơ sở là độ dài mảng =1. Nếu không, hãy duyệt qua mảng bằng cách sử dụng vòng lặp for đơn và hoán đổi các phần tử cho phù hợp.
-
Lấy mảng đầu vào Arr [] và độ dài là số phần tử trong đó.
-
Hàm recurbublSort (int arr [], int len) nhận mảng và độ dài của nó và sắp xếp đệ quy mảng bằng cách sử dụng sắp xếp bong bóng.
-
Thực hiện một nhiệt độ thay đổi.
-
Nếu độ dài mảng là 1 thì trả về void.
-
Khác lướt qua mảng bằng vòng lặp for đơn và đối với mỗi phần tử arr [i]> arr [i + 1], hãy hoán đổi các phần tử đó.
-
Đặt temp =arr [i], arr [i] =arr [i + 1] và arr [i + 1] =temp.
-
Bây giờ độ dài giảm đi 1 khi vòng lặp trước đặt phần tử lớn nhất ở vị trí cuối cùng.
-
Thực hiện lệnh gọi đệ quy tới recurbublSort (arr, len).
-
Khi kết thúc tất cả các lệnh gọi, khi len trở thành 1, chúng ta sẽ thoát ra khỏi đệ quy và mảng sẽ được sắp xếp.
-
In mảng đã sắp xếp bên trong main.
Ví dụ
#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<<"Sorted array : ";
for(int i=0;i<length;i++){
cout<<Arr[i]<<" ";
}
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau
Sorted array : 20 21 31 34 43 66 78