The Gateway to Computer Science Excellence
0 votes
113 views
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.
in Algorithms by Boss (18.2k points) | 113 views
0

Yeah I too think that QS is not adaptive and not an online sorting algorithm. But I read this on Quora. 

2 Answers

0 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
by Active (1.4k points)
0 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.

 

by Boss (35.6k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,648 questions
56,429 answers
195,206 comments
99,910 users