Thread: What is the logic behind sorting an array list in this algorithm?

The method below is intended to use an insertion sort. For example: if I had a String ArrayList of elements ["code", "computer", "area", "school"], it should sort the elements by insertion sort into ["area", "code", "computer","school"]. I'm having a hard time understanding the logic, and have watched many videos.

I'm mainly struggling to understand what the two for loops are doing.

 public static int insertSort(ArrayList<String> list) {
  int count = 0;
 
  for (int i = 1; i < list.size(); i++)
  {
    String toInsert = list.get(i);
    int j;
 
    for (j = i; j > 0; j--)
    {
      count++;
      if (toInsert.compareTo(list.get(j-1)) >= 0)
      {
        break;
      }
    }
 
    list.add(j, list.remove(i));
  }
  return count;
 }

How have you tried tracing the execution of the code to see what it is doing?
Try adding some print statements that print out the values of the variables as they are set and used. The print out will help you see what the code is doing.

Thanks. I've tried tracing loops, and kinda get it, but I still struggle to get why I need two loops instead of one. Is it possible to do an insertion sort with one loop?

why I need two loops instead of one

Does the code work without both loops? Try it and see what happens. Be sure to use different sets of input data for testing.

Thanks so much for your help! You made me realize that I need the second loop to simultaneously compare 2 values in the array and move them around. Also, how do I do a selection sort on an ArrayList and find the median? I'm studying unit 7 for AP CSA and I'm stuck on sorting and searching. Do I need to make a new post for those topics?

The areas I'm struggling with are sorting and searching (2d and 3d arrays), tracing recursion, and understanding polymorphism/inheritance.

I was also confused a lot by the second loop since 'i' could be 1 and it seems like it might not work.

Do I need to make a new post for those topics?

Yes a new thread for a new topic would be good.