In this problem you will implement a function to sort a list of integers or floats...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
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]). 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]).
Expert Answer:
Answer rating: 100% (QA)
Answer def indexOfMinL start end if start 0 or end lenL or start end I... View the full answer
Related Book For
Discrete Mathematics and Its Applications
ISBN: 978-0073383095
7th edition
Authors: Kenneth H. Rosen
Posted Date:
Students also viewed these programming questions
-
Write a program that reads a number nuggets , (input by the user), and then calculates how many calories and displays the result. Use a named constant CALORIES_PER_NUGGET . The value to use is: 59.3...
-
Assignment 5: Hash Table implementation andconcordance There are three parts to this assignment. In the first two parts,you will complete the implementation of a hash map and aconcordance program. In...
-
How does the integration of positive psychology principles, such as strengths-based approaches and flow theory, contribute to the enhancement of motivation and well-being in individuals and...
-
Mr. and Mrs. Thomas are buying a new house for $330,000. Compare the two loan offers by finding the monthly payments for each and calculating the total amount paid for each. Loan Options Down Payment...
-
Determine the force in each member of the truss and state if the members are in tension or compression. Units Used: kN = 103 N Given: P1 = 2kN P2 = 4kN a = 2 m = 15 deg P2
-
11. If an ultrasound wave travels through brain tissue at a speed of 1540 m/s and takes 10 microseconds to pass through the tissue, what is the thickness of the brain tissue? (10 Points)
-
A milk processing unit claims that, of the processed milk converted to powdered milk, \(95 \%\) does not spoil. Find the probabilities that among 15 samples of powdered milk (a) all 15 will not...
-
On February 11, 20Y9, Quick Fix Company purchased $2,250 of supplies on account. In Quick Fixs chart of accounts, the supplies account is No. 15, and the accounts payable account is No. 21. a....
-
2B. Union Express has 60 tons of cargo that needs to be shipped from Boston to Dallas. The shipping capacity on each of the routes Union Express planes fly each night is shown in the following table:...
-
Consider the following parlor game to be played between two players. Each player begins with three chips: one red, one white, and one blue. Each chip can be used only once. To begin, each player...
-
Prepare a critical analysis of the difference between a fixed loan and a variable rate loan.
-
_______________________ In the two-sample t test, the number of degrees of freedom for the test statistic increases as sample sizes increase.
-
A woman has eight skirts and four blouses. Assuming that they all match, how many different skirt and- blouse combinations can she wear?
-
_______________________ One of the assumptions underlying the use of the (pooled) two-sample test is that the samples are drawn from populations having equal means.
-
_______________________ If the calculated value of the t statistic is negative, then there is strong evidence that the null hypothesis is false.
-
_______________________ It is not necessary to have equal sample sizes for the paired t test.
-
1. How is data in a relational table organized? Rows and Columns O Header and Footer O Pages and Paragraphs 2. Which of the following is an example of unstructured data? An Employee table with...
-
Using the information in P11-2B, compute the overhead controllable variance and the overhead volume variance. Data From Problem 11-2B: Huang Company uses a standard cost accounting system to account...
-
What are the codes for a, e, i, k, o, p, and u if the coding scheme is represented by this tree? 0 0 0 0 0
-
Describe a graph model that represents traditional marriages between men and women. Does this graph have any special properties?
-
Let X be a random variable on a sample space S such that X(s) 0 for all s S. Show that p(X(s) a) E(X)/afor every positive real number a. This inequality is called Markov's inequality.
-
Identical positively charged objects \(A, B\), and \(C\) are launched with the same initial speed from the same position above a negatively charged sheet that produces a uniform electric field. The...
-
A proton, a deuteron (a hydrogen nucleus containing one proton and one neutron), and an alpha particle (a helium nucleus consisting of two protons and two neutrons) initially at rest are all...
-
What orientation of an electric dipole in a uniform electric field has the greatest electric potential energy? What orientation has the least? (Let the system comprise both the electric dipole and...
Study smarter with the SolutionInn App