Thuật toán insertion sort

#1

đây là thuật toán insertion sort mình thấy trên mạng
ai 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;
}
}

#2

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

#3

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.

#4

(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.

#5

Đơn giản vầy thôi :smile:
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 :wink:

1 Like
#6

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

1 Like
#7

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

1 Like
#8

tks b. mình hiểu r :slight_smile:

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?