Sorting values, but only if they are X more than current order

Question

Hi,

I've been searching Google (and stack overflow of course!) for a way to sort a list of integers by value, but also by an extra factor. I'm looking for some sort of algorithm to implement I suppose. So far, I have an array in Delphi 2007 that sorts the values from largest to smallest, but now I would like it to sort values that are only X number more than the previous number in the list.

For example, the values 5, 7, 25, 15 are currently sorted to 25, 15, 7, 5. The order I am trying to get now, with the X value being 5, is 25, 15, 5, 7. As you can see, the 5 and 7 haven't switched positions because there isn't a difference of more than 5 between them.

Not sure if I'm explaining this particularly well, but that's the general idea.

One more example would be the values 10, 40, 18, 20, 16, 28. Sorted, they should be 40, 28, 18, 20, 16, 10. 18, 20 and 16 haven't moved, because again, there is not more than 5 between each of the numbers.

The idea behind it is so that the item linked to the number (for example the number of times something has been ordered) isn't changing all the time because of a difference of only 1 or 2. For example, if the list of most frequently ordered paper is displayed on a web page by frequency purchased, then the order of a particular type of paper will only change for the user if it has been ordered more than five times more than the next most frequent.

Hope this makes sense, and thanks for your time!

Answer 1

Having thought about this some more I think a bubble sort is the only type of sort that will work. This is because in a bubble sort a number must be explicity larger (or in this case 5 larger) than the numbers above it in order for them to change places. This is exactly what you have asked for.

From a high level point of view here is what I think you will need:

1. A bubble sorting implementation that takes in a custom compare function.

2. a compare funtion that returns equal if the difference is less than 5.

Merging these 2 things should leave you with what you are after.

Answer 2

I think your requirement leads to really strange results. You can, ultimately, have a sort order where items sorted exactly the wrong way round, and how they are sorted depends on how they change.

I think you need to establish "classes" of values (use percentiles?) and then sort the newspapers alphabetically within each class.

For example: barely ordered (90% of papers are ordered more than this one), lower than median (50% of newspapers are ordered more than these), higher than median, top 10 ordered (sorted by number of orders of course).

Answer 3

At the very least you need to use a stable sort, i.e., a sort that preserves ordering of equivalent values.

Once you have that, you should probably define your comparison as if abs(a - b)<5, equals, otherwise, do the normal comparison. That makes compare(a, b)==compare(b, a), which is something that most good sorting implementations should assert.

If you are using C++, you can use std::stable_sort to do this.

MSN

Answer 4

Try sorting with custom comparing function , you can quickly try this if you fill TList with numbers and call MyList.Sort(myCompareFunc);

function  myCompareFunc(item1,item2:Pointer):Integer;
var 
 v1,v2:Integer;
begin

  v1 := (integer)item1;
  v2 := (integer)item2;

  if v1 > v2 then 
       result := 1
  else if (v1 < v2 )
       result := -1
  else 
       result := 0

  //most important
  if abs(v1-v2) < 5 result := 0 ; 

end;

Answer 5

It might make sense to apply your sorting principle to an almost sorted list, but you should be aware of the fact that it violates a basic assumption on general sorting algorithms: That the elements to be sorted form a total order. This roughtly means that the < operator behaves the way it does for real numbers. If you violate this rule, then you can get strange effects, and library algorithms might not even terminate (or even crash, I've seen this happen for std::sort in C++).

One way to modify your idea to make it a total order is to sort with respect to each number rounded down to the closest multiple of 5.

Answer 6

I think this needs two passes. On the first pass, identify any values which are subject to being sorted, and on the second pass actually move only the ones which were such identified. In your second example, using an array of Y/N with Y being to sort, you would end up with [ Y, Y, N, N, N, Y ], then by only sorting the values Y, the N's would be "ignored not eligible for sorting" you would get your resulting list of [40, 28, 18, 20, 16, 10]. The group of N (will always be a group based on the definition) should be compared to as the value of the highest in its group.

Answer 7

TList.Sort won't work because it uses quick sort algoritham as mghie commented.

Bubble sort algoritham is not that fast, here is implementation so you can try, this time in pascal.

var I,N,T,D:Integer ;
    A:array of Integer;
    Change:Boolean;
begin

  SetLength(A, 4);
  A[0] := 5;
  A[1] := 7;
  A[2] := 25;
  A[3] := 15;

  Change := True;
  N := High(A);

  while Change do
  begin
    Change := false;

    for I := 1 to N do
    begin
       D := A[I]-A[I-1];

       if  (D > 5)  then
       begin
          T := A[I-1];
          A[I-1] := A[I];
          A[I] := T;
          Change := true;
       end;
    end;
  end;
end;