[BorlandC]Hỏi về giải thuật Insertion

[nanosi]

Cho mình hỏi trong giải thuật insertion :

 for(i=0;i<length;i++)
    {
     j=i;

     while(j>0&&a[j]<a[j-1])
     {
      t=a[j-1];
      a[j-1]=a[j];
      a[j]=t;
      j--;
     }
    }

Mình thắc mắc ở chỗ là tại sao trong vòng lặp while lại có điều kiện j>0 vậy , ở đây mình hiểu là cứ mỗi khi bốc một "lá bài" thì lại đem so sánh lá bài ấy với các lá bài đã có sẵn trên tay theo thứ tự từ phải sang trái , nếu lá bài này bé hơn các lá bài có trên tay thì ta đổi chỗ . Có điều nếu như lá bài này đã đến bét nhất rùi ( ô a[0] ) thì nó còn lá bài nào nữa đâu mà so sánh , chẳng lẽ trong mảng có tồn tại ô a[-1] và giá trị của ô này là giá trị rác ư ?

<Xài thẻ CODE plz>

[soda_chanhmuoi]

trong khi j còn lớn hơn 0 mà tức là gặp j=0 thì stop!! khỏi cần làm mấy cái trong while nữa

[nanosi]

à mình muốn hỏi là bây giờ nếu như ta bỏ điều kiện j>0 luôn thì có được không ? nếu ko thì tại sao mong giải thích giùm với .

[huyfeng]

Tôi viết lại giải thuật InsertionSort như sau cho dễ hiểu để giải thích :

void InsertionSort (int * a , int n)
{
int  save; // Biến trung gian lưu lại giá trị phần tử cần chèn
for (int i = 0 ; i < n ; i + +)
	{
	save = a [i]; //Lưu lại phần tử cần chèn thứ i
        //Dịch chuyển cách phần tử trong phần đã sắp xếp sang phải
	for (int j = i ; j  > 0 && save < a [j-1] ; j --)
		a [j] = a [j -1];
		a [j] = save;//Chèn phần tử vào đúng vị trí
	 }
}

Cách tiếp cận thuât toán Insert như sau :

Chia mảng cần sắp xếp thành 2 phần :

- Phần đã được sắp xếp và phần chưa được sắp xếp
- Phần đã sắp xếp ban đầu chỉ 1 phần tử (và chính là phần tử đầu tiên của mảng). Lưu ý phần tử này hông nhất thiết phải là phần tử nhỏ nhất
- Sau đó ta mở rộng phần được sắp xếp bằng cách chọn phần tử nhỏ nhất trong phần chưa được sắp xếp (biến j xuất hiện từ đây)
- Sau đó so sánh phần tử nhỏ nhất vừa lấy trong phần chưa được sắp xếp với phần tử trong phần đã được sắp xếp để sắp thứ tự 2 phần tử này (vì phần được sắp xếp bây giờ đã là 2 phần tử)
....
- Cứ như thế tiếp tục

Thực ra mà nói, ta có thể đặt điều kiện cho biến j>=0 nhưng nếu nó bằng 0 vì ban đầu xét i = 0 (tức mảng được sắp xếp roài) nếu j = 0 nữa hóa ra ta so sánh nó với chính nó. Vậy nghĩa là ít ra phải lấy phần tử kế sau nó (tức phần tử trong phần chưa được sắp xếp) tức j = 1 > 0.

Và thêm 1 điều nữa, nếu j = 0 thì ta phải so sánh với phần tử kế trước nó tức ptử [j-1]. Mà lúc này j = 0 vậy [j - 1] sẽ là phần tử nào. Vì chỉ số mảng trong C++ bắt đầu từ 0 hoặc 1

Từ đó về sau không ai viết là j>=0 nữa mà viết là j>0

Chạy tay :

Giả sử bạn có mảng gồm 3 phần tử sau :

a= 7 1 2
a[0] a[1] a[2]

- Xét i = 0 :

Lưu biến saved = a[0] = 7
xét j = i = 0 nhưng không thỏa điều kiện j >0 nên thoát khỏi vòng lặp for (j ...) ngay.

- Cứ như thế tiếp tục ...

Thân !

[anggon]

Cho mình hỏi trong giải thuật insertion :

for(i=0;i<length;i++)
{
j=i;

while(j>0&&a[j]<a[j-1])
{
t=a[j-1];
a[j-1]=a[j];
a[j]=t;
j--;
}
}

Mình thắc mắc ở chỗ là tại sao trong vòng lặp while lại có điều kiện j>0 vậy , ở đây mình hiểu là cứ mỗi khi bốc một "lá bài" thì lại đem so sánh lá bài ấy với các lá bài đã có sẵn trên tay theo thứ tự từ phải sang trái , nếu lá bài này bé hơn các lá bài có trên tay thì ta đổi chỗ . Có điều nếu như lá bài này đã đến bét nhất rùi ( ô a[0] ) thì nó còn lá bài nào nữa đâu mà so sánh , chẳng lẽ trong mảng có tồn tại ô a[-1] và giá trị của ô này là giá trị rác ư ?

về thuật toán mình thấy huyfeng nói quá rõ rồi chuyện giá trị rác mình nghĩ chắc chắn là có đó bạn về nguyên lí mình không rõ lắm nhưng có lẽ khi bạn cấp phát n phần tử (n vùng nhớ sát nhau+ liên tiếp)cho mảng thì phần tử như ban nói a[-1] nó nằm ngay sau a[0] và đó là một giá trị mà chúng ta chưa xác định được trước các huynh xem đúng ko ạh

[nanosi]

về giải thuật thì mình hiểu rồi , cái thắc mắc chính của mình ở chỗ là có tồn tại phần tử a[-1] ,a[-2],... hay không mà thôi .

[huyfeng]

Theo mình nghĩ thì không tồn tại phần tử a[-1], a[-2]

Thân !

[Xcross87]

# Không có ..và không tồn tại :|
# Trừ khi dùng trong số ảo có tồn tại được phần tử tại vị trí âm nhưng mà xét theo vecto ảo

[shinichi_haha]

về giải thuật thì mình hiểu rồi , cái thắc mắc chính của mình ở chỗ là có tồn tại phần tử a[-1] ,a[-2],... hay không mà thôi .

Vẫn tồn tại nếu thỏa điều kiện giả sử i<0 là phần tử a[i] của một mảng, phần tử a[i] này vẫn tồn tại nếu (a-i) trỏ tới địa chỉ >NULL. (Chú ý mảng vẫn là một contro) tuy nhiên với i<0 phần tử a[i] là một nơi nào đó (có thể là nhân hệ điều hành) do đó việc thay đổi nó sẽ bị ngăn chặn nhưng ta có thể xem nội dung của nó được.

Câu hỏi của cậu rất hay!

[soda_chanhmuoi]

Có tồn tại, giải thuật sắp xếp chèn trực tiếp lính canh dùng phần tử a[-1] để làm lính canh đó thôi!!

void chenTrucTiepLC( long a[], long n)
{
	long j;
	long x;
	for(long i=1;i<n;i++)
	{
		x=a[i];
		j=i-1;
		while(a[j]>x )
		{
			a[-1]=x;
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=x;
	}
}

tiết kiệm 1 phép so sánh trong while(j>0&&a[j]<a[j-1]) bù lại vẫn phải tốn thêm phép gán a[-1]=x, mình nghĩ ý đồ của bạn là gợi mở ra cái này ah?