0
$\begingroup$

So I'm trying to implement an insertion sort algorithms based on page 18 Cormen psuedocode but I'm confused by for j = 2 to A:length. Specifically, what does the j=2 mean? I'm implementing it using the below python code and it only works when the range is the entire length of the array:

def insertion_sort(arr):
    # length of array
    n = len(arr)

    # traverse through array
    for i in range(n):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

Could someone explain?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Most of us probably don't have a copy of Cormen page 18, and it's probably not possible to answer this question without context from what is in the book. Can you transcribe the pseudocode you are looking at? I don't know how to answer "what does j=2 mean?" -- it is presumably a line of code that you are supposed to implement. I don't know how to answer questions about the meaning of a line of code; it just is whatever it is. $\endgroup$ Commented May 7, 2021 at 1:50
  • $\begingroup$ One thing to find out is whether "CLRS" assume A one- or zero-based. $\endgroup$ Commented May 8, 2021 at 3:54

1 Answer 1

Reset to default
1
$\begingroup$

The following two points might clear your confusion.

  1. The pseudocode in the book is following $1$ based indexing. Your code is following $0$ based indexing.

  2. Your code is technically doing nothing in the first iteration of the while loop. In the first iteration $i = 0$, therefore $j = -1$. Since $j<0$, the inside while loop is not executed. And it keeps $A[0] = key$ to its original value. Effectively, your code starts executing from $i = 1$, which is equivalent to $j = 2$ in CLRS implementation.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.