I have a JS application that needs to execute the complex look of a large array and then display it. Using the built-in array.sort(cb) method can take up to 1 second with my data. It's long enough for my user interface to get noisy.
Since the user interface is tall enough to display a subset of the sorted array on the screen and the rest are below scrolling or paginated, I had an idea. What if I made an algorithm that went through a large array and quickly did a sort so that the top N elements were perfectly sorted, but the rest of the elements in the array were incorrectly sorted. Every time I run my algorithm, it would sort a little more array from top to bottom.
So I could break my processing into pieces and have a smooth interface. For the first few seconds, the array will not be perfectly sorted, but the flaws will be below the scroll bar so that they are not noticed.
My naive solution would be to write my own "Selection Sort" with the possibility of breaking after N matches and resuming later, but "Selection Sort" is a pretty terrible algorithm. Faster algorithms (in my opinion) should be completed to ensure that the top N elements are stable.
Does anyone know of an existing solution for this? I'm crazy? Any suggestions?
UPDATE
Taking the idea suggested by @moreON, I wrote a custom QuickSort that resets as soon as it has the required accuracy. For this data, its own form took 1 sec. Regular QuickSort took about 250 ms, which is already surprisingly better. QuickSort, which helps out after the first 100 items are sorted, took more than 10 ms, which is much better. Then I can take an extra 250 ms to finish the sort, but that doesn't really matter, because the user is already looking at the data. This reduces the user delay from 1 sec to 10 ms, which is pretty good.
//Init 1 million random integers into array var arr1 = []; var arr2 = []; for(var i=0;i<1800000;i++) { var num = Math.floor(Math.random() * 1000000); arr1.push(num); arr2.push(num); } console.log(arr1); //native sort console.time("native sort"); arr1.sort(function(a,b) { return ab; }); console.timeEnd("native sort"); //1sec console.log(arr1); //quicksort sort Ref: https://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/ function swap(arr, a, b) { var temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } function cmp(a,b) { return (a<b); } function partition(items, left, right) { var pivot = items[Math.floor((right + left) / 2)]; var i = left; var j = right; while (i <= j) { while (cmp(items[i],pivot)) i++; while (cmp(pivot,items[j])) j--; if (i <= j) { swap(items, i, j); i++; j--; } } return i; } function quickSort(items, left, right, max) { if(max && left-1 > max) return items; //bail out early if we have enough if (items.length > 1) { var index = partition(items, left, right); if (left < index - 1) quickSort(items, left, index - 1, max); if (index < right) quickSort(items, index, right, max); } return items; } //sort first 100 console.time("partial Quicksort"); arr2 = quickSort(arr2,0,arr2.length-1,100); console.timeEnd("partial Quicksort"); //10ms console.log(arr2); //sort remainder console.time("finishing Quicksort"); arr2 = quickSort(arr2,100,arr2.length-1); //250ms console.timeEnd("finishing Quicksort"); console.log(arr2);