The Gateway to Computer Science Excellence

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

0

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

+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.

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

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

52,315 questions

60,432 answers

201,778 comments

95,257 users