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.

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

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,648 questions

56,429 answers

195,206 comments

99,910 users