1
$\begingroup$

I have the following pseudo code for a insertion sort algorithm

INSERTION-SORT

1 for j = 2 to A.length
2    key = A[j]
3    // Insert A[j] into the sorted sequence A[1..j-1]
4    i = j -1 
5    while i > 0 and A[i] > key
6        A[i+1] = A[i]
7         i = i -1
8    A[i+1] = key

I am trying to convert it into executable code written in Python

def main():
    A = [5,2,4,6,1,3]
    for j in range(1,len(A)):
        key = A[j]
        i = j - 1
        while i >= 0 and A[i] > key:
            A[i + 1] = A[i]
            i = i - 1
        A[i + 1] = key
        print A[0:j+1]
    return A
 
main()

is this a correct translation? I'm not sure if I messed something up with the indexes because it seems as though I'm not getting the end index with range. Furthermore I'm going to be testing correctness with initialization, maintenance and termination.

I added the line print A[0:j] to show initialization and maintenance but I'm not sure if it should be print A[0:j-1].

Any help is greatly appreciated!

Improve this question
$\endgroup$
1
  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. I'm not sure if I messed something up … hard to follow not given any specification. it seems as though I'm not getting the end index with range there are fine manuals about range() and slices. (I seem to remember loop invariant. While programming questions are off-topic here, your question may be about the semantics of Python ranges & slicing, which I'd consider border-line.) $\endgroup$ Commented Feb 14, 2021 at 10:58

1 Answer 1

Reset to default
1
$\begingroup$

Python arrays have 0-based indexing, like in C, and unlike Fortran, which uses 1-based indexing. You can check Wikipedia for information about other languages.

A python array $A$ of length $n$ consists of the elements $A[0],\ldots,A[n-1]$. The python function range(n) goes over the indices $0,\ldots,n-1$, and your range(1,n) goes over the indices $1,\ldots,n-1$.

In insertion sort, we go over all prefixes of the array inductively, and make sure that they are sorted. If $A[0],\ldots,A[j-1]$ is already sorted, in order to make $A[0],\ldots,A[j]$ sorted, we just need to more the current $A[j]$ into its proper location. Since $A[0]$ is automatically sorted, we only need to go over $j=1,j=2,\ldots,j=n-1$, at which point the entire array $A[0],\ldots,A[n-1]$ is sorted. This is why the loop goes over range(1,n).

Is your implementation correct? Practically speaking, the best way to find out is to test it on many inputs. While such a test cannot verify that the algorithm is correct, and could miss some corner cases, it is also likely to catch off-by-one errors, especially in a language like python with bounds checking. Since insertion sort is such a simple algorithm, you are likely to catch any implementation errors by sorting small random arrays.

Improve this answer
$\endgroup$
9
  • $\begingroup$ how can i show using code that the loop invariant is correct with like a print statement? As it seems that A[1..j-1] isnt true for the python version $\endgroup$ Commented Feb 14, 2021 at 12:46
  • $\begingroup$ You can add code that checks that the first $j$ elements are sorted after iteration $j$. $\endgroup$ Commented Feb 14, 2021 at 13:00
  • $\begingroup$ do you have an example of where to place it in the python code? I tried for 2 hours now and i just cant wrap my head around it $\endgroup$ Commented Feb 14, 2021 at 13:15
  • $\begingroup$ Whenever the loop invariance should hold, you can add code that checks that it holds. $\endgroup$ Commented Feb 14, 2021 at 13:16
  • $\begingroup$ thats what i did i think, after every j iteration ends it prints print A[0:j] $\endgroup$ Commented Feb 14, 2021 at 13:28

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.