CMPSC 24 Lecture Notes - Lecture 1: Insertion Sort, The Algorithm
Document Summary
Programs: implementation of the algorithm in some programming language. Data structures/abstract data types: organization of data/information involved in solving the problem. Many number of possible ways to solve a problem. Efficient time space running time of an algorithm with respect to the size of the input (n for size of input) Too much work to implement all these algorithms. Want to develop a methodology about algorithm efficiency, without implementation should rely on high level description instead of programming implementation. Pseudocode: mix of natural language and high-level programming concepts. More structured than prose, but less formal than a programming language. = for boolean equals (==) if then else repeat until while for . Account for all possible inputs (size + distribution) insensitive to underlying hardware/software. Correctness: a < b < c and permutation of the input sequence. Insertion sort algorithm for j=2 to n do key = a[j] i = j-1 while (i > 0 and a[i] > key) do.