Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
6 Cards in this Set
- Front
- Back
|
Bubble Sort Algorithm |
1. Start at the beginning of the list. Pass through the list and compare adjacent values. For each pair of values - if they are in order, leave them - if they are not in order, swap them. 2. When you get to the end of the list, repeat step 1. 3. When a pass is completed without any swaps, the list is in order. |
|
|
Quick Sort Algorithm |
1. Choose the item at the mid-point of the list to be the first pivot. 2. Write down all the items that are less than the pivot, keeping their order, in a sub-list. 3. Write down the pivot. 4. Write down the remaining items (those greater than the pivot) in a sub-list. 5. Apply steps 1 to 4 to each sublist. 6. When all the items have been chosen as pivots, stop. |
|
|
Binary Search Algorithm |
1. Select the middle item in the list, m (use (n+1)/2 and round up if necessary), 2. (i) if T = m, the target is located and the search is complete, (ii) if T is before m, it cannot be in the second half of the list, so that half, and m, are discarded, (iii) if T is after m, it cannot be in the first half of the list, so that half, and m, are discarded. 3. Repeat steps 1 and 2 to the remaining list until T is found. |
|
|
Bin Packing: First-fit Algorithm Give an advantage and a disadvantage |
1. Take the items in the order given. 2. Place each item in the first available bin that can take it. Start from bin 1 each time. + It is quick to do - It is not likely to lead to a good solution |
|
|
Bin Packing: First-fit Decreasing Algorithm Give two advantages and a disadvantage |
1. Reorder the items so that they are in descending order. 2. Apply the first-fit algorithm to the reordered list. + You usually get a fairly good solution + It is easy to do - You may not get an optimal solution |
|
|
Bin Packing: Full-bin Packing Algorithm Give an advantage and a disadvantage |
1. Use observation to find combinations of items that will fill a bin. Pack these items fist. 2. Any remaining items are packed using the first-fit algorithm. + Usually a good solution - Difficult to do, especially when the numbers are plentiful and awkward |
