Сортировка значений, но только если они на X больше текущего порядка

Question

Я искал в Google (и, конечно, переполнение стека!) Способ сортировки списка целых чисел по значению, но также по дополнительному коэффициенту. Я ищу какой-то алгоритм для реализации, я полагаю. До сих пор у меня в Delphi 2007 есть массив, который сортирует значения от наибольшего к наименьшему, но теперь я бы хотел отсортировать значения, которые на X только больше, чем предыдущее число в списке.

Например, значения 5, 7, 25, 15 в настоящее время отсортированы по 25, 15, 7, 5. Порядок, который я сейчас пытаюсь получить, со значением X, равным 5, равен 25, 15, 5, 7. Как видите, 5 и 7 не поменялись местами, потому что между ними нет разницы больше 5 *.

Не уверен, что я объясняю это особенно хорошо, но это общая идея.

Еще одним примером будут значения 10, 40, 18, 20, 16, 28. Сортировать, они должны быть 40, 28, 18, 20, 16, 10. 18, 20 и 16 не переместились, потому что опять же, между каждым из чисел не более 5

Идея заключается в том, что элемент, связанный с номером (например, количество раз, когда что-то было заказано), не меняется постоянно из-за разницы только в 1 или 2. Например, если Список наиболее часто заказываемой бумаги отображается на веб-странице по частоте приобретения, тогда заказ определенного типа бумаги изменится только для пользователя, если он был заказан более чем в пять раз больше, чем следующий наиболее часто встречающийся.

Надеюсь, что это имеет смысл, и спасибо за ваше время!

Answer 1

По крайней мере, вам нужно использовать стабильную сортировку, то есть сортировку, которая сохраняет порядок эквивалентных значений.

Получив это, вы, вероятно, должны определить свое сравнение, как если бы abs(a - b)<5 равнялось, в противном случае выполните обычное сравнение. Это делает compare(a, b)==compare(b, a), что должно утверждать большинство хороших реализаций сортировки.

Если вы используете C ++, вы можете использовать std::stable_sort для этого.

Answer 2

Я думаю, что ваше требование приводит к действительно странным результатам. В конечном итоге вы можете создать порядок сортировки, в котором элементы будут отсортированы в неправильном направлении, и то, как они сортируются, зависит от того, как они изменяются.

Я думаю, вам нужно установить «классы» значений (использовать процентили?), А затем отсортировать газеты по алфавиту в каждом классе.

Например: едва заказано (90% бумаг заказано больше, чем этот), ниже медианы (50% газет заказано больше, чем эти), выше медианы, топ 10 упорядочено (отсортировано по количеству порядков Конечно).

Answer 3

Подумав об этом еще немного, я думаю, что пузырьковая сортировка - единственный тип сортировки, который будет работать. Это потому, что в пузырьковой сортировке число должно быть явно больше (или в этом случае на 5 больше), чем числа над ним, чтобы они могли поменяться местами. Это именно то, что вы просили.

С точки зрения высокого уровня, вот что, я думаю, вам понадобится:

1. Реализация пузырьковой сортировки, использующая пользовательскую функцию сравнения.

2. функция сравнения, которая возвращает значение равное, если разница меньше 5.

Объединение этих двух вещей должно оставить вас с тем, что вы хотите.

Answer 4

Есть две вещи, которые важны для этого:

1) Вам нужен устойчивый алгоритм сортировки (хотя он не должен быть пузырьковой сортировкой и, вероятно, не должен), то есть он сохраняет первоначальный порядок, если компаратор возвращает 0 (= равно). См. сравнение википедии алгоритмов сортировки для хорошего обзора.

2) Вам нужен собственный компаратор, который возвращает 0 именно в тех случаях, которые вы упомянули.

Answer 5

TList.Sort не будет работать, потому что он использует алгоритм быстрой сортировки, как прокомментировал mghie.

Bubble sort algoritham не такой быстрый, вот реализация, которую вы можете попробовать, на этот раз на паскале.

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;

Answer 6

Я думаю, что для этого нужно два прохода. На первом проходе идентифицируйте любые значения, которые подлежат сортировке, а на втором проходе фактически перемещайте только те, которые были идентифицированы таким образом. Во втором примере, используя массив Y / N с сортировкой Y, вы получите [Y, Y, N, N, N, Y], а затем, только отсортировав значения Y, N будут " игнорируется, не имеет права на сортировку "вы получите ваш результирующий список [40, 28, 18, 20, 16, 10]. Группа N (всегда будет группой, основанной на определении) должна сравниваться с величиной самой высокой в ​​ее группе.

Answer 7

Возможно, имеет смысл применить ваш принцип сортировки к почти отсортированному списку, но вам следует учитывать тот факт, что он нарушает основное предположение об общих алгоритмах сортировки: элементы, которые должны быть отсортированы, образуют общий порядок. Это означает, что оператор <ведет себя так же, как и для действительных чисел. Если вы нарушите это правило, вы можете получить странные эффекты, и библиотечные алгоритмы могут даже не завершиться (или даже аварийно завершить работу, я видел, как это происходит для std :: sort в C ++). </p>

Один из способов изменить вашу идею, чтобы сделать ее общим порядком, - это отсортировать по каждому числу, округленному до ближайшего кратного 5.

Answer 8

Попробуйте выполнить сортировку с помощью пользовательской функции сравнения, вы можете быстро попробовать это, заполнив TList числами и вызвав 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;