Solving sub problems in algorithmic manner

Thread Starter

Ryan$

Joined Dec 14, 2018
178
Hi guys, firstly maybe it's by default understandable to others so please I know "it's simple" but I need to be freshly and not confused about what I'm going to ask.

What's confusing me is, when I've a specific Problem, and I need to solve the problem by solving its sub-problems(recursive manner), I'm wondering why we disregarding the solved part problem once solved ? meaning if I have a Problem which its to sort an Array by using for instance QuickSort, lets say I have {1,2,3,4,5,6} and the pivot is 6 which we say that 6 is on its exact place so its sorted, then we are having now sub-problem to solve which is {1,2,3,4,5} ..and then the same thing, 5 is the pivot, and its on the same exact place, so we just ignoring it and saying now we have subproblem which is {1,2,3,4} ..etc , my question why we are neglecting the sorted element and once its sorted we subtract it from the problem? it's like a nullity for us after sorted why?! maybe I'm not good as much good at logic but I believe by your help I could understand it very well.

Maybe if you give me please a real life analogues elaborating that logic(neglecting some parts of the problem and going just to the subproblems) would be much appreciated to get fast learning
 

djsfantasi

Joined Apr 11, 2010
9,185
Let me explain by using your example. The first pass through the array, you know the last element is in the correct position. So, you look at the sub-problem, and pass through the first five elements. Why do we ignore the last element? Because it’s in the correct position. We don’t want to ever change it. And since it is in its correct position, we don’t want to waste time looking at it again.

This holds true for your remainder sub-problems. At any given step, there is a set of values that are in the correct position. And we don’t want to waste time looking at them again. So you have a sub-problem and a sub-answer at each pass.
 

Thread Starter

Ryan$

Joined Dec 14, 2018
178
Let me explain by using your example. The first pass through the array, you know the last element is in the correct position. So, you look at the sub-problem, and pass through the first five elements. Why do we ignore the last element? Because it’s in the correct position. We don’t want to ever change it. And since it is in its correct position, we don’t want to waste time looking at it again.

This holds true for your remainder sub-problems. At any given step, there is a set of values that are in the correct position. And we don’t want to waste time looking at them again. So you have a sub-problem and a sub-answer at each pass.
I understand the clue of; it's like logo/sudoku pazzle; whenever we solve a block of the problem we dynamically moving to the sub-problem ..right?
Thanks anyway
 
Top