Sắp xếp chèn, rất mong mọi người giúp đỡ

[manutd1988]

Sắp xếp chèn mình ko hiểu mong mọi người giải thích giùm

 int index,i,j;  for (i=1; i < array_size; i++)  {    index = numbers[i];        for(j=i ; j > 0 && (numbers[j-1] > index) ; j=j-1)    {      numbers[j] = numbers[j-1];    }    numbers[j] = index;

Cảm ơn mọi người

[Xcross87]

Ví dụ : cho mảng : 4 2 7 ..sắp xếp bé tới lớn

Cho i = 1 ; number[1] = 2 = index ;
         Cho j = i
               Chọn j = 1 ; nếu number[0] = 4 > 2 = index và j - 1 = 1 - 1 = 0
                        Thì đổi chỗ index và number [0];
                        =>>> number[0] = 2 
               Quay về : trả lại cho number[1] giá trị 4 => number[1] = 4;
=> có dãy : 2 4 7

Cứ thế tiép tục sắp .

[manutd1988]

Cảm ơn anh Peter 87 nhiều

Nhưng anh có thể nói rõ hơn được ko ?

Thank

[neverland87]

Cảm ơn anh Peter 87 nhiều

Nhưng anh có thể nói rõ hơn được ko ?

Thank

Đoạn code trên dùng để sắp xếp 1 mảng số dựa theo giải thuật Insertion Sort nè. Neverland nhớ hồi trước bạn đã từng hỏi về giải thuật này rồi mà.
Muốn hiểu đoạn code trên ra sao, bạn hãy tự viết ra giấy 1 dãy số bất kỳ, sau đó chạy bằng tay (nhẩm trong đầu) đoạn code trên, lúc đó bạn sẽ hiểu ngay!
Lời giải thích của pete cũng dễ hiểu mà.

[hikaru007]

Theo mình thì thuật toán trên có thể viết như sau:

int index,i,j;
for(i=0;i<array_size;i++)
    for(j=i+1;j<array_size;j++)
          if(number[i]<number[j]) 
               { index=number[i];number[i]=number[j];number[j]=index;} 

Có thể giải thích thuật toán như sau:

VD luôn mảng 4 2 7...
Xét vòng lặp đầu tiên thì number[i]=number[0]=4,number[j=i+1]=number[1]=2,
ta thấy number[i]<number[j] nên đổi chỗ 2 phần tử này.
Dùng biến index giống biến trung gian (để nhận giá trị tạm thời ) 
để đổi chỗ number[i] và number[j].Ta có đoạn code 
{ index=number[i];number[i]=number[j];number[j]=index;}
Sau lần đổi chỗ nầy thì number[0]nhận giá trị nhỏ nhất trong 2 phần tử đầu.
Tiếp tục thực hiện vòng lặp để so sánh number[0] (hiện tại ) 
với các phần tử khác (j=i+1) đến hết mảng.
Sau j<array_size lần thực hiện thì number[0] sẽ là phần tử bé nhất trong mảng.
Đến vòng lặp lớn tiếp theo thì xét đến number[1] và tìm ra 
phần tử bé thứ 2 trong mảng.cứ như vậy cho đến hết.

Thuật toán này đơn giản nên mình hi vọng là bạn đã hiểu.

[manutd1988]

Cảm ơn các bạn nhiều nhé , các bạn rất nhiệt tình giúp đỡ , Thank

[neverland87]

Theo mình thì thuật toán trên có thể viết như sau:

int index,i,j;
for(i=0;i<array_size;i++)
    for(j=i+1;j<array_size;j++)
          if(number[i]<number[j]) 
               { index=number[i];number[i]=number[j];number[j]=index;} 

Đoạn code trên của bạn dùng để sắp xếp mảng theo giải thuật Bubble Sort, trong khi đoạn code mà bạn manutd1988 đã post lúc đầu dùng để sắp xếp mảng theo giải thuật Insertion Sort. Do đó nó không hề tương đồng.
Và đây là đoạn code tương đồng:

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

[kidkid]

Đúng rồi cái trên của hikaru là buble sort , còn bạn MU thì đang hỏi về insert sort ý tưởng của nó giống như MU chơi bài tiến lên vậy , bắt từng cây lên và sắp xếp nó theo 1 trật tự nào đó , cây tiếp theo sẽ phải kiểm tra nó cần ở vị trí nào để thỏa trật tự đó sau đó chèn vào . MU hiểu chưa ?

[hikaru007]

Cám ơn các bạn KidKid Và Neverland87 vì các bạn giúp mình hiểu hơn về thuật toán của bài này.Trước giờ mình vẫn nhầm lẫn nó là một.Nhưng mà các bạn có thể nói rõ về chức năng của nó không?
Vì mỗi thuật toán có ưu điểm riêng nên mình cần biết sử dụng thuật toán khi nào thì hợp lí nhất và ưu việt nhất.Thank!