1
\$\begingroup\$

A 'slow sort' is probably the slowest practical sort. It compares each element with the elements after it, and swaps immediately if one is greater than the other, and goes back to the start of the array.

For example:

CBAD -> BCAD -> ACBD -> ABCD

My code:

function go() {
   var arrLen=Math.floor(Math.random()*20)+30;
   var arr=Array.from({length:arrLen}).map(()=>Math.floor(Math.random()*20)); // make random array
   txtIn.textContent=arr; //display
   //txtOut1.textContent=arr.sort(function(a,b) {return -(a<b);}); // native sort
   txtOut1.textContent=arr.sort((a,b)=>a-b); // native sort
   var srcPos=0,dstPos,tmp; // declare variables
   while (srcPos<arrLen-1) {
        dstPos=srcPos+1;
        while (dstPos<arrLen) { // three swap routines
             if (arr[srcPos]>arr[dstPos]) {tmp=arr[srcPos];arr[srcPos]=arr[dstPos];arr[dstPos]=tmp;srcPos=0;break}
             //if (arr[srcPos]>arr[dstPos]) {arr[srcPos]^=arr[dstPos];arr[dstPos]^=arr[srcPos];arr[srcPos]^=arr[dstPos];srcPos=0;break}
             //if (arr[srcPos]>arr[dstPos]) {arr[srcPos]+=arr[dstPos];arr[dstPos]=arr[srcPos]-arr[srcPos];arr[srcPos]+=arr[dstPos];srcPos=0;break}
             srcPos++;
             dstPos++;
             }
       }
   txtOut2.textContent=arr; //display
}
<span id='txtIn' style='display:overflow; width:200px; border:2px grey solid'></span><label>data</label><br>
<span id='txtOut1' style='display:overflow; width:200px; border:2px red solid'></span><label>native sort</label><br>
<span id='txtOut2' style='display:overflow; width:200px; border:2px red solid'></span><label>slowsort</label><br>
<button onclick='go();'>go</button>

I have included three swap types, tmp, XOR and add, and commented out two of them. The native sort includes a EMCA2015 arrow function version.

It seems to work okay - admittedly I haven't tested it for other data types, but any feedback would be appreciated.

\$\endgroup\$
2
\$\begingroup\$

There are a few terms one can use to grade code. Correctness, efficiency, readabilty, reuse testability and few other objectively measurable metrics come to mind.

Efficiency isn't really a concern here, and due to the simplicity of the algorithm, neither is correctness. However, it was hard to check whether the code is correct because it's nearly not readable. Also, it's not reusable, at all, as the sorting method is embedded inline and therefore not testable.

With this small overview in mind, let's review the code in detail.

Correctness

The outer while loop will only exit when srcPos == arrLen - 1. This may only happen if srcPos does not get set to 0, which again only happens if two elements weren't in order. Therefore when we have srcPos == arrLen - 1, all elements where lesser or equal to their predecessors and the array is sorted.

Efficiency

This was an inverse goal. While it's already slow, I accidentally misread the code (see the next section) and read:

...
   var srcPos=0,dstPos,tmp; // declare variables
   while (srcPos<arrLen-1) {
        dstPos=srcPos+1;
        while (dstPos<arrLen) { // three swap routines
             if (arr[srcPos]>arr[dstPos]) {tmp=arr[srcPos];arr[srcPos]=arr[dstPos];arr[dstPos]=tmp;srcPos=0;break}
             //if (arr[srcPos]>arr[dstPos]) {arr[srcPos]^=arr[dstPos];arr[dstPos]^=arr[srcPos];arr[srcPos]^=arr[dstPos];srcPos=0;break}
             //if (arr[srcPos]>arr[dstPos]) {arr[srcPos]+=arr[dstPos];arr[dstPos]=arr[srcPos]-arr[srcPos];arr[srcPos]+=arr[dstPos];srcPos=0;break}

             dstPos++;
             }
             srcPos++; // whoops!
       }
 ...

That's even worse, since we end up with a lot of unnecessary comparisons. See "But this can be made worse" below.

It's already slow...

Your code restarts for every inversion and end up with \$\mathcal O(n^3)\$. That's already bad, but you can do worse.

But this can be made worse

Just increase src only in the outer while. Here's the analysis for the case: The worst runtime we can get is for an inverse array, e.g. [5,4,3,2,1]:

[5,4,3,2,1]
[4,5,3,2,1]
[3,5,4,2,1]
[2,5,4,3,1]
[1,5,4,3,2]
...

For \$n\$ elements, we need \$1\$ comparison to move the largest element to the second position, \$2\$ elements to move the second largest to the third, and so on. In summary, we have $$1 + 2 + \ldots + (n-2) + (n - 1) = \frac{n(n-1)}{2}$$ comparisons to get the smallest value to the front. However, contrary to bubble sort, we always reset srcPos to zero. Therefore, the second smallest value won't take less time to get to the front:

[1,4,5,3,2] -- 4 comparisons for 1, 1 comparison for 5-4
[1,3,5,4,2] -- 4 comparisons for 1, 2 comparisons for 4-5, 4-3
[1,2,5,4,3] -- 4 comparisons for 1, 3 comparisons for 3-5, 3-4, 3-2

Although we should be able to only look at the subarray starting at index one, we always have the initial 4 comparisons. So for the second element, we have

$$((n-1)+1) + ((n-1)+2) + \ldots + ((n-1)+(n-3)) + ((n - 1)+(n-2)) = (n-1)(n-2) + \frac{(n-1)(n-2)}{2}$$ comparisons. It's similar for the rest:

[1,2,5,4,3]
[1,2,4,5,3] -- 4 comparisons for 1, 3 comparisons 2, 1 comparison for 5-4
[1,2,3,5,4] -- 4 comparisons for 1, 3 comparisons 2, 2 comparison for 4-5, 4-3

If we complete the induction, we get

$$ \sum_{i=0}^n \frac{(n-i)(n-i-1)}{2} + (n-i-1)\sum_{j=1}^i (n-j) $$ which is inefficient enough. Good job there :).

Readability, reuse and testability

Readability really suffers since the swap logic is put into a single line. Also, there are several values with short names that are not related to your algorithm at all.

Furthermore, we cannot use the sort outside of that snippet. That prevents

  • sorting more than one array
  • custom sort (for example reverse, lexicographic, etc.)
  • testing

So first of all let's make a function:

function slowSort(arr) {
    var src = 0;
    var dest;
    var tmp;

    while(src < arr.length - 1) {
        dest = src + 1;
        while(dest < arr.length) {
            if(arr[src] > arr[dest]) {
                temp = arr[dest];
                arr[dest] = arr[src];
                arr[src] = temp;
                src = 0;
                break;
            }
            dest++;
            src++; // place this one in the outer to make it worse, but
                   // keep in mind to set `src = -1` instead.
        }
    }
}

That's a lot easier to read. Also, we can now

  • sort multiple times
  • get improvements/speed regressions for every call site
  • add additional comparison methods, e.g.

    function slowSort(arr, comp) { ... }
    
  • test the function

Bottom line

Always try to make your code reusable, testable and readable.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.