Things course is going to go over:
Course covers things like correctness of algorithms, efficiency, actual programmi
Efficiency is things like steps, number of steps, and if its optimal
How do u know if something is actually optimal?
Chapter 0: Sorting and Measurement (Big O)
Insertion sort:
You have an array of numbers that unsorted
Start at the second step then keep moving backwards if your smaller than the on
Repeat for each item
Best case: Already sorted -> (n-1) steps or about (n) steps.
Worst case: Sorted in opposite order and O(n2)
Input: An array A[1..n] of n numbers. Output: An array containing the numbe
1: for j = 2 to n do
2: key = A[j]
3: i = j − 1
4: while i > 0 and A[i] > key do
5: A[i + 1] = A[i]
6: i = i − 1
7: end while
8: A[i + 1] = key
9: end for
Trace:
Course covers things like correctness of algorithms, efficiency, actual programmi
Efficiency is things like steps, number of steps, and if its optimal
How do u know if something is actually optimal?
Chapter 0: Sorting and Measurement (Big O)
Insertion sort:
You have an array of numbers that unsorted
Start at the second step then keep moving backwards if your smaller than the on
Repeat for each item
Best case: Already sorted -> (n-1) steps or about (n) steps.
Worst case: Sorted in opposite order and O(n2)
Input: An array A[1..n] of n numbers. Output: An array containing the numbe
1: for j = 2 to n do
2: key = A[j]
3: i = j − 1
4: while i > 0 and A[i] > key do
5: A[i + 1] = A[i]
6: i = i − 1
7: end while
8: A[i + 1] = key
9: end for
Trace:
