Register

Adaptive sorting Algorithm.

5,096 views
1 votes
1 votes
Is Quick sort an adaptive sorting Algorithm? I think no. Because as per the definition given in the Wikipedia is that A adaptive sorting Algorithm is one who takes the advantage of preorderedness of the input. But in case of Quick sort it act as disadvantage.
User Avatar

2 Answers

1 votes
1 votes
Quick sort is Adaptive sorting algorithm because the time complexity of Quick sort depends on the  initial input sequence (pre- orderedness).

Adaptive sorting algorithms:
1. Bubble Sort
2. Insertion Sort
3. Quick Sort

Non-adaptive sorting algorithms:
1. Selection Sort
2. Merge Sort
3. Heap Sort
User Avatar
1 votes
1 votes

An adaptive algorithm is an algorithm that changes its behavior on given input sequence.

in quick sort:

  • If input sequence is sorted then time complexity become O(n^2).
  • If input sequence is not sorted then time time complexity become O(nlogn).

So quick sort change its behavior based on inout sequence so it is adaptive algo.

in merge sort:

  • If input sequence is sorted then time complexity become O(nlogn).
  • If input sequence is not sorted then time time complexity also become O(nlogn).

So merge sort not change its behavior based on input sequence so it is non adaptive algo.

 

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
4 answers
1
Ramij asked Dec 20, 2018
2,347 views
MadeEasy Subject Test 2019: Algorithms - Sorting
Suppose there are 4 sorted list of 16 elements each. If we merge these lists into a single sorted list of 64 elements. The key comparisons that are needed in the worst case using an efficient algorithm are
Suppose there are 4 sorted list of 16 elements each. If we merge these lists into a single sorted list of 64 elements. The key comparisons that are needed in the worst ca...
User Avatar
4 votes
4 votes
1 answer
2
Prince Sindhiya asked Aug 23, 2018
2,014 views
Gateforum Test Series: Algorithms - Sorting
. In the standard merge sort algorithm on a list of size n, what is the maximum number of times an item can be compared? a)2 b)logn c)n-1 d)nlogn
. In the standard merge sort algorithm on a list of size n, what is the maximum number of times an item can be compared?a)2b)lognc)n-1d)nlogn
User Avatar
0 votes
0 votes
0 answers
3
Rahul Ranjan 1 asked Jun 15, 2018
671 views
Sorting
You are asked to sort 15 randomly generated numbers. One should prefer - 1. Bubble Sort 2. Quick Sort 3. Merge Sort 4. Heap Sort Please explain why others 3 sorting algorithms except the answer can't be used ?
You are asked to sort 15 randomly generated numbers. One should prefer - 1. Bubble Sort2. Quick Sort3. Merge Sort4. Heap Sort Please explain why others 3 sorting algorith...
User Avatar
4 votes
4 votes
4 answers
4
Aibi asked Oct 8, 2017
2,624 views
Ace Test Series: Algorithms - Sorting
Consider bottom-up merge sort working on 'n' elements. Assume 'n' is a power of 2. The minimum number of comparisons in order to get sorted list is (A) (n log n) / 2 (B) n lon n - n + 1 (C) n log n (D) n log n + n
Consider bottom-up merge sort working on 'n' elements. Assume 'n' is a power of 2. The minimum number of comparisons in order to get sorted list is(A) (n log n) / 2(B) n ...
User Avatar
Link Copied!