www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - What is this sort called?

reply Stefan Koch <uplink.coder googlemail.com> writes:
Hi,

I've come across a sorting algorithm ato build up a sorted array 
and I am not sure what it's called.
Perhaps someone here knows what the name of it is.

It goes like this:

  - assume it already sorted
  - compare the element against the highest element we have seen 
so far, if it's
    higher put the incoming element to the right and continue.
  - if it's not higher we have to search for the place where it 
goes
       - for the search we first check if it's higher than the 
last record that did not come in order, if it is than that's were 
we start our search. if it's not we start searching from the 
beginning of the array.
    once we have found the index where the value needs to be 
inserted we copy all the records that are to the right of it. one 
position to the right, and stick in our value, then we update the 
index of the last record that did not come in order and continue.

or in psedocode:

```d
void insertSorted (Record[] records, Record r, SortState* s)
{
   if (r.value > records[$-1].value)
   {
      records ~= r;
   }
   else
   {
      int ourPlace = 0;
      if (records[s.lastUnsortdedElementIndex].value < r.value)
      {
         ourPlace = s.lastUnsortedElementIndex;
      }
      while(records[ourPlace].value < r.value)
      {
         ourPlace++;
      }
      // after the while loop is done ourPlace is the index at 
which we should go
      {
         records.length = records.length + 1;
         //everyone to the right of our place move one further.
         foreach(i; ourPlace .. records.length -1)
         {
           records[i+1] = records[i];
         }
         records[ourPlace] = r;
         s.lastUnsortedElementIndex = ourPlace;
      }
   }
}
```

I am fascinated by this because it seems to perform so poorly 
once the initial assumption is violated.
However how poor it performs is directly linked to the amount of 
disorder in the incoming stream.
Aug 27 2021
next sibling parent Stefan Koch <uplink.coder googlemail.com> writes:
On Friday, 27 August 2021 at 15:02:59 UTC, Stefan Koch wrote:

 or in psedocode:

 ```d
         foreach(i; ourPlace .. records.length -1)
         {
           records[i+1] = records[i];
         }
 ```


I have been alerted to a rather nasty bug in this transcription.
it only works if you iterate the array in reverse as otherwise,
you'll override all values with `records[ourPlace]`

I guess `foreach_reverse` does have a place in the language after 
all.
Aug 27 2021
prev sibling next sibling parent Stefan Koch <uplink.coder googlemail.com> writes:
On Friday, 27 August 2021 at 15:02:59 UTC, Stefan Koch wrote:

 Hi,

 I've come across a sorting algorithm ato build up a sorted 
 array and I am not sure what it's called.
 Perhaps someone here knows what the name of it is.

 [...]


I've attempted to use "the sound of sorting" to visualize what's 
happening.

https://www.youtube.com/watch?v=NQ5iGTQQ1vY

Ironically without sound :)
Aug 27 2021
prev sibling parent reply Dennis <dkorpel gmail.com> writes:
On Friday, 27 August 2021 at 15:02:59 UTC, Stefan Koch wrote:

 I've come across a sorting algorithm ato build up a sorted 
 array and I am not sure what it's called.


I don't think it has a name, it looks like insertion sort with an 
ad-hoc optimization that it tries to guess where to insert based 
on the input being mostly monotonically increasing.
Aug 27 2021
parent Stefan Koch <uplink.coder googlemail.com> writes:
On Friday, 27 August 2021 at 19:25:46 UTC, Dennis wrote:

 On Friday, 27 August 2021 at 15:02:59 UTC, Stefan Koch wrote:

 I've come across a sorting algorithm ato build up a sorted 
 array and I am not sure what it's called.


 I don't think it has a name, it looks like insertion sort with 
 an ad-hoc optimization that it tries to guess where to insert 
 based on the input being mostly monotonically increasing.


I was guessing that it's some insertion sort.
Comparing it with a generic insertion sort without the 
optimization it does quite well.
Aug 27 2021