Discussion
Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?
I. Quicksort runs in \(\Theta(n^{2})\) time
II. Bubblesort runs in \(\Theta(n^{2})\) time
III. Mergesort runs in \(\Theta(n)\) time
IV. Insertion sort runs in \(\Theta(n)\) time
Answer: D
The true statements are I and IV only.
I: the standard quicksort picks the first (or last) element as pivot. On sorted input that pivot is the smallest (or largest) element, every partition is maximally unbalanced, and the running time is \(\Theta(n^{2})\).
IV: insertion sort compares each new element only with its left neighbour, finds it already in place and moves on, so sorted input takes \(\Theta(n)\).
II is not taken as true: bubble sort with the usual check for a pass with no swaps stops after one pass over sorted input, \(\Theta(n)\); the key assumes this standard version, since a bubble sort without the check would take \(\Theta(n^{2})\). III is false: merge sort always splits and merges fully, so it takes \(\Theta(n\log n)\) on any input, never \(\Theta(n)\).
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development