Java IntegerArrayLists:A first year question

Skud

I've done limited topics this year. IntegerArray lists, Binary search, hash sets, linear search, array lists, for,extended for, while, if-else, if expression(We gotta work with what we have). Our lecturer is fairly fond of the old recursion and has tipped the following code to come up or a variation of it. I'm just wondering is there an easier way of re-writing this recursively?

//Assuming you already have created an integer array list with all methods, import java.util.ArrayList etc written.
//Make another one and sort it in ascending order.

public IntegerArrayList sort()
{
  IntegerArrayList sorted = new IntegerArrayList( );
  int thisItem, sortedIndex;

 for (int thisIndex = 0 ; thisIndex < this.list.size() ; thisIndex++ )
   {  
     thisItem = this.list.get( thisIndex );

     sortedIndex = 0;
 while ( sortedIndex < sorted.list.size() && thisItem > sorted.list.get( sortedIndex ))
   sortedIndex++;

   sorted.list.add( sortedIndex, thisItem);
   }
 return sorted;
} 

The way I figure is if I put the whole for loop in an external method and call it recursively(say public void sort2()) with the while loop in another external method and call that recursively also(say public void sort3()). So you end up with something like this.

public IntegerArrayList sort()
{
  IntegerArrayList sorted = new IntegerArrayList( );
  int thisItem, sortedIndex;
 {
  sort2();
  sort():
 }
 return sorted;
}
public void sort2()
{
  if ( int thisIndex = 0 && thisIndex < this.list.size() )
   {
     thisItem = this.list.get(thisIndex); 
     thisIndex++;
   }
  sort2();
  sort3();
}
public void sort3()
{
  sortedIndex = 0;
    if (sortedIndex < sorted.list.size() && thisItem > sorted.list.get(sortedIndex))
      sortedIndex++;

       sorted.list.add( sortedIndex, thisItem );
   sort3();
}

Or else a friend suggested doing it by finding max and min vlaues of the array list and sorting it in the while loops' place.

Another alternative suggestion is using the binary search for the max and min values or I could do it a final simple way and lose marks for doing it a long winded (not that recursion is long winded enough in this case at least)

public IntergerArrayList sort()
{
  IntegerArrayList sorted = new IntegerArrayList( );
  int maxSoFar = list.get( 0 );
  int i = 1;

 if ( i < list.size() && list.get(i) > maxSoFar )
  maxSoFar = list.get(i);
  
  return maxSoFar;
  sort();
}

Please help this is a tricky little number and could be worth 20% of a 20 credit module. Just suggest corrections to my code or an easier alternative way? Thanks for the help.

Skud

bump

PhantomBeaker

Personally, I haven't really played with arraylists too much. But here's how I'd approach it. I won't give code, but you should get a good idea.

The underlying data structure is an array, right?

Most recursive algorithms are recursive because they do something slightly sweeter than pure iteration does. Looking at your iterative example: there's a for loop inside a for loop. I'm assuming you've done some Big-Oh notation. If there're two nested for loops it tends to be run in O(n^2) time - i.e. the running time is proportional to the size of the dataset in the arraylist. That's pretty bad. In fact, you're hosed if you have large sets of data in there.

So, if you do recursion right, you can get it done pretty nicely. A popular recursion strategy is commonly known as Divide and Conquer. What would happen with sorting is that you take the dataset and chop it in half, and sort those seperately. Those bits are still probably quite difficult to sort, so you chop THEM in half and sort them again.

When you hit 1 or 2 elements in your list, that's very easily sortable. Then you can just interleave the two halves

So, the running time ends up becoming O(n log(n)) but I won't go into it now. But that's a better way to take care of it.

So a rough sort of pseudocode would be.

public void sort(){
     if(length > 1){
           // Chop it in half
           first_half.sort();
           second_half.sort();

           // interleave the elements from the two halves.

     } 
}

Does that help?

Skud

thanks for the reply, I think I get what you are saying but we haven't done it so I think he'll know But it does give me some ideas. Basically sort the lists in half and interleave? When I get time later I'll search google for interleaving but I do have an idea where you are coming from.

PhantomBeaker

Yeah. that's the common recursion theme.

Just think, imagine you have a deck of cards but in two piles. You know that those two piles are already sorted. So, that means when it comes to making a bigger pile, you just take the bigger/smaller (however you're sorting it) of the piles and put it on the new pile. Keep doing that for all of your two piles, and you now have a bigger pile all happily sorted. (That's the n factor in the O(n log(n)) )

I'm not giving the code because basically that bit is trivial to implement.

Take care,
P.B