SFWRENG 2C03 Study Guide - Midterm Guide: Quicksort, Pseudocode, Merge Sort

• School: McMaster University
• Department: Software Engineering
• Course: SFWRENG 2C03
• Professor: R. Khedri

Document Summary

An algorithm is correct if its output is correct. This can be measured by looking at the loop invariant. Loop invariant: a property that will be true through all iterations; it proves correctness in algorithms; initialization, maintenance, termination; e. g. insertion sort is always sorted on the left side. For a given array, a, loop invariant: a[1: j 1] is going to be sorted. Insertion sort: know the pseudo-code e. g. stack of cards with numbers: 6, 8, 4, 7, 3 j = current card i = previous card key = value at current card. Wc = 8 7 6 4 3 n = # of elements in array. For this course, log2 x = log x = lg x. Better than merge sort for smaller array sizes. It also uses less memory space than merge sort. Auxiliary space: space required to run an algorithm.