Chapter 1 algorithms Flashcards
Algorithm.
A set of instructions which, if carried out correctly, will solve a problem
Bubble sorts order is
Quadratic
Max number of comparisons
n(n-1) / 2
How to do the bubble sort
Adjacent numbers are compared eg 1 and. 2. They are swapped if in wrong order. The second and third number is now compared. After first pass, last number will be correctly positioned and so on. Algorithm stops when a pass provides no swaps
Pro of bubble sort
Simple to implement
efficent for small lists
Cons of bubble sort
Extremely inefficient for big lists
How to do quick sort
Find middle number which becomes the pivot and circle it. If sorting in ascending order, write all numbers smaller than the pivot to the left of the pivot, in the same order. And write all numbers larger than the pivot to the right, keeping same order. The pivot is now fixed. Repeat this for all new sublists created until all numbers are fixed or sublists contain only 1 number.
Aim of bin packing
Pack items of diff lengths into a minimum number of bins
3 types of bin packing
First fit
First fit decreasing
Full bins
Lower bound
Is not always possible
Lower bound helps us find
Minimum amount of bins
Pros of first fit
Efficent
Straight forward
Cons of first fit
Wasted space
Pros of first fit decreasing
More space used
Pack big ones first
Cons of first fit decreasing
Spends time ordering first
