GO Classes DPP | GATE CS, DA | Algorithms | Bubble Sort

Answer 1

B. Brute force

Bubble Sort repeatedly scans through the unsorted elements and directly compares adjacent pairs.

It does not use a sophisticated method to avoid unnecessary comparisons.

Therefore, it is primarily classified as a brute-force algorithm.

C. Decrease-and-conquer

After the first pass, the largest element reaches its final position.

Therefore, the remaining unsorted problem has size: $n-1$

After the next pass, it becomes: $n-2$ and so on.

Thus, Bubble Sort can also be viewed as reducing the unsorted problem by one element after every pass.

This corresponds to the decrease-and-conquer idea.

It does not divide the problem into independent subproblems, so Divide-and-Conquer is incorrect. 

It also does not use overlapping subproblems or an optimal-choice rule, so Dynamic Programming and Greedy are incorrect. 

The source classifies Bubble Sort as brute force and also reasonably as decrease-and-conquer.

Answer: B and C

Comments

@GOClasses Why not greedy ? because in every comaprsion we are picking smallest one  

Answer 2

A. Greedy - NOT CORRECT:
Make locally optimal choice towards an optimal objective. But bubble sort simply runs through the unsorted portion of the array, swapping adjacent elements if needed. So we are definitely not choosing the greedy action here. So not greedy.

B. Brute Force - CORRECT:
We are going through the unsorted portion of the array in each iteration the same way regardless of whether the elements in it are already sorted or not. So we go through every possibility even if not needed. So definitely Brute Force.

C. Decrease and Conquer - CORRECT:
After each iteration we decrease the size of the unsorted portion by 1. That is Decrease and Conquer.

D. Divide and Conquer - NOT CORRECT:
Divide and conquer divides a problem into two or more sub-problems, solves them independently and combines the result. So this is not Divide and Conquer.

E. Dynamic Programming - NOT CORRECT:
When we have overlapping subproblems with optimal sub-structure, we resuse solutions using dynamic programming, We do not have that here.

Answer: B, C