Review of loop invariants



Yüklə 42,5 Kb.
tarix17.11.2018
ölçüsü42,5 Kb.
#80054
növüReview


Insertion Sort – review of loop invariants


Insertion Sort

  • Problem: sort n numbers in A[1..n].

  • Input: n, numbers in A

  • Output: A in sorted order:  i  [2..n], A[i-1] <= A[i]



Loop Invariants

  • Invariants – statements about an algorithm that remain valid

  • We must show three things about loop invariants:



Example: Insertion Sort



Example: Insertion Sort

  • Invariant: at the start of each for loop, A[1…j-1] consists of elements originally in A[1…j-1] but in sorted order



Example: Insertion Sort

  • Invariant: at the start of each for loop, A[1…j-1] consists of elements originally in A[1…j-1] but in sorted order



Example: Insertion Sort

  • Invariant: at the start of each for loop, A[1…j-1] consists of elements originally in A[1…j-1] but in sorted order



Yüklə 42,5 Kb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2022
rəhbərliyinə müraciət

    Ana səhifə