Algorithms Flashcards
What are the 3 steps to ‘Bubble sort’?
- Start at the beginning of the list. Pass though the list & compare values. If not in order swap them
- When you get to the end of the list, repeat step 1
- When a pass is completed without any swaps, the list is ordered
What are the 6 steps to ‘Quick sort’?
- Choose the item in the middle of the list as 1st pivot
- Write down all the items that are less than the pivot, keeping them in order, into a sub-list
- Write down the pivot
- Write down the items that are greater than the pivot, keeping them in order, into a sub-list
- Apply step 1-4 to each sub-list
- When all have been chosen as pivots, STOP
What do you have to do before a binary search?
Order the list
What are the 3 steps to do a ‘binary search’?
- Select the middle item
n+1 / 2 - If T is before M it can’t be in second half of list so it is discarded. If T is after M it can’t be in the first half of list so it is discarded
- Repeat 1-2 to remaining list until T is found
What are the 3 bin packing algorithms?
- First-fit
- First-fit decreasing
- Full-bin
What are the 2 steps to do a ‘first-fit’ bin sort?
- Take the items in order given
2. Place each item into 1at available bin. Start from bin 1 each time
What is 1 strength and 1 weakness of the first-fit algorithm
Strength:
- Quick
Weakness:
- Not likely to lead to a good solution
What are the 2 steps to do a ‘first-fit decreasing’ bin sort?
- Reorder the items so that they are in decreasing order
2. Apply he first-fit algorithm
What is 1 strength and 1 weakness of a ‘first-fit decreasing’ algorithm?
Strength:
- Easy to do
- Usually get good solution
Weakness:
- May not get optimal solution
What are the 2 steps to do a ‘full-bin’ bin sort?
- Use observation to find combination of items that will fill a bin
- Any remaining items are packed using ‘first-fit’ algorithm
What is 1 strength and 1 weakness of ‘full-bin’ algorithm?
Strength:
- Usually get good solution
Weakness:
- Difficult to do
