Sorting 99% ordered list

I'm working with a time series (of numbers, e.g., temperatures, stock prices, etc.) where I want to maintain a sorted moving window of N elements (N generally < 200).

In other words, I want to take Data 1 .. 100, sort it; then Data 2 .. 101, sort that; and so on down the line.

I figure once the array has been filled & sorted for the first time, there must be a relatively elegant & efficient solution for removing the oldest data point & inserting the newest one in the correct location.

One solution would be to simply replace the oldest data point with the new one, then do a bubble sort since that method is fairly efficient when data is mostly sorted. (Only one element will be out of position, though it may require multiple exchanges to fix.)

But it seems to me there must be an even better approach. It should be possible, for instance, to take advantage of the fact that for these particular time series, the newest data point will almost always have a value very close to the value of the previous data point that was added.

Since this code will be called very frequently, the most efficient algorithm will definitely help a lot. If it's relevant, I'm working in Visual Basic 6 for the moment.

Many thanks for any suggestions!

If only one element is out of place, then there's no need to apply a sort algorithm to the entire array. The easiest thing to do, I think, would be to start at the initial position of the new element and step up or down the array as appropriate until we find the place where the element should be positioned in order for the array to remain sorted. Then, once we know the initial position and target position, shift all the existing array elements in that interval up or down as needed (overwriting the old value at the initial position), then set the new element in its target position. I don't know if this could be improved, but it is O(n) and doesn't shuffle items around any more than is absolutely necessary.

Here's a bit of pseudocode that shows how it would work. I don't remember much about BASIC syntax but I figured this would be good enough for you to figure out what I'm saying. :)

Code:

---

// This bit of code takes a value called NewElement, replaces the value
// at array index InitialPos with that value, then shifts the values
// as needed so that the array remains sorted
//
// Inputs required:
//    NewElement = the value of the new element to insert
//    InitialPos = the array index at which to insert NewElement
//    Array      = the actual array of values
//    Min        = the lowest valid array index
//    Max        = the highest valid array index
//
// Internal variables used:
//    TargetPos  = the array index where NewElement should be when
//                  the array is properly sorted
//    Direction  = the direction to step through the array when
//                  shifting existing elements
//    CurrentPos = loop counter, used to shift array elements

// initialize the target position
TargetPos = InitialPos

// find target position if less than initial position
While TargetPos > Min And NewElement < Array(TargetPos - 1)
    TargetPos = TargetPos - 1

// find target position if greater than initial position
While TargetPos < Max And NewElement > Array(TargetPos + 1)
    TargetPos = TargetPos + 1

// determine direction to step through array
If TargetPos < InitialPos Then
    Direction = -1
Else
    Direction = 1

// shift existing array elements into their proper places
CurrentPos = InitialPos
While CurrentPos != TargetPosition // != is 'does not equal'
{
    Array(CurrentPos) = Array(CurrentPos + Direction)
    CurrentPos = CurrentPos + Direction
}

// insert new element
Array(TargetPos) = NewElement;

---

Edit: I don't know if you're familiar with C, but if you're interested, here's the C code I wrote to test this:

Code:

---

// -InsertElement()-
// Replaces the element at InitialPos with the value NewElement,
// then repositions the element so that the array remains sorted.
//
//    Array      = the array of values
//    ElemCount  = the number of values in the array
//    NewElement = the new value to be inserted
//    InitialPos = the location of the value to be replaced
//
// Return value: the new location of NewElement, or -1 if an
// invalid argument was received.
int InsertElement(int* Array, int ElemCount, int NewElement, int InitialPos)
{
    int TargetPos = InitialPos;
    int Direction, Index;

    // test for invalid index
    if (InitialPos < 0 || InitialPos >= ElemCount)
        return -1;

    // find target position
    while (TargetPos > 0 && NewElement < Array[TargetPos - 1])
        TargetPos--;
    while (TargetPos < (ElemCount - 1) && NewElement > Array[TargetPos + 1])
        TargetPos++;

    // shift elements
    Direction = (TargetPos < InitialPos) ? -1 : 1;
    for (Index = InitialPos; Index != TargetPos; Index += Direction)
        Array[Index] = Array[Index + Direction];

    // insert new element
    Array[TargetPos] = NewElement;
    return TargetPos;
}

---

Would it be too much effort to redo it as a linked-list instead of an array?

It would probably be the most efficient, although obviously it is a little trickier to implement then a simple array/bubblesort.

Quote:

---

Originally Posted by Zeb

Would it be too much effort to redo it as a linked-list instead of an array?

It would probably be the most efficient, although obviously it is a little trickier to implement then a simple array/bubblesort.

---

In my case, yes, since I'm a newbie.

I've worked on Devourer's suggestion & have come up with something that seems to work, though getting there took some extra thought. (Finding the correct target position was trickier than I thought it would be, & I couldn't get the While loop to handle shifting elements both up & down for some reason.)

I'm still surprised though that there's not some super-efficient algorithm for sorting a list that has only 1 item out of order. Sounds like it's time to run some tests :-)

Thanks.

Quote:

---

Originally Posted by sv651

I've worked on Devourer's suggestion & have come up with something that seems to work, though getting there took some extra thought. (Finding the correct target position was trickier than I thought it would be, & I couldn't get the While loop to handle shifting elements both up & down for some reason.)

---

What do you mean about getting the while loop to shift elements both up and down? That should not be necessary if only one item is out of place.

If you're talking about the while loops used to find the target position of the new item in the array, then it's not possible for both loops to run as long as the array is sorted (except for that one element). Suppose your new element N is located between elements A and B in an array sorted in ascending order. Then N can only move towards the lower indices if N < A, and N can only move towards the higher indices if N > B. But because we know that the array is sorted (except for N), then if N < A, we know N < B, and similarly if N > B, then N > A. So the search to find N's target position cannot move both ways.

If you're talking about the while loop (or in the case of the C code, the for loop) used to shift elements after the desired position has been found, then it's also never useful to shift elements both up and down the array. If some element N is to move down X places in the array, then we compensate by shifting each of X elements one place up in the array. Similarly, if we wish to move N up X places, we compensate by shifting X elements down a single place. In that sense I suppose you could say that elements are moving in both directions -- N in one direction, and the elements it displaces in the other -- but that's not really what's happening in the code. N is not "shifted" at all in the algorithm I posted; it's not even inserted into the array until its final place in the array has been prepared.

If you get this working and still need more speed, you could try replacing the method by which I've located the new element's target position with a binary search. This would improve the complexity of the position location from O(n) to O(log n). The overall algorithm would still be O(n) since the insertion code is necessarily O(n), but it would be an improvement.

A simple insertion sort will sort a mostly sorted list in approximately O(n). See Sedgewick's Algorithms for details.

You will have a very hard time beating this sort for mostly ordered lists.
--
EV

Quote:

---

Originally Posted by sv651

I'm still surprised though that there's not some super-efficient algorithm for sorting a list that has only 1 item out of order. Sounds like it's time to run some tests :-)

---

Because arrays are stored sequentially in memory (well, most arrays...), then either way to do this you are going to have to move a chunk of memory. Now, there is probably a quicker way of doing it than iterating through each element you want to move and doing it one at a time, but in VB, I don't know what it would be.

use sorting tree (std::set). You need to delete last element add add new - it would take O(log(n)).

Quote:

---

Originally Posted by RoboTact

use sorting tree (std::set). You need to delete last element add add new - it would take O(log(n)).

---

he's using VB6.

Yet he can get the implementation of algorithm (I don't know if there is one in VB's standard library) - or even implement it himself...

Quote:

---

Originally Posted by Smasher/Devourer

What do you mean about getting the while loop to shift elements both up and down? That should not be necessary if only one item is out of place.

---

Whoops, I meant to say that I was struggling with this part of your code:

// shift elements
Direction = (TargetPos < InitialPos) ? -1 : 1;
for (Index = InitialPos; Index != TargetPos; Index += Direction)
Array[Index] = Array[Index + Direction];

Of course, it's been several days now & I can't remember exactly where I ran into trouble. Sigh.

In any event, thanks again for all the help & suggestions. I'll take a look at the insertion sort & see if it might help.

Cheers.

Quote:

---

Originally Posted by Zeb

Because arrays are stored sequentially in memory (well, most arrays...), then either way to do this you are going to have to move a chunk of memory. Now, there is probably a quicker way of doing it than iterating through each element you want to move and doing it one at a time, but in VB, I don't know what it would be.

---

Ok, from my understanding of your question. You have a bunch of elements that have sorted. You then want to pop the oldest one, and insert a new one.

My answer to this Is god's gift to programmers. use a heap. A heap is a semi sorted array, basically it's like a binary tree, except you can allocate it in an array. what you do is demand that an element be older than it's two children. You don't care about the relation between the two children as long as they are newer than the parent. Using this data structure you can order the tree initially really efficiently. It's been a while since i looked at the specifics but i know you can do this in at most n*log(n) time. then inserting and deleting an element takes only log(n) time. If you look up a heap there should be plenty of resources available that can explain how to create one much better than i can.

now if you need ALL elements to be sorted correctly at all times, I'd say to modify an insertion sort. You would put the new element in the place of the old one, and then move that element to where it needs to be with regards to the others.

if you don't mind not being able to access a certain element in better than (n) time you could use a linked list.

anywho these are the three best data types i could think of. good luck any questions shoot me an e-mail or private message.

tex23bm

Quote:

---

Originally Posted by RoboTact

use sorting tree (std::set). You need to delete last element add add new - it would take O(log(n)).

---

RoboTact at first when I saw this thread I thought that the best way would be a Binary Search Tree, but it is not. Becouse every new element has a value close to the last one the tree is going to look like linear list.
So for the insert and delete operations still to have the complexity of O(LogN) you will have to balance it. But balancing a dynamic represented tree is many times slower and harder then just goint through a static array.

sv651 If you don't need the array to be necesarily sorted but you need one of those operations - find the smallest element, find the biggest element, the oldest, the newest, find the nomber of elements smaller or bigger then some element there are many data structures whit which you may implement those elements with O(LogN)

Finding smallest/biggest/n-th element is O(1) per iteration (shifting the window). Complete sorting can't be faster then C*logn, so search tree is OK. Balancing is included in insert/remove operation and taking the same O(logn).

I have a question. The author didn't mention what is the range of the values. If it is small a linear time sorting algorithm can be implemented.

RoboTact excuse be for my not so good english but I did not understand the last post. You can implement insert, delete and find the k smallest element in O(1) ? If it is so - you are wrong.

You can find smallest element in O(1), and you can implement insert/delete in O(logn). Given the limitation of values, you may replace log(n) with appropriate constant and use same estimations.

Yes, you mean heap. But you can't replace insert/delete O(logN) with O(1)

Quote:

---

Originally Posted by vedex

Yes, you mean heap. But you can't replace insert/delete O(logN) with O(1)

---

Who said I'm to?

Quote:

---

Originally Posted by RoboTact

use sorting tree (std::set). You need to delete last element add add new - it would take O(log(n)).

---

of cource just adding and removing an item takes O(logn) but firstly we should make a heap sorted array which takes O(nlogn) then adding and removing items which probabaly takes O(logn)..so because OP should initialy make a sorted array so I think its time is O(nlogn).

You can't sort array in time less then nlogn, so it's useless to discuss this component.

Quote:

---

Originally Posted by RoboTact

You can't sort array in time less then nlogn, so it's useless to discuss this component.

---

Quote:

---

Originally Posted by vedex

I have a question. The author didn't mention what is the range of the values. If it is small a linear time sorting algorithm can be implemented.

---

i don't think so

[Edited Post]

Quote:

---

Originally Posted by RoboTact

use sorting tree (std::set). You need to delete last element add add new - it would take O(log(n)).

---

//not familiar with std::set I just consider a simple array
if we have a sorted tree like this

Code:

---

2
4 6
8 13 16 18
20 22 25 27 30 32 35 37

---

then if we add a new element(for example 23) instead of 37..for keepping the tree sorted again,just a simple percolate is not sufficient,so it doesn't take logn :confused:
I think we should recall the heap-sort function(nlogn). maybe it could be optimized to n but realy can't get how you could get logn?

Take a look at binary heap data structure.

well, I checked that link(I knew them)
if we have this min binary heap(it is sorted)

1
3 5
8 10 14

then if we add a new element for example 2 it becomes

1
3 2
8 10 14 5

well,its clear it takes logn but our min binary heap is not sorted anymore, but we wanted when we add a new element it remains sorted
I hope I could represnt my meaning :o

Just read about that data structure more carefully. It doesn't make sense to just "add" element, violating structure - of course inserting and deleting operations mean adding and deletion of element preserving heap property.