Không thể sắp xếp chèn từ phần giới thiệu đến thuật toán thứ 3 ed. đúng. Sai lầm suy nghĩ của tôi ở đâu?

Question

Tôi đang làm việc theo cách của mình thông qua cuốn sách Giới thiệu về thuật toán, ấn bản thứ 3. Một trong những điều đầu tiên được giải thích là loại sắp xếp. Trên trang 18 có một số mã giả:

A = {5, 2, 4, 6, 1, 3};

Nó nói rằng mã giả được sử dụng để nó dễ dàng dịch sang bất kỳ loại ngôn ngữ nào (C, C++, Java, chúng không đề cập đến, nhưng tôi cũng đoán C#). Kể từ khi tôi chương trình trong C#, tôi dịch nó trong LinqPad.

int[] a = { 5, 2, 4, 6, 1, 3 }; 

for (var j = 1; j < a.Length; j++) 
{ 
    var key = a[j]; 

    var i = j - 1; 

    while(i > 0 && a[i] > key) 
    { 
     a[i + 1] = a[i]; 
     i--; 
    } 

    a[i + 1] = key; 
} 

a.Dump(); 

Có thể bạn sẽ hỏi, tại sao j bắt đầu ở mức 1 khi nói rõ 2? Trong cuốn sách, mảng có một chỉ số bắt đầu từ 1. Và có, tôi bây giờ tôi có lẽ nên đã cập nhật tất cả các [i - 1] và [i + i] là tốt.

Dù sao, sau khi tôi đã hoàn tất, tôi chạy mã và nhận thấy rằng nó không thực sự sắp xếp chính xác. Đầu ra là { 5, 1, 2, 3, 4, 6 }. Đã muộn và đáng lẽ phải dừng lại, nhưng tôi đã phải vật lộn để làm cho mã đúng. Tôi đã làm tất cả mọi thứ, thậm chí lấy mã giả như là từ cuốn sách (bắt đầu từ 2). Vẫn không có đầu ra chính xác.

tôi đã liên lạc với một trong những giáo sư của cuốn sách, và anh gửi cho tôi mã cho loại chèn, trong C:

void insertion_sort(int *A, int n) { 
    for (int j = 2; j <= n; j++) { 
    int key = A[j]; 
    int i = j-1; 

    while (i > 0 && A[i] > key) { 
     A[i+1] = A[i]; 
     i--; 
    } 

    A[i+1] = key; 
    } 
} 

dịch trong C#:

int [] a = {5 , 2, 4, 6, 1, 3};

for (var j = 2; j <= a.Length; j++) 
{ 
    var key = a[j]; 

    var i = j - 1; 

    while(i > 0 && a[i] > key) 
    { 
     a[i + 1] = a[i]; 
     i--; 
    } 

    a[i + 1] = key; 
} 

Tôi nhận được một mảng ngoài giới hạn. Được rồi, có thể:

int [] a = {5, 2, 4, 6, 1, 3};

for (var j = 2; j <= a.Length - 1; j++) 
{ 
    var key = a[j]; 

    var i = j - 1; 

    while(i > 0 && a[i] > key) 
    { 
     a[i + 1] = a[i]; 
     i--; 
    } 

    a[i + 1] = key; 
} 

Output: {5, 1, 2, 3, 4, 6}

Tôi đang nghĩ, điều này có thể không chính xác. Mã giả nói 2 đến mảng.Length. Có phải là 2 < mảng.Length, hoặc 2 < = array.Length? Chuyện gì đang xảy ra ở đây?

Cá nhân tôi nghĩ rằng đó là do thuộc tính 0 > 0 trong vòng lặp while. Nó thực sự rơi ngắn một lần mỗi lần.

lời giải thích của tôi (từ email của tôi gửi đến các giáo sư, để lười biếng để gõ nó trên tất cả):

Lý do tại sao vòng lặp vẫn kết thúc với { 5, 1, 2, 3, 4, 6 } là vì i > 0 vị. Mỗi lần trong vòng lặp while bạn trừ 1 của i (i--). Điều này cuối cùng sẽ dẫn đến 0 > 0 kết thúc sai (chỉ 0 == 0 sẽ trả về true), nhưng đây là khi vòng lặp vẫn cần chạy thêm một lần nữa. Nó liên tục rơi một đoạn ngắn. Nó sẽ đi làm trong khi vòng lặp 1 thêm thời gian để sắp xếp đúng cách.

Một lời giải thích:

Khi j bắt đầu với 2, phím == 4, i == 1 và a [i] == 2. Vòng lặp while sẽ không chạy trong trường hợp này vì 2> 0 nhưng 2 không lớn hơn 4.

j == 3, key == 6, i == 2, a[i] == 4

Trong khi vòng lặp sẽ không chạy vì 4 là không lớn hơn 6

j == 4, key == 1, i == 3, a[i] == 6

Trong khi vòng lặp chạy thời gian này:

a[i + 1] = a[i] -> a[4] = a[3] -> { 5, 2, 4, 6, 6, 3 } i-- -> i == 2

Một lần nữa trong khi vòng lặp vì 2> 0 và 4> 1

a[i + 1] = a[i] -> a[3] = a[2] -> { 5, 2, 4, 4, 6, 3 } i-- -> i == 1

Một lần nữa trong khi vòng lặp vì 1> 0 và 2> 1

a[i + 1] = a[i] -> a[2] = a[1] -> { 5, 2, 2, 4, 6, 3 } i-- -> i == 0

Và đây là nơi mà nó đi (theo ý kiến ​​của tôi) sai. Bây giờ tôi bằng 0, nhưng vòng lặp while nên chạy thêm một lần nữa để lấy 5 ra khỏi vị trí thứ 0.

Giáo sư đảm bảo với tôi rằng anh ấy đúng, nhưng tôi không thể có được kết quả đúng. Tư duy của tôi đi sai ở đâu?

---

Mảng trong mã C mà giáo sư gửi cho tôi thực sự bắt đầu bằng chỉ mục 1. Tôi không biết điều này và kiểm tra mảng C tôi thấy tất cả bắt đầu bằng 0. Có , sau đó mã C không tạo ra kết quả chính xác. Vị giáo sư đã giải thích điều này với tôi và các mảnh bây giờ rơi vào vị trí của nó.

Answer 1

Tôi nghĩ rằng chuyên gia đang sử dụng ký pháp mảng dựa trên 1, vì vậy với while (i > 0 && a[i] > key), bạn thiếu phần tử [0] trong vòng lặp. Thay đổi mã ban đầu của bạn thành mã này sau đó nó hoạt động:

for (var j = 1; j < a.Length; j++) 
{ 
    var key = a[j]; 

    var i = j - 1; 

    while(i >= 0 && a[i] > key) <----------- Try this, or you'd miss the first number 
    { 
     a[i + 1] = a[i]; 
     i--; 
    } 

    a[i + 1] = key; 
} 

Ngoài ra, nếu bạn muốn sử dụng mã của giáo sư, chỉ cần bỏ qua phần tử thứ 0 ở đó.

Trên ghi chú bên, bạn đã liên hệ với ai? Rivest? Corman? Lần sau tôi bị nhầm lẫn, tôi nghĩ rằng tôi sẽ cố gắng liên lạc với anh ấy, vì có vẻ như giáo sư này trả lời thư :)

