Answered step by step
Verified Expert Solution
Question
1 Approved Answer
In this problem you will implement a function to sort a list of integers or floats in non-decreasing order using the selection sort algorithm.
In this problem you will implement a function to sort a list of integers or floats in non-decreasing order using the selection sort algorithm. The idea of Selection of Sort is as follows. To sort a length-n list L = [L[0],..., L[n 1]]: 1. Find the index minIndex of smallest element in L (find the index of first occurrence if you have more than one element equal to the min). 2. Exchange L[minIndex] (swap it) with L[0], hence now L[0] is the (a) smallest element of L, i.e., the number stored in L[0] is in its correct position in the desired sorted order 3. Find the index minIndex of the smallest element in [L[1], ..., L[n 1]] 4. Exchange L[min Index] with L[1], hence now L[1] is the (a) second smallest element of L, i.e., the number stored in L[1] is in its correct position in the desired sorted order. 5. Find the index minIndex of the smallest element in [L[2], ..., L[n 1]] 6. Exchange L[minIndex] with L[2], hence now L[2] is the (a) third smallest element of L, i.e., the number stored in L[2] is in its correct position in the desired sorted order. 7. And so on until the whole list L is sorted You will implement this algorithm in Part (c), but first you will try it on an example in part (a) and you will implement a function to do Steps 1,3,5,... in Part (b). a) Try it on an example. Illustrate the algorithm on L= [5, 2, 4, 6, 1, 3]. There is no need to submit this part. b) Function to find the index of min. Implement a function indexOfMin (L, start, end), which takes as input arguments a list L of integers or floats and two indices start and end such that 0 < start < end Test script: L = [10,4,3,7,3,15] print (indexOfMin (L, 0,5)) print (indexOfMin (L,1,5)) print (indexOfMin (L,3,4)) print (indexOfMin (L, 4,4)) Output: NE44 2 2 c) Selection sort function. Using your function in Part (b), implement a function selectionSort (L), which given a list L of integers floats, sorts L in non-decreasing order as explained in the selection sort algorithm. Note that unlike the function indexOfMin, the function slectionSort modifies the list L. Notes: * Note that the slicing operator is not useful in the implementing of selectionSort. * Swapping: Say that we want to swap, i.e., exchange, L[7] and L[2]. If you set L[7] to L[2], and then set L[2] to L[7], you loose the old value of L[7]. To resolve this issue, use a temporary variable temp: 1. set a temp to L[7] 2. set L[7] to L[2], then 3. set L[2] to temp. Another approach to swap is use tuples: (L[7], L[2]) = (L[2], L[7]).
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Answer def indexOfMinL start end if start 0 or end lenL or start end I...Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started