Adaptive sorting Algorithm.

Question

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.

Comments

https://stackoverflow.com/questions/19255999/is-quicksort-adaptive-and-online

---

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

Answer 1

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

Answer 2

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.