C# - Сортировка нескольких массивов String с помощью Quicksort

Question

Извините за неопределенное название, но я постараюсь описать, что моя проблема, насколько я могу ниже.

В основном у меня есть 5 строковых массивов, которые содержат данные, относящиеся к одному и тому же индексу в других массивах. Например, элемент 5 в массиве 1 соответствует элементу 5 в массивах 2, 3, 4 и 5.

Что я сделал, используется Quicksort algorthim для сортировки массива 1 в алфавитном порядке. Проблема в том, что когда массив сортируется, больше не выполняются элементы в других массивах, поскольку другие массивы не отсортированы.

Что мне нужно, так это обменять те же элементы вокруг других 4-х массивов, как и до массива 1. Например, если элемент 2 в массиве 1 заменен на элемент 55, тогда элемент 2 в другом 4 массива должны быть заменены на элемент 55 в их массиве и наоборот.

Конечная цель - отобразить все данные в определенном элементе по всем 5 массивам.

Ниже я добавил алгоритм QuickSort я использую и добавил 3 примера массивов, которые требуют сортировки:

string[] array1 = {"z","y","x","a"}; 
    string[] array2 = {"26","25","24","1"}; 
    string[] array3 = { "black","yellow","white","red" }; 


    // The first 2 arrays should clarify my point further. 

    // I use Quicksort to sort array 1 


    public static void QuicksortSTRING(IComparable[] elements, int left, int right) 
    {         
     int i = left, j = right; 
     IComparable pivot = elements[(left + right)/2]; 

     while (i <= j) 
      { 
      while (elements[i].CompareTo(pivot) < 0) 
      { 
       i++; 
      } 

      while (elements[j].CompareTo(pivot) > 0) 
      { 
       j--; 
      } 

      if (i <= j) 
      { 
       // Swap 
       IComparable tmp = elements[i]; 
       elements[i] = elements[j]; 
       elements[j] = tmp; 

       i++; 
       j--; 
      } 
     } 

     // Recursive calls 

     if (left < j) 
     { 
      QuicksortSTRING(elements, left, j); 
     } 

     if (i < right) 
     {  
      QuicksortSTRING(elements, i, right); 
     } 
    } 

Если вам нужна любая другая информация просто спросить.

Answer 1

У вас есть эти три элемента информации для сортировки. Попробуйте создать класс для их хранения. Это может быть внутренний класс внутри одного из ваших классов программ, если вы хотите.

struct MyThing :IComparable { 
     char a; 
     int b; 
     string c; 
    } 

Затем сделайте List<MyThing>. Затем заполните его своими данными.

Для вашего класса вам необходимо реализовать IComparable interface (requiring your own CompareTo method), поэтому он знает, что нужно сортировать по a или независимо от того, что вы хотите отсортировать.

Затем используйте встроенную функцию List.Sort() или свой собственный метод быстрой сортировки.

Answer 2

Я думаю, было бы больше смысла, если вы храните всю вашу соответствующую информацию вместе в один массиве, например:

var array = new[] { Tuple.Create("z", "26", "black"), 
        Tuple.Create("y", "25", "yellow"), 
        Tuple.Create("x", "24", "white"), 
        Tuple.Create("a", "1", "red") }; 

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

Answer 3

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

Например:

public class Demo 
{ 
    public string Key; 
    public string S1; 
    public string S2; 

    public override string ToString() 
    { 
     return string.Format("Key: {0}, S1: {1}, S2: {2}", Key, S1, S2); 
    } 
} 

Затем, когда вы хотите отсортировать, что вам нужен способ, чтобы определить, какое свойство или свойства для использования при сравнении элементов. Есть несколько способов сделать это; один должен сделать ваш тип реализации IComparable<T>.

Однако есть еще один более гибкий подход. Вы можете предоставить вашему методу сортировки объект IComparer<T>, который он может использовать для сравнения элементов.

Используя это, вы можете «выбрать» элемент класса, который вы хотите использовать при сравнении.

Вот полный пример:

using System; 
using System.Collections.Generic; 

namespace Demo 
{ 
    public class Demo 
    { 
     public string Key; 
     public string S1; 
     public string S2; 

     public override string ToString() 
     { 
      return string.Format("Key: {0}, S1: {1}, S2: {2}", Key, S1, S2); 
     } 
    } 

    static class Program 
    { 
     static void Main() 
     { 
      var list = new List<Demo> 
      { 
       new Demo {Key = "Z", S1 = "Z1", S2 = "Z2"}, 
       new Demo {Key = "Y", S1 = "Y1", S2 = "Y2"}, 
       new Demo {Key = "X", S1 = "X1", S2 = "X2"}, 
       new Demo {Key = "W", S1 = "W1", S2 = "W2"}, 
       new Demo {Key = "V", S1 = "V1", S2 = "V2"} 
      }; 

      // Rather than write your own IComparer<Demo> implementation, you can 
      // leverage a built-in .Net implementation by using 
      // Comparer<Demo>.Create() as follows: 

      var keyComparer = Comparer<Demo>.Create((x, y) => string.Compare(x.Key, y.Key, StringComparison.Ordinal)); 

      QuicksortSTRING(list, 0, list.Count-1, keyComparer); 

      Console.WriteLine(string.Join("\n", list)); 
     } 

     public static void QuicksortSTRING<T>(IList<T> elements, int left, int right, IComparer<T> comparer) 
     { 
      int i = left, j = right; 
      var pivot = elements[(left + right)/2]; 

      while (i <= j) 
      { 
       while (comparer.Compare(elements[i], pivot) < 0) 
       { 
        i++; 
       } 

       while (comparer.Compare(elements[j], pivot) > 0) 
       { 
        j--; 
       } 

       if (i <= j) 
       { 
        // Swap 
        T tmp = elements[i]; 
        elements[i] = elements[j]; 
        elements[j] = tmp; 

        i++; 
        j--; 
       } 
      } 

      // Recursive calls 

      if (left < j) 
      { 
       QuicksortSTRING(elements, left, j, comparer); 
      } 

      if (i < right) 
      { 
       QuicksortSTRING(elements, i, right, comparer); 
      } 
     } 
    } 
} 

Answer 4

Лучше поставить три связанные строки в единый объект:

sealed class RelatedInformation  // or struct, you decide 
{ 
    public string First; 
    public string Second; 
    public string Third; 
} 

, а затем отсортировать список этих объектов:

var myList = new List<RelatedInformation>(); 
// insert code that populates the list here 
myList.Sort((a, b) => a.First.CompareTo(b.First)); 

или, если это должен быть массив:

var myArray = /* obtain the RelatedInformation[] here */; 
Array.Sort(myList, (a, b) => a.First.CompareTo(b.First)); 

Кроме того, вам не нужно самостоятельно реализовывать Quicksort (если это не домашняя работа? :)). Вы можете просто использовать Array.Sort или List<T>.Sort с выражением лямбда, которое определяет ваш критерий сортировки.

Если вы используете приведенный выше код, вам даже не нужно реализовывать интерфейс IComparable<T>. Однако, если класс (или структура) RelatedInformation используется во многих местах, которые имеют какое-то отношение к их упорядочению, может быть разумным его реализовать; то вы можете угробить лямбды:

sealed class RelatedInformation : IComparable<RelatedInformation> 
{ 
    public string First; 
    public string Second; 
    public string Third; 

    public int CompareTo(RelatedInformation other) 
    { 
     return First.CompareTo(other.First); 
    } 
} 

// ... 

var myList = new List<RelatedInformation>(); 
// insert code that populates the list 
myList.Sort(); 

---

Однако, поскольку вы явно просил о ситуации в три-массива, здесь есть решение, которое будет работать под этим ограничением. Вместо сортировки любого из массивов идея состоит в сортировке списка индексов. Я собираюсь использовать LINQ для этого, потому что это довольно succint и читаем:

var sortedIndexes = Enumerable.Range(0, array1.Length) 
         .OrderBy(i => array1[i]) 
         .ToArray(); 

var sortedArray1 = sortedIndexes.Select(i => array1[i]).ToArray(); 
var sortedArray2 = sortedIndexes.Select(i => array2[i]).ToArray(); 
var sortedArray3 = sortedIndexes.Select(i => array3[i]).ToArray(); 

Довольно короткий, да? Конечно, при вызове OrderBy вы можете указать любой другой массив для сортировки.

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

В качестве дополнительной информации, OrderBy от LINQ является устойчивым сорт; это означает, что пункты, где array1 имеют одну и ту же строку, остаются в том же порядке. Array.Sort и List<T>.Sort не имеют стабильной сортировки.

Вы также можете использовать этот метод для сортировки по нескольким критериям; например, вы хотите сортировать по строкам в array1, но всякий раз, когда array1 имеет ту же строку для некоторых элементов, вы хотите, чтобы эти элементы были отсортированы по-любому в array2. Вы можете это сделать, используя ThenBy:

var sortedIndexes = Enumerable.Range(0, array1.Length) 
         .OrderBy(i => array1[i]) 
         .ThenBy(i => array2[i]) 
         .ToArray();