Answer 2

Tôi tin rằng đối số của bạn về i>0 là chính xác, bất kể prof là gì. nói. Trong mã giả, vòng lặp là while i > 0 và việc lập chỉ mục mảng bắt đầu bằng 1. Trong C#, việc lập chỉ mục mảng bắt đầu bằng 0, do đó bạn cần có while i >= 0.

Answer 3

Bạn không nên nghĩ đến việc dịch mã giả, nhưng về việc dịch sự hiểu biết của bạn về thuật toán.

Mảng hoàn toàn không được phân loại lúc đầu. Thuật toán hoạt động bằng cách lấy các phần tử chưa phân loại liên tiếp và chèn chúng vào phần đã được sắp xếp. Phần "phần được sắp xếp" bắt đầu là phần tử đầu tiên, được sắp xếp một cách nhỏ gọn. Vì vậy, phần tử đầu tiên chèn vào là giây. Đó là chỉ số của phần tử thứ hai? j của bạn phải bắt đầu từ đó.

Sau đó, i phải đi qua từng chỉ số của các yếu tố được sắp xếp, ngược, cho đến khi tìm thấy vị trí để chèn giá trị hiện tại hoặc hết các phần tử. Vì vậy, nơi nào nó phải bắt đầu, và nơi mà hiện nó phải kết thúc? Hãy cẩn thận rằng nó thực sự nhìn vào từng yếu tố là phải.

