Recursion

Quote:

---

Originally Posted by King Mir

It really isn't that hard to write selection sort recursively, which is what he's trying to do.

---

Yes you're right. In fact upon reading the description closer, there's no need for sorting at all. For each item in array 1 just search for a corresponding item in array 2. it's O(n*m) but selection sort is basically the same, so why bother. I doubt this needs to be as fast as possible.

Quote:

---

Originally Posted by iMalc

Yes you're right. In fact upon reading the description closer, there's no need for sorting at all. For each item in array 1 just search for a corresponding item in array 2. it's O(n*m) but selection sort is basically the same, so why bother. I doubt this needs to be as fast as possible.

---

Quote:

---

Originally Posted by King Mir

A way to approach this problem more broadly is to identify known recursive algorithms that can be applied to the situation. Such algorithms include: accumulate/fold, which applies a function to total all the elements together in to one result; map/for each/transform, which applies a function to each element using; and filter/grep, which gets rid of all elements that do not satisfy a boolean condition function.

For for example you can alternatively use this set of algorithms:
For each element A in array one, filter list two on the condition of each element being equal to A.
Then count the number of elements in the resultant list using accumulate (or more directly if you can figure out how).

---

:)

Sorting is the best way to do this, which is why I suggested it first, particularly if quick sort is used; That's how I'd do it.

There really are a lot of ways to do this, and several ways to approach the problem. Recursion is very similar to proof by induction, so if you can think and express the problem in those terms, finding a solution is easy. If you know a few basic recursive functions then you can you can just use those. That approach is particularly elegant, because it allows you to consicely express complex algorithms in a single line of code. And I suppose you can take the static variable approach, and effectively map/for each with a state barring function.

Quicksort uses two interior loops. Although it's a wonderful algorithm, it's not the best choice for a student struggling to make every loop into recursive calls.

Selection sort is better, but can't compare to the simplicity of bucketsort, which uses just one loop and two other lines of code. Since what it really does is a distribution count, rather than a sort, bucketsort is ideal. There is no sorting algorithm which is as simple as bucketsort, period. Please go back and look at the code for it that I posted. I hate to sound like the Borg Queen and say that it's the essence of perfection, but for this case, it's just that.

I'm surprised at the continued recommendations for using a more difficult, (and more complex), algorithm.

It's not that selection or Qsort can't be made into a totally recursive, non-looping function, but clearly the student is struggling and unable to do it with selection sort. Qsort being even more difficult than selection sort (although I've never tried to make either function, without using any loops).

When a better way presents itself, why not recommend it? After seeing the "backbone" of the logic in code for using bucketsort, I'm also surprised that the student didn't immediately try that approach.

Actually with recursion quicksort is easier to implement then selection sort. Quicksort is a naturally recursive algorithm that contains only one tricky part: partitioning the list into values less then and greater then the pivot. But that just a fileter/grep of a list on a boolean condition. The filter algorithim is sterait fiorward:

Code:

---

filter(boolFunc, array, arraySize, targetArray) {
  if(arraySize==0)
    return;
  if(boolFunc(*array)){
    *targetArray=*array;
    targetArray++;
  }
  filter(boolFunc,array+1,arraySize,targetArray);
}

---

In this case boolfun is the less than t function, were t changes in each loop. And of course there is no need to make it generic; I'm just doing that to show the algorithm more purely.

Ok that's not as simple as I though it'd be because I have to use an array instead of a linked list. But it is still strait forward. The outer loop of selection sort is trickier than this.

The problem with bucket sort is that it requires you to know the set of possible values, which is not a given in the assignment. You could use one of the lists as that set, but then you are not using bucketsort, you are applying the algorithm iMalc and I mentioned above. Calling that bucketsort would be misleading.

Speaking of the outer loop of selection sort, since its been some time I'll just give the algorithm for it:

the outer loop just itterates by considering the minimum element of the array one index higher.
base case-> an array of size one is already sorted
recursive step-> the sorted result is the minimum element of an array, prepended to the array sans that element. To get the array sans the element, just swap the element with array[0]

I guess that has the advantage that you don't need a target array.