Pseudocode: We use a procedure INSERTION-SORT. Takes as parameters an array A[1

Question

Pseudocode: We use a procedure INSERTION-SORT.

Takes as parameters an array A[1 . . n] and the length n of the array.

• As in Pascal, we use ". ." to denote a range within an array.

• The array A is sorted in place: the numbers are rearranged within the array, with at most a constant number outside the array at any time.

What does it mean to "with at most a constant number outside the array at any time"?

INSERTION-SORT(A)

for j ? 2 to n

do key ? A[j]

while i > 0  and A[i] > key

  do A[i + 1] ? A[i]

i  ? i ? 1

A[i + 1] ? key

Correctness: We often use a loop invariant to help us understand why an algorithm gives the correct answer.

Here ís the loop invariant for INSERTION-SORT:

Loop invariant: At the start of each iteration of the "outer" for loop -- the loop indexed by j -- the subarray A[1 . . j ?1] consists of the elements originally in A[1 . . j ? 1] but in sorted order.

To use a loop invariant to prove correctness, we must show three things about it:

Initialization: It is true prior to the first iteration of the loop.

Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.

Termination: When the loop terminates, the invariant --usually along with the reason that the loop terminated -- gives us a useful property that helps show that the algorithm is correct.

Using loop invariants is like mathematical induction. How so? I don't understand this point. Also, please explain more detail how we can use a loop invariant to prove correctness.

Explanation / Answer

Hello,

There are two types of sorting algorithm [according the extra space they needed to sort an array]

In-place algorithm and out-of-place algorithm. Insertion sort follows in-place sorting algorithm . ie it will not take any extra space to sort the elements so the space complexity will be O(1). Thats why you they said 'with at most a constant number outside the array at any time'.

2. i <- i+1

when the symbol '<-' is used, It means that the value of I is assigned to i+1. To be more simple [i=i+1] is the meaning of that line.

3. When the condition of the 'while loop' gets failed the entire loop will be terminated. This helps us to stop the algorithm when the list gets sorted . Each and every time initial subarray part of the orginal array will be sorted in Insertion sort. so at the end we get the array sorted on whole.

Hope, I have cleared all your doubt. :)

Thank you :).

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.