Lỗi off-by-one nổi tiếng rất khó phát hiện (và trộn khái niệm mảng dựa trên 1 và 0 chắc chắn không hữu ích), nhưng không chỉ xoay quanh cho đến khi nó hoạt động. Hãy cố gắng hiểu mã số thực sự đang làm gì.

Answer 4

Hãy nhớ rằng: A.length đi từ 0 đến n, vì vậy Độ dài phải là A.Length -1. Tôi đã thực hiện thuật toán này cho sinh viên của tôi bằng C++ bằng tiếng Tây Ban Nha, sử dụng cuốn sách đó. Rất đơn giản để dịch trong C#.

một số dịch để bạn có thể hiểu rõ hơn về

largo = length 
actual = current 
cadena = chain 

void InsertionSort::Sort(char cadena[]) 
{ 
    int largo = strlen(cadena) - 1; 
    char actual = '0'; 
    int i = 0; 

    for (int j = 1; j <= largo; j++) 
    { 
     actual = cadena[j]; 
     i = j - 1; 
     while(i >= 0 && cadena[i] > actual) 
     { 
      cadena[i + 1] = cadena[i]; 
      i--; 
     } 
     cadena[i + 1] = actual; 
    } 
} 

Answer 5

Tôi cũng đã xem qua vấn đề của bạn, và tôi thấy các giải pháp này. Tôi đã mã hóa thuật toán trong java như dưới đây.

int a[] = {5,2,4,3,1}; 
    int key; 
    int i; 
    for(int j = 0; j < 5; j++) 
    { 
     key = a[j]; 
     i = j - 1; 

     while(i>=0 && a[i]>key) 
     { 
      a[i+1]= a[i]; 
      i--; 
     } 
     a[i+1] = key; 

     for(int k=0; k<a.length;k++) 
     { 
      System.out.print(a[k]+" "); 
     } 
    } 

Answer 6

Tôi gặp phải sự cố tương tự. Dưới đây là mã trong C, thực hiện đúng mã giả ở trên. Tôi không sử dụng con trỏ, giống như các giải pháp khác.

Thật vậy, phần phức tạp về điều này là mã giả đang sử dụng ký hiệu mảng dựa trên 1 không giống như hầu hết các ngôn ngữ lập trình!

#include <stdio.h> 

int main(void) 
{ 
    int A[] = { 50, 20, 10, 40, 60, 30 }; 
    int j, key, len, i; 
    len = (sizeof(A))/(sizeof(A[0])); 

    for (j = 1; j < 6; j++) { <-- Change here 
     key = A[j]; 
     // Insert key into the sorted sequence A[1 .. j - 1]. 
     i = j - 1; 
     while (i >= 0 && A[i] > key) { <-- Change here 
      A[i + 1] = A[i]; 
      i--; 
     } 
     A[i + 1] = key; 
    } 

    for (int z = 0; z < len; z++) { 
     printf("%d ", A[z]); 
    } 
    printf("\n"); 
}