Java Recursively Sort an ArrayList

[Satlen]

Hello fellow programmers, I am currently working on an assignment and the goal is to output each object in an arraylist by ascending area (the objects are shapes with different dimensions). My question to you is what would be the best way of sorting the objects out if I have a method getArea() to retrieve the area for each object in the list? I have to use recursion so I will probably be using merge sort but should I work with the arraylist directly or grab all the areas and work with only the areas (I am not sure how to keep track of which area belongs to which object)? I am open to any ideas so if you got something post it!

 

Edit: I do not want to use the comparable interface or any sort methods from java, I am trying to learn how sorting works and the best practices in sorting.

[Marvzl1357]

Hello fellow programmers, I am currently working on an assignment and the goal is to output each object in an arraylist by ascending area (the objects are shapes with different dimensions). My question to you is what would be the best way of sorting the objects out if I have a method getArea() to retrieve the area for each object in the list? I have to use recursion so I will probably be using merge sort but should I work with the arraylist directly or grab all the areas and work with only the areas (I am not sure how to keep track of which area belongs to which object)? I am open to any ideas so if you got something post it!

 

Edit: I do not want to use the comparable interface or any sort methods from java, I am trying to learn how sorting works and the best practices in sorting.

 

I'm not sure how to sort it recursively, but the way I managed something similar was to have two arrays, say one for area and one for object, then do sorting on the area array but do the exact same rearranging on the object array. That way area[0] corresponds to object[0] and area[2] should correspond to object[2] etc etc. 

[prolemur]

I'm not sure how to sort it recursively, but the way I managed something similar was to have two arrays, say one for area and one for object, then do sorting on the area array but do the exact same rearranging on the object array. That way area[0] corresponds to object[0] and area[2] should correspond to object[2] etc etc. 

Yes doing it this way would only call the getArea function, the amount of items in the array, times.

[Satlen]

Alright guys, I actually figured it out. I ended up not going with the merge sort because that was making things more complicated than they needed to be. I ended up using a much simpler sorting method which basically sets the the first value in a given range to the min and compares it to the rest, swaps the two elements if it finds a smaller one, then is recursively called until everything is sorted.

 

Here is a snippet of my method in case anyone is curious in the future:

    private static void sortObjects(ArrayList<GeometricObject> list, int low, int high){    	if (low < high){    		int minIndex = low;    		GeometricObject min = list.get(low); //set min to first object in range    		for (int i = low + 1; i <= high; i++){ //loop through all values other than first    			if (list.get(i).getArea() < min.getArea()){ //check if the value is smaller than current min    				min = list.get(i); //if it is update the min    				minIndex = i; //store min index so we can swap locations later    			}    		}    		Collections.swap(list, low, minIndex); //move the original min to new min's old index (tricky wording)    		list.set(low, min); //set the old lowest to the new lowest using store min value    		sortObjects(list, low + 1, high); //call it again    	}    }

[imthewalrus]

Hello fellow programmers, I am currently working on an assignment and the goal is to output each object in an arraylist by ascending area (the objects are shapes with different dimensions). My question to you is what would be the best way of sorting the objects out if I have a method getArea() to retrieve the area for each object in the list? I have to use recursion so I will probably be using merge sort but should I work with the arraylist directly or grab all the areas and work with only the areas (I am not sure how to keep track of which area belongs to which object)? I am open to any ideas so if you got something post it!

 

Edit: I do not want to use the comparable interface or any sort methods from java, I am trying to learn how sorting works and the best practices in sorting.

 

Why not use a quick sort? It doesn't need that much memory (merge sort does since you are making multiple arrays). 

[imthewalrus]

 

- Algorithm snippet -

 

That's called a selection sort! If your list is really long you will find that it might be inefficient but good job!

[Satlen]

That's called a selection sort! If your list is really long you will find that it might be inefficient but good job!

 

Yeah, that is basically why. My list only has a size of 5 so I did not need to be super efficient. Plus in class we have not gone over the merge sort yet. We have only covered selection and insertion sort so I didnt want to jump too far ahead. So we will for sure being doing work with more efficient sorts. Honestly the real challenge for me was understanding how to do the rearranging with the arraylists since most examples are given using standard arrays and numbers.