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.
- 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.
or in psedocode:
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.