Thuật Toán Sắp xếp chèn ( Insertion Sort )

* ý tưởng của bài toán : 
- lần lượt chọn các phần tử A[i] trong mảng A sau đó so sánh lần lượt với các giá trị từ A[i] -> A[0], nếu trong khoảng từ A[i]-> A[0] (" gọi tắt A[k] là phần tử trong khoảng này ")có giá trị nào nhỏ hơn giá trị đang chọn thì chuyển sang chọn phần tử kế tiếp A[i+1] nếu ngược lại thì ta đẩy dần phần tử A[k] đấy lên vị trí k+1 .

* Ví Dụ :
mảng A = {3, 6, 2, 1, 5};

* code :

#include <iostream>

#define Max 100

using namespace std; 

// nhập mảng 

void Nhap (int A[],int &n){

cout << "Nhap n : "; 

cin >> n;

for (int i = 0; i<n; i++){

cout << "A["<< i <<"] = ";

cin >> A[i]; 

}

}

// thuật toán 

void Insertion_Sort (int A[], int n){

for (int i = 1 ; i<n; i++ ){

int temp = A[i]; 

int j = i-1; 

while (temp < A[j] && j>=0){

if (A[j] > temp){

A[j+1] = A[j]; 

j--; 

}

}

A[j+1] = temp; 

}

}

// xuất mảng 

void Xuat (int A[],int n){

cout << " Mang dk sx lai nhu sau : "; 

for (int i = 0; i<n; i++ ){

cout << A[i] << " ";  

}

}

// MAIN 

int main (){

int A[Max], n = 0; 

Nhap (A,n);

Insertion_Sort(A,n);  

Xuat (A,n);

return 0; 

}