Use shuttle sort to sort the five numbers 8, 6, 9, 7, 5 into increasing order. Write down the list that results at the end of each pass. Calculate and record the number of comparisons and the number of swaps that are made in each pass.
The algorithm below is part of another method for sorting a list into increasing order. A pply it to the list 8, 6, 9, 7, 5. Show the result of each step.
Step 1: Input the original list and call it list A.
Step 2: Remove the first item in list \(A\) and call this item \(X\).
Step 3: If the first item remaining in list A is less than X move it to list B , otherwise move it to list C.
Step 4: If the next item remaining in list A is less than X move it to become the next item in list B, otherwise move it to become the next item in list C.
Step 5: If there are still items in list A, repeat Step 4.
Step 6: Count the number of items in list \(\mathbf { B }\) and call this \(\mathbf { N }\).
Step 7: Put the items in list B at positions 1 to N of list A, item X at position \(\mathrm { N } + 1\) of list A and the items in list C at positions \(\mathrm { N } + 2\) onwards of list A.
Step 8: Display list A.