The Gateway to Computer Science Excellence
0 votes
382 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 | 382 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

+1 vote

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
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
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
52,315 questions
60,432 answers
201,778 comments
95,257 users