DS&A

Exercises: Sorting

Before attempting these exercises, you should read the posts on comparisons and swaps, iterative sorting and recursive sorting.

Exercises

1. 1. Write a function which, given a list and two indices, swaps the values at those indices.
   2. Modify your function so that it only swaps if the first value is greater than the second value.
2. Consider the interactive model for the “out-of-place” selection sort algorithm.
   1. Work through an example step-by-step — at each step, write down the value being sorted, and the current state of both lists.
   2. State which list operations are needed to implement this algorithm.
   3. Write a function which finds the index of the minimum value in the input list. (Hint: use plans.)
   4. Implement the algorithm using a loop which sorts values into the output list, one at a time.
3. Consider the interactive model for the “out-of-place” insertion sort algorithm.
   1. Work through an example step-by-step — at each step, write down the value being sorted, and the current state of both lists.
   2. State which list operations are needed to implement this algorithm.
   3. Write a function which finds the index of the first value in the output list greater than a given target. (Hint: use plans.)
   4. Implement the algorithm using a loop which sorts values into the output list, one at a time.
4. Add the following print statements to your algorithms from 2. and 3.:
   • print('Input list:', repr(input_list))
   • print('Output list:', repr(output_list))
   • print('Sorting the value', repr(value))
   Using the lists you sorted in 2a. and 3a., test your functions and compare your step-by-step working with the printed output.

• Tags: 
• exercises, sorting, algorithms