C# - Sortierung mehrerer String-Arrays mit Quicksort

Question

Sorry für den vagen Titel, aber ich werde versuchen und beschreiben, was mein Problem so gut wie ich kann unten.

Grundsätzlich habe ich 5 String-Arrays, die alle Daten für den gleichen Index in den anderen Arrays halten. Beispiel: Element 5 in Array 1 entspricht Element 5 in den Arrays 2, 3, 4 und 5.

Was ich getan habe, ist das Quicksort algorthim, um Array 1 in alphabetischer Reihenfolge zu sortieren. Das Problem besteht darin, dass beim Sortieren des Arrays die Elemente in den anderen Arrays nicht mehr übereinstimmen, da die anderen Arrays nicht sortiert wurden.

Was ich brauche, ist eine Möglichkeit, die gleichen Elemente in den anderen vier Arrays umzuschalten, wie es bei Array 1 der Fall war. Wenn beispielsweise Element 2 in Array 1 gegen Element 55 ausgetauscht wird, dann Element 2 im anderen 4 Arrays müssen in ihrem Array in das Element 55 und umgekehrt getauscht werden.

Das Endziel besteht darin, alle Daten in einem bestimmten Element über alle 5 Arrays hinweg anzuzeigen.

Im Folgenden werde ich die quicksort Algorithmus hinzugefügt haben, ich verwende und hinzugefügt 3 Beispiel Arrays, die Sortierung müssen:

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); 
     } 
    } 

Wenn Sie andere Informationen müssen nur fragen.

Answer 1

Sie haben diese drei Informationen zu sortieren. Versuchen Sie, eine Klasse zu erstellen, um sie zu halten. Es kann eine innere Klasse innerhalb einer Ihrer Programmklassen sein, wenn Sie möchten.

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

Dann machen Sie eine . Dann füllen Sie es mit Ihren Daten.

Sie müssen die IComparable interface (requiring your own CompareTo method) für Ihre Klasse implementieren, so dass es auf a sortieren kann, oder was auch immer Sie möchten sortiert.

Verwenden Sie dann die eingebaute Funktion List.Sort() oder Ihre eigene Quicksort-Methode.

Answer 2

ich denke, es würde mehr Sinn machen, wenn Sie zusammen alle zugehörigen Informationen gespeichert in einem Array, zum Beispiel:

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

Dann können Sie Ihre Array von jedem Schlüssel sortieren Sie mögen und andere Elemente an entsprechenden Positionen zu bewahren .

Answer 3

Sie könnten dies erreichen, indem Sie alle Ihre verwandten Strings in eine einzige Klasse einfügen, anstatt sie alle in separaten Arrays zu halten.

Zum Beispiel:

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); 
    } 
} 

Dann, wenn Sie, dass sortieren möchten, müssen Sie einen Weg zu verwenden, welche Eigenschaft oder Eigenschaften zu bestimmen, wann Elemente zu vergleichen. Es gibt mehrere Möglichkeiten, dies zu tun; Eine besteht darin, Ihren Typ zu implementieren IComparable<T>.

Allerdings gibt es einen weiteren flexibleren Ansatz. Sie können Ihrer Sortiermethode ein Objekt IComparer<T> zur Verfügung stellen, mit dem Elemente verglichen werden können.

Mit diesem können Sie das Mitglied einer Klasse auswählen, die Sie beim Vergleich verwenden möchten.

Hier ist ein vollständiges Beispiel:

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

Es ist besser, die drei in Beziehung stehenden Saiten zu einem einzigen Objekt zu setzen:

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

und dann eine Liste der Objekte sortieren:

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

oder, wenn es sich um ein Array handeln muss:

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

Außerdem müssen Sie Quicksort nicht selbst implementieren (es sei denn, das sind Hausaufgaben?). :)). Sie können einfach Array.Sort oder List<T>.Sort mit einem Lambda-Ausdruck verwenden, der Ihr Sortierkriterium angibt.

Sie müssen nicht einmal die IComparable<T> Schnittstelle implementieren, wenn Sie den obigen Code verwenden. Wenn die RelatedInformation-Klasse (oder -Struktur) jedoch an vielen Stellen verwendet wird, die etwas mit ihrer Reihenfolge zu tun haben, ist es ratsam, sie trotzdem zu implementieren. dann können Sie die Lambda-Ausdrücke Graben:

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(); 

---

Da jedoch explizit über die Situation drei-Array gefragt, hier ist eine Lösung, die unter dieser Einschränkung arbeiten. Anstatt eines der Arrays zu sortieren, besteht die Idee darin, eine Liste der Indizes zu sortieren. Ich werde LINQ für diese verwenden, weil es ziemlich succint ist und lesbar:

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(); 

Ziemlich kurz, nicht wahr? Natürlich können Sie beim Aufruf von OrderBy jedes andere Array angeben, nach dem sortiert werden soll.

bewusst sein, Sie aber, dass dieser Code eine Ausnahme ausgelöst wird, wenn eine der Arrays ist kürzer als die erste, und es wird still Elemente verwerfen, wenn eine der Arrays länger als der erste ist. Ein großer Vorteil der Objektlisten-Lösung ist, dass Sie sich darüber keine Gedanken machen müssen.

Als eine zusätzliche Information, die OrderBy von LINQ ist eine stabile Art; Das bedeutet, dass Elemente, bei denen array1 denselben String hat, in derselben Reihenfolge bleiben. Array.Sort und List<T>.Sort haben keine stabile Sortierung.

Sie können diese Methode auch verwenden, um nach mehreren Kriterien zu sortieren. Angenommen, Sie möchten nach den Strings in array1 sortieren, aber wenn array1 dieselbe Zeichenfolge für einige Elemente hat, möchten Sie, dass diese Elemente nach dem sortiert werden, was in array2 ist. Sie können dies tun mit ThenBy:

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