7.03k Sorting: quick sort

A machinist has to cut the following seven lengths (in centimetres) of steel tubing. $$150 \quad 104 \quad 200 \quad 60 \quad 184 \quad 84 \quad 120$$

1. Perform a quick sort to put the seven lengths in descending order. [4 marks]

The machinist is to cut the lengths from rods that are each 240 cm long. You may assume that no waste is incurred during the cutting process.

1. Explain how to use the first-fit decreasing bin-packing algorithm to find the minimum number of rods required. Show that, using this algorithm, five rods are needed. [4 marks]
2. Find if it is possible to cut additional pieces with a total length of 300 cm from the five rods. [1 mark]

17 & 9 & 15 & 8 & 20 & 13 & 28 & 4 & 12 & 5 \end{array}$$ The numbers in the list shown above are the weights, in kilograms, of ten boxes. The boxes are to be transported in containers that will each hold a maximum weight of 40 kilograms.

1. Calculate a lower bound for the number of containers that will be needed to transport the boxes. You must show your working.
2. Use the first-fit bin packing algorithm to allocate the boxes to the containers.
3. Using the list provided, carry out a quick sort to produce a list of the weights in ascending order. You must make your pivots clear.
4. Use the binary search algorithm to try to locate the weight of 9 in the sorted list. Clearly indicate how you choose your pivots and which part of the list is being rejected at each stage.