c# - Sorting Multiple String arrays with Quicksort

It’s better to put the three related strings into a single object:

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

and then sort a list of those objects:

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

or, if it needs to be an array:

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

Additionally, there is no need for you to implement Quicksort yourself (unless this is homework? :)). You can just use Array.Sort or List<T>.Sort with a lambda expression that specifies your sort criterion.

You don’t even need to implement the IComparable<T> interface if you use the above code. However, if the RelatedInformation class (or struct) is used in many places that have something to do with their ordering, it may be wise to implement it anyway; then you can ditch the lambdas:

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

However, since you explicitly asked about the three-array situation, here is a solution that will work under that constraint. Instead of sorting any one of the arrays, the idea is to sort a list of the indexes. I’m going to use LINQ for this because it’s pretty succint and readable:

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

Pretty short, huh? Of course, in the call to OrderBy, you can specify any other array to sort by.

Do be aware though that this code will throw an exception if any of the arrays is shorter than the first one, and it will silently discard items if any of the arrays is longer than the first one. One major benefit of the list-of-objects solution is that you do not need to worry about that.

As an added piece of information, the OrderBy from LINQ is a stable sort; this means that items where array1 has the same string stay in the same order. Array.Sort and List<T>.Sort do not have a stable sort.

You can even use this method to sort by multiple criteria; for example, let’s say you want to sort by the strings in array1, but whenever array1 has the same string for some items, you want those items to be sorted by whatever is in array2. You can do that using ThenBy:

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

You've got these three items of information to sort. Try creating a class to hold them. It can be an inner class inside one of your program classes if you want.

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

Then make a List<MyThing>. Then populate it with your data.

You'll need to implement the IComparable interface (requiring your own CompareTo method) for your class, so it knows to sort on a, or whatever you want sorted.

Then use the built in List.Sort() function or your own quicksort method.

I think it would make more sense if you stored all your related information together in one array, e.g.:

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

Then you can sort your array by any key you like and preserving other elements at corresponding positions.

You could approach this by putting all your related strings into a single class, rather than keeping them all in separate arrays.

For example:

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

Then when you want to sort that, you need a way to determine which property or properties to use when comparing elements. There are several ways to do this; one is to make your type implement IComparable<T>.

However there is another more flexible approach. You can supply to your sort method an IComparer<T> object that it can use to compare elements.

Using this, you can "pick out" the member of a class that you want to use when comparing.

Here's a full example:

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