COMP 250 Lecture Notes - Lecture 5: Insertion Sort, Sorting Algorithm

• School: McGill University
• Department: Computer Science (Sci)
• Course: COMP 250
• Professor: Claude Crepeau

Document Summary

Lecture #5: the insertion sort algorithm and intro to linked lists. A sorting algorithm has an input of an array a[] with n elements that can be compared against each other, and produces an output array whose elements are organized in increasing order. For k=1 to n-1 do: tmp a[k, i k, while (i>0) & (tmp < a[i-1]) do. A[i] a [i-1] i i-1: end while, a[i] = tmp. The for loop repeats n-1 times, (linear number of times) and the entire algorithm is linear-quadratic. Time < c1 + c2 xn + c3 x n^2. In the worst case scenario, the time is o (n^2) and in the best case scenario, time is (n) Note that not every single exam must be shifted/copied into a new place. The ideal way of representing lists (ordered sets of elements) is not necessarily always through using arrays. Null-pointer in an array contains no object, and it points" to nothing.