ISRO2007-55

Question

Selection sort algorithm design technique is an example of

• A. Greedy method
• B. Divide-and-conquer
• C. Dynamic Programming
• D. Backtracking

Comments

greedy....coz it always find small among the large to sort

---

 Brute Force

.

---

I think all 4 options were incorrect

Answer 1

Correct Answer would be A) Greedy Algorithm

Because, In the first iteration we put a pointer in the start of the array. Then next we start searching index of minimum element index in the rest of the array. Then replace the starting pointer value with minimum index value. (Considering the we are sorting in ascending order). Then repeat this process for each element. 

Comments

sir, but greedy approach is used to solve optimization problems like maximize the profit , minimize the delay etc. so, to sort the numbers is a optimization problem ?

Answer 2

Selection sort used in divide and conquer technique

Here smallest element replaces 1st element of the array , 2nd smallest element replaces 2nd element and like that all element sorted

Comments

yes @shivani in ur link also told " the list is divided into two parts"

---

@ srestha after dividing ..how about conquering

---

like selection sort does , is it not?

Answer 3

Selection Sort is Brute force Approach

http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L28-Design.htm#brute

As we move through all the elements of array so greedy is within available elements we select min between 2 elements but we further move to all elements so i think it wont be greedy

Comments

Shivani, Yeah its bruitforce, but if you look at the core its greedy. Smilarly Insertion is divide and conquer.

---

You have given it a proof definitely you are right .

---

The link you provided categorize solution of Knapsack Problem as Brute-Force approach. Whereas, Fractional Knapsack Problem is solved using Greedy Approach and 0/1 Knapsack Problem using Dynamic Programming.