Thuật toán insertion sort

đây là link mình đọc

STDIO

Insertion Sort :: Bài viết :: STDIO

Trong bài viết này, tôi sẽ tiếp tục giới thiệu và hiện thực thuật toán sắp xếp khác là Insertion Sort - sắp xếp chèn. Trong phạm vi bài viết, tôi chỉ hiện thực việc sắp xếp tăng dần, bạn có thể làm tương tự cho việc sắp xếp giảm dần và tôi sử dụng...

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.

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. 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 a 1 , . . . , a ...

đây là thuật toán insertion sort mình thấy trên mạngai giải thích cho mình vs( a[], n, j là gì…) mình ms học nên k hiểu

void InsertionSort(int a[], int n){ for (int i = 1; i < n; i++) { int x = a[i]; int j = i; while (j > 0 && a[j - 1] > x) { a[j] = a[j - 1]; j--; } a[j] = x; }}

(a[],n) là đối số của hàm, dùng để trao đổi dữ liệu với hàm khác khi có lời gọi hàm.
j đơn giản là biến cục bộ kiểu int của hàm thôi.

Đơn giản vầy thôi
Bạn có một mảng chứa hầm bà lằng.

unsortedArray -> [1][9][6][2][3][6][9][0][5][4]

Bạn lấy [T] là một biến chứa thằng cuối cùng của phần mảng đã sắp xếp (bắt đầu sẽ là thằng unsortedArray[0]) và một biến /P/ làm vị trí (ngay sau thằng [T])
Sau đó bạn xét: Nếu thằng ở /P/ mà nhỏ hơn [T] thì bạn tạo một khoảng nhỏ để nhét thằng [P] vào sau [T]

[1][9][6][2][3][6][....  -> đùn nhau ra
       
[1] [ ... ] [9][6][2][3][...

      / <----- \
[1] [ ... ] [9][6][2][3][...

[1][6][9][2][3][...

Như vậy th.
Trong đoạn

for (int i = 1; i < n; i++)  //việc sắp xếp
{
int x = a[i];   // đây là [T]
int j = i;     // đây là /P/
while (j > 0 && a[j - 1] > x)  //đùn nhau ra để tạo khoảng trống
{
   a[j] = a[j - 1]; //lấp khoảng trống
   j--;
}
   a[j] = x;
}

Có gì chưa hiểu cứ reply

Bạn lấy [T] là một biến chứa thằng cuối cùng của phần mảng đã sắp xếp (bắt đầu sẽ là thằng unsortedArray[0]) và một biến /P/ làm vị trí (ngay sau thằng [T])

đoạn này là sao b
mình vẫn chưa hiểu :’(

là vầy này bạn:

   /P/ -> /P/ = 1 // /P/ chứa vị trí
    |
    V
 0  1  2  3  4  5  ...  <- vị trí trong mảng
[1][9][6][2][3][6][.... <- dữ liệu trong mảng
 ^
 |
[T] -> [T] = 1 //[T] chứa dữ liệu

và /P/ - vị_trí ( [ T ] ) -> 1 vì P sẽ luôn đi trước T

tks b. mình hiểu r