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.
| 113 views
0
0

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

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

1. Bubble Sort
2. Insertion Sort
3. Quick Sort

1. Selection Sort
2. Merge Sort
3. Heap Sort
by Active (1.4k points)

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)