Sorting algorithm method timeout occurred

Processing Coding Questions
1

Hey everybody! I’m trying to make a really stupid sorting algorithm as a joke, but I can’t seem to get it to work. It’s called “Supernatural Occurence Sort”, and basically, my idea was as follows:

if nArr is sorted somehow
       sorted = true and we're done
if nArr is not sorted
       if the current value is less than/equal to the next value
                go to the next value
       if the current value is greater than the next value 
                swap the current value with a random value in the list
if we're at the end of the list and all the numbers are somehow in the right order
       sorted = true and we're done
if we're at the end of the list and the numbers are not in the right order
       call the method again

So it says in the console a timeout occured at [a random packet] each time I run the code, so i’m not sure what i’m doing wrong. Any tips? My code is down below:

int[] nArr = new int[10];
boolean soFarSoGood = false;
boolean sorted = false;
void setup() {
  for (int i = 0; i < nArr.length; i++) {
    nArr[i] = (int)random(1, 10);
  }
  supernaturalOccurenceSort();
}

void draw() {
  for (int i = 0; i < nArr.length; i++) {
    print(nArr[i] + " ");
  }
  println("Sorted: " + sorted + " SFSG: " + soFarSoGood);
}

void supernaturalOccurenceSort() {
  for (int i = 0; i < nArr.length; i++) {
    if (i < nArr.length - 1 ) {
      if (nArr[i] >= nArr[i+1] && soFarSoGood == true) {
        soFarSoGood = true;
      } 
      if (nArr[i] < nArr[i+1]) {
        soFarSoGood = false;
        swap(nArr[i], nArr[(int)random(1, 10)]);
      }
    } 
    if (i >= nArr.length-1) {
      if (soFarSoGood == true) {
        sorted = true;
      }
    }
  }
  if (sorted == false) {
    supernaturalOccurenceSort();
  }
}

void swap(int a, int b) {
  int temp = nArr[a];
  nArr[a] = nArr[b];
  nArr[b] = temp;
}
1 Like
2

StackOverflowError: This sketch is attempting too much recursion.

Your problem is twofold – first, this may run for a long time. For arrays of any appreciable size, it could run forever (well, for longer than the life of your laptop). That is because you aren’t biased towards increasing in order – you are actively destroying order with your random swaps. If you started with this list:

0123456798

and ran your sort, the list will become worse.

0129456738

And worse.

5129604783

And worse…

At a certain point you are doing something like calling (int)random(99999) and telling the program to stop when it guesses correctly.

Second problem: recursion. You are calling your function from inside your function each time – you may need to do this a few hundred thousand times. But this increases the stack, and eventually causes a stack overflow.

supernaturalOccurenceSort(0123456798)
   supernaturalOccurenceSort(0129456738)
      supernaturalOccurenceSort(5129604783)
        ...x999999

So, instead you would use a while() loop, not recursion.

Recursion works great for sorting that involves progress – for example, divide and conquer, where at each step you are doing a smaller part of the job, and all the small completed jobs add up to one big job that is complete. That is definitely not the case in your approach.