リストを並べ替えるときに同じ値の項目の相対的な順序を保持する

Question

重複する値の項目が含まれている可能性のある変更リストをソートする必要があるとします。たとえば、[99,99,90,89]でしたが、4番目のアイテムの値が91に変更されました。[99、99、91、90]にしたいと思っていますが、最初の2番目の項目を変更します。

私はSort()メソッドを使用しましたが、上の例の最初と2番目の項目の順序が変更されるようです。それを防止し、同じ値を持つアイテムの相対的な順序を保持する方法はありますか？

これがなぜ必要なのか考えることができない場合は、進捗リストを想定してください。リストの項目は毎秒更新されます。アイテムが進捗状況でソートされている場合は、同じ進行状況のアイテムが相対的な位置を変更し続けるようにします。

これをテストするためのサンプルコードを作成しました。目標はDebug.WriteLine("No change");に達するでしょう。

public void Start() 
{ 
    var list = new List<Item>(); 
    var ran = new Random(); 
    const int nItems = 30; 
    for (int i = 0; i < nItems; i++) 
    { 
     var name = "Item " + (list.Count + 1); 
     var item = new Item(name, ran.Next(0, 10)); 
     list.Add(item); 
    } 

    var sorter = new ItemComparer(); 
    var snapshot = new Item[nItems]; 
    for (int nSort = 0; nSort < 10000; nSort++) 
    { 
     list.CopyTo(snapshot); 
     list.Sort(sorter); 

     if (nSort == 0) 
     { 
      //Sorted for the first time, so the snapshot is invalid. 
      continue; 
     } 

     for (int pos = 0; pos < nItems; pos++) 
     { 
      if (snapshot[pos] != list[pos]) 
      { 
       Debug.WriteLine($"Order changed at position {pos} after {nSort} sorts."); 
       PrintChangedLocation(list, snapshot, pos); 
       return; 
      } 
     } 
    } 

    Debug.WriteLine("No change"); 
} 

private static void PrintChangedLocation(List<Item> list, Item[] snapshot, int changedLocation) 
{ 
    Debug.WriteLine($"Before\t\t\tAfter"); 
    for (int pos = 0; pos < list.Count; pos++) 
    { 
     var before = snapshot[pos]; 
     var after = list[pos]; 
     Debug.Write($"{before.Name} = {before.Progress}"); 
     Debug.Write($"\t\t{after.Name} = {after.Progress}"); 

     if (pos == changedLocation) 
     { 
      Debug.Write(" <----"); 
     } 
     Debug.WriteLine(""); 
    } 
} 

class Item 
{ 
    public string Name; 
    public float Progress; 

    public Item(string name, float progress) 
    { 
     Name = name; 
     Progress = progress; 
    } 
} 

class ItemComparer : IComparer<Item> 
{ 
    int Direction = -1; 

    public int Compare(Item x, Item y) 
    { 
     return Direction * (int)(x.Progress - y.Progress); 
    }  
} 

出力例：

Order changed at position 12 after 1 sorts. 
Before   After 
Item 7 = 9  Item 7 = 9 
Item 24 = 9  Item 24 = 9 
Item 30 = 8  Item 30 = 8 
Item 4 = 8  Item 4 = 8 
Item 19 = 8  Item 19 = 8 
Item 27 = 7  Item 27 = 7 
Item 5 = 7  Item 5 = 7 
Item 25 = 7  Item 25 = 7 
Item 20 = 7  Item 20 = 7 
Item 26 = 6  Item 26 = 6 
Item 14 = 6  Item 14 = 6 
Item 1 = 6  Item 1 = 6 
Item 28 = 5  Item 2 = 5 <---- 
Item 2 = 5  Item 12 = 5 
Item 12 = 5  Item 28 = 5 
Item 11 = 4  Item 11 = 4 
Item 6 = 4  Item 6 = 4 
Item 13 = 3  Item 13 = 3 
Item 3 = 3  Item 3 = 3 
Item 21 = 3  Item 21 = 3 
Item 10 = 3  Item 10 = 3 
Item 18 = 3  Item 18 = 3 
Item 22 = 2  Item 22 = 2 
Item 29 = 2  Item 29 = 2 
Item 23 = 1  Item 23 = 1 
Item 8 = 1  Item 8 = 1 
Item 17 = 1  Item 17 = 1 
Item 16 = 0  Item 9 = 0 
Item 9 = 0  Item 16 = 0 
Item 15 = 0  Item 15 = 0 

Answer 1

を検討するための一つのオプションが変更されます：

list.Sort(sorter); 

をする：

list = list 
    .Select((item, index) => new { item, index}) 
    .OrderBy(z => z.item, sorter) 
    .ThenBy(z => z.index) 
    .Select(z => z.item) 
    .ToList(); 

これは、あなたは、あなたの比較演算によってソートできます次にの位置はListになり、相対的な順序が維持されます。