Recursively sorting an array of strings w/o aux. parameter

[Enharmonics]

One of my professor's assignments is proving particularly tricky for me. It reads:

"Write the method

public static void sort(String[] a)

that sorts the array a in increasing order. The method must be
a short recursive program. Do not use quicksort or merge sort.
It should be a lot shorter."

The catch: I'm not allowed to change the method header in any way, I'm not allowed to use either merge sort or quick sort (as stated in the instructions), and I'm not allowed to use any extraneous classes, packages, and the like (no java.util.Arrays, etc).

Merge sort and quick sort being disallowed isn't that big a deal for me as I'm not very fond of either, but I'm finding it hard seeing how to do this without passing some auxiliary parameter (to store an index position for the array) that would get used in recursive invocations.

This is what I came up with after a few hours of frustration and basically spinning my wheels:

public static void sort(String[] a)
{

   String temp;

   // Note that we use a.length - 1 in the loop condition
   // to account for the fact that we will be checking the value of the
   // element at the current index against the value of the element at the NEXT index.
   // Since array indices are zero-based, iterating from 0 to a.length would result
   // in an ArrayIndexOutOfBoundsException when we index = 7, since the
   // base case would check a[7] against a[8], the latter of which does not exist

   for (int index = 0; index < a.length - 1; index++)
   {
       if (a[index].length() < a[index + 1].length())
       {
           continue;
       }
       else
       {
           temp = a[index + 1];
           a[index + 1] = a[index];
           a[index] = temp;

           // Recursive call to the sort method
           sort(a);
       }
   }
}

The basic idea was to check each element "multiple times" with the for loops so as to encourage each element getting into its "proper place" (in the "increasing order" sense). I doubt it's right, though I haven't tested it (professor hasn't uploaded a driver for this assignment yet).

If not, could someone maybe point me in the right direction? There don't seem to be any methods in either the Array or String class that would be useful here. I don't even see the point of using recursion here. Isn't it useless since I'm just passing the method the same array over and over again (to the best of my knowledge there's no method in the Array class to create a "Subarray" of an array, the only thing that comes close is Arrays.asList(), but I'm not allowed to use it)?

 

[Borg]

It sounds like he wants you to examine smaller pieces of the String[] by passing those pieces recursively back to the same method for examination. Does that make sense?

 

[anorlunda]

Have you done a search on recursion sort algorithms?

 

[QuantumQuest]

Merge sort and quick sort being disallowed isn't that big a deal for me as I'm not very fond of either

They're both excellent algorithms - particularly quicksort in optimized fashion and very much used in a whole lot of applications, so I cannot really see why you are not fond of them. In any case, merge sort is recursive and quicksort has both a recursive and an iterative version.

Now, for your question, I think that what your professor asks you, is think about what you have to pass recursively to the sorting method, in order for the method to terminate successfully having done its job. My hint is along the lines of Borg i.e. using each time a start and a stop point, that will be relevant recursively to the start and stop index of the array, if strings are sorted then go on else interchange.

Also, you can take ideas for recursion examining how merge sort, quicksort and other recursive algorithms are working.

 

[Boing3000]

The method must be a short recursive program

If this means the only method of the program is the one following that signature you should concentrate on that.
Given your own remarks on the problem of that signature, it seems your are already on your way to find a "solution" to that problem.

 

[jim mcnamara]

@anorlunda - Unfortunately, 'recursive sort' as a search topic is not very helpful for this topic. Several prominent (at least in programming classes) recursive algorithms are all over the result. Probably 'recursive bubble sort' would be better since that is what the OP was really asked to implement.

What you need, you have already written in a slightly different form. You have a bubblesort, so use most of that. Simply reduce the ending variable by one each time you call it. nelems is the limit for tour index variable
pseudocode for a recursive bsort:

bsort ( arr, nelems)
begin
    if nelems == 1 return
   [your loop goes here ]
   call bsort(arr, nelems -1)
end

 

[wle]

Merge sort and quick sort being disallowed isn't that big a deal for me as I'm not very fond of either, but I'm finding it hard seeing how to do this without passing some auxiliary parameter (to store an index position for the array) that would get used in recursive invocations.

Well normally in recursion you're supposed to recurse your way down to some base case. I can think of two approaches:

• Define how to sort an array of length N in terms of how to sort an array of length N - 1, with the base case being sorting an array of length zero or one. Since, like you say, Java doesn't seem to offer a good way to pass a reference to a subarray, and you're not allowed to pass additional information like an index or length, I don't see how you can use this approach without doing a lot of copying between temporary arrays.
• In your case, you're comparing strings, and the empty string "" comes before any other string. So you could try defining how to sort an array in terms of how to sort the same array except with the "smallest" non-empty string replaced with "", recursing your way down to sorting an array containing only empty strings. (This is probably not very conventional, but at least it avoids lots of copying.)

By the way, it's not obvious from the wording of the exercise, but I would have expected that you're meant to sort the strings lexicographically (i.e., "abcd" should come before "efg") instead of by length. You can compare strings lexicographically with the compareTo method: string1.compareTo(string2) is negative, zero, or positive depending on if string1 should precede, equals, or should follow string2.

 

[newjerseyrunner]

Use a bucket sort? There are several recursive sorting algorithms that are not merge or quick.

Split the string up into buckets, then recourse on each bucket.