Infinite Loop in recursive algorithm

Question

I need to make a pivot sorting algorithm where essentially you take the first item of a linked list, sort it into two separate lists one with items greater than or eual to the first item, and one with items less than the first item, then sort them recursively until you reach a linked list of size 1 where it is already sorted, then just merge together the lesser and greater than lists to form a sorted list.

My algorithm keeps getting stuck on the last item in an infinite loop and I've been without sleep now for about 23 hours and need a fresh pair of eyes to spot where I'm making the mistake. If you could help out I would be much obliged.

The Linked list class is simple, two items, first is just a positive integer, second is of course the next item in the list. The code gets caught in the Sort() function when it hits the last item and doesn't then append the last items together

public class PivotSort {
   public static void main(String[] args) {
      try {
         intList x = intList.CreateFromUserInput(); // just makes a linked list
                                                    // from numbers I type in
         x = Sort(x);
         x.PrintList();
      } catch (Exception e) {
         System.out.println(e);
      }
   }

   public static intList Sort(intList list) {
      if (list == null || list.item == null)
         return list;
      return Append(Sort(Part_Less(list.item, list)),
            Sort(Part_Greater(list.item, list)));
   }

   public static intList Part_Less(int N, intList L1) {
      if (L1 == null)
         return null;
      if (L1.item < N)
         return new intList(L1.item, Part_Less(N, L1.next));
      else
         return Part_Less(N, L1.next);
   }

   public static intList Part_Greater(int N, intList L1) {
      if (L1 == null)
         return null;
      if (L1.item >= N)
         return new intList(L1.item, Part_Greater(N, L1.next));
      else
         return Part_Greater(N, L1.next);
   }

   public static intList Append(intList L1, intList L2) {
      try {
         if (L1 == null)
            return L2;
         if (L2 == null)
            return L1;
         for (intList curr = L1; curr != null; curr = curr.next) {
            if (curr.next == null) {
               curr.next = L2;
               break;
            }
         }
         return L1;
      } catch (Exception e) {
         System.out.println(e);
         return null;
      }
   }
}

If two elements are equal to each other, then how do you want to produce a "list of size 1" from "elements that are greater than or equal to" one of the two? The 'greater-or-equal' set will always contain both elements under this logic (unless the pivot is a member of neither set) — John Dvorak
– John Dvorak, Commented Nov 3, 2012 at 22:30
From the description it seems you are trying to implement QuickSort - am I correct? — John Dvorak
– John Dvorak, Commented Nov 3, 2012 at 22:33

phant0m · Accepted Answer · 2012-11-03 22:54:12Z

2

The problem is, that your base case of Sort can never be reached for the second call:

Sort(Part_Greater(list.item, list))

The Part_Greater() function will at first construct a list that contains all items bigger or equal than the first item. Let's say this is your origianl list:

10 5 7 11 15 7 16 20

Part_Greater() will construct a list, that contains 10 11 15 16 20. When you pass that to Sort, it will call Part_Greater() on that very list again, which results in just that list.

Since no elements are removed after the first call to Part_Greater(), you enter an infinite recursion.

What you need to do is remove the pivot element from the list. This ensures, that with every recursive step, your list of numbers gets shorter by at least one, eventually hitting the base case when the list is empty.

return Append(
    Sort(Part_less(list.item, list.next)),
    new intList(list.item, Sort(Part_Greater(list.item, list.next)))
);

edited Nov 3, 2012 at 22:54

answered Nov 3, 2012 at 22:39

phant0m

17k6 gold badges52 silver badges84 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Adam James Over a year ago

Thanks, I knew I was forgetting something, I know there is a more elegant way to solve it but I am so tired right now I just want sleep XD Thanks for your help.

phant0m Over a year ago

@user1797238 Yes, I have simplified it now. That should work as well.

Collectives™ on Stack Overflow

Infinite Loop in recursive algorithm

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related