0

Hi I am writing a naive search/ brute force sorted algorithm but I am not sure how to stop it when it has sorted. I know how to algorithm works and I have written code for it, I have implemented a while(!sorted) loop but that doesnt seem to do the trick. How do I know when to stop calling the algorithm itself i.e. when its sorted. I know for things like bubble sort it is it's big O notation, so you loop n squared times but what about this sorting algorithm? Here is my failed attempt, error that I get is the webpage itself crashing, console.logs don't print out nothing loads, nothing in console.

var 
cols         = 100;
windowWidth  = 800, windowHeight = 800,
dataWidth     = windowWidth/cols,
dataStructure = new Array(cols),
colorCode    = [],
sortedd = new Boolean;

//function discovered on https://stackoverflow.com/questions/951021/what-is-the-javascript-version-of-sleep
function sleep(ms) {
   return new Promise(resolve => setTimeout(resolve, ms));
}

function setup(){

   createCanvas(windowWidth, windowHeight);
   for(var i = 0; i < dataStructure.length; i ++){
       dataStructure[i] = random(800);
       colorCode[i] = "blank";
   }
   while(!sorted(dataStructure)){
    sorted(dataStructure);
   }
}

function naiveSort(arr){

    for(var i = 0; i < arr.length - 1; i ++){
        colorCode[i] = "red";
        var temp = Math.random() * (dataStructure.length);
            swap(arr, i, temp);
            colorCode[i] = "red";
    }
}

function sorted(arr){
    for(var i = 0; i < arr.length - 1; i ++){
        if(arr[i] > arr[i + 1]){
            return false;
        }
    }
    return true;
}

 function swap(arr, a, b){
       var temp = arr[a];
           arr[a] = arr[b];
           arr[b] = temp;
}

Ignore createCanvas, p5js library function, doesn't affect problem

B.brown
  • 21
  • 5
  • 1
    I think it's just that it takes that long to get sorted with those numbers. Try some smaller values of cols. – mrmcgreg Apr 01 '20 at 03:28
  • Hmmm, why does it work with other sort algorithms, I have done quick sort and bubble, they both work at this scale – B.brown Apr 01 '20 at 04:13
  • 1
    You're not calling your `naiveSort` function, and it seems like it is not a sort function because it sets all the elements to `"red"`. I guess you've edited the code a bit to see if you can understand what's going on, but it makes for a very difficult-to-understand question. – Paul Hankin Apr 01 '20 at 07:15
  • @B.brown both of those are polynomial time. This looks exponential. That’s a huge difference! – mrmcgreg Apr 01 '20 at 12:09

1 Answers1

2

Your code is

while(!sorted(dataStructure)){
    sorted(dataStructure);
   }

When it should be

while(!sorted(dataStructure)){
    naiveSort(dataStructure);
   }
aeternalis1
  • 675
  • 4
  • 7
  • Michael Huang still no luck, when I put console.log("test"); in the loop i never get it, I noticed that error I made, I mustve done it mindlessly when trying other apporaches, any idea what could still be causing it? – B.brown Apr 01 '20 at 04:12