Awesome q2a theme
0 votes
23 views
Consider a sequence A of length n which is
sorted except for one item that appears out of order.Which of the following can sort the
sequence in O(n) time?

(a) Heap sort
(b) Quick sort
(c) Merge sort
(d) Insertion sort
in Algorithms by (8 points) | 23 views

1 Answer

0 votes

Insertion sort works best for nearly sorted or almost sorted array and gives the time complexity of $O(n)$ . So answer should be d


If found helpful, UPVOTE and mark ans as the BEST ANSWER (by clicking the blue tick on the left side of the ans). This motivates me to ANSWER YOUR QUESTIONS IN FUTURE

by (1.2k points)
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Oct 2019
  1. GAITONDE

    410 Points

  2. Satbir

    317 Points

  3. Rudr Pawan

    163 Points

  4. srestha

    136 Points

  5. Mk Utkarsh

    127 Points

  6. Debapaul

    94 Points

  7. chandrikabhuyan8

    83 Points

  8. Shaik Masthan

    79 Points

  9. Verma Ashish

    77 Points

  10. !KARAN

    74 Points

Monthly Top User and those within 60% of his/her points will get a share of monthly revenue of GO subject to a minimum payout of Rs. 500. Current monthly budget for Top Users is Rs. 450.
1,680 questions
1,089 answers
4,559 comments
89,591 users