retagged by
4,752 views
0 votes
0 votes
Q.Suppose our aim is to sort an array in ascending order. Which of the following statements is true?

 1.Input in ascending order is worst case for both selection sort and insertion sort.

 2. Input in descending order is worst case for both selection sort and insertion sort.

 3. Input in ascending order is worst case for insertion sort but not for selection sort.

 4.Input in descending order is worst case for selection sort but not for insertion sort.
retagged by

1 Answer

0 votes
0 votes
only 2nd option is true.

selection sort involves determination of minimum for the suffix[i..n] for all i , so in every case it will do O(n^2)

insertion sort involves sorting the prefix[1..i] for all i , which it does by comparing previous element with the new element and pushing it in its right position . since every prefix is sorted in ascending array ,it will take O(n). however for any other array it will take O(n^2)
Answer:

Related questions

0 votes
0 votes
1 answer
1
Edwees asked Feb 6, 2017
1,895 views
We have a list of pairs [("Tariq",71),("Brinda",85),("Shweta",71),("Sunita",85),("Salma",72),("Uday",60)], where each pair consists of a student's name and his/her marks ...
0 votes
0 votes
1 answer
3
saurabh12345 asked Jul 24, 2018
402 views
Insertion sort uses an incremental approach for designing algorithm can someone please explain?
0 votes
0 votes
1 answer
4
iamdeepakji asked Oct 2, 2018
323 views
What is adaptive algorithm and is merge sort and quick sort is adaptive?