Correctness and the Loop Invariant

Sort by

recency

|

195 Discussions

|

  • + 0 comments

    Here is my c++ solution, you can watch the explanation here : https://youtu.be/G0rl1U-fDRY

    void insertionSort(int N, int arr[]) {
        int i,j;
        int value;
        for(i=1;i<N;i++)
        {
            value=arr[i];
            j=i-1;
            while(j>=0 && value<arr[j])
            {
                arr[j+1]=arr[j];
                j=j-1;
            }
            arr[j+1]=value;
        }
        for(j=0;j<N;j++)
        {
            printf("%d",arr[j]);
            printf(" ");
        }
    }
    
  • + 0 comments

    while(j>=0 && value

  • + 0 comments

    java

    public static void insertionSort(int[] A) {

        Arrays.sort(A);
    
        printArray(A);
    

    } }

  • + 0 comments

    Python: Modifying j>0 to j>=0 is the only change.

    def insertion_sort(l):
        for i in range(1, len(l)):
            j = i-1
            key = l[i]
            while (j >= 0) and (l[j] > key):
               l[j+1] = l[j]
               j -= 1
            l[j+1] = key
    
    m = int(input().strip())
    ar = [int(i) for i in input().strip().split()]
    insertion_sort(ar)
    print(" ".join(map(str,ar)))
    
  • + 0 comments

    in java code add = to sign in while loop

    while(j >= 0 && A[j] > value){