How to Sort Array Elements in C# with a given order and not using library's sort function?

Question

I've been searching about an algorithm that sorts "strings" with a given order.

Input: [W, R, B, G, G, R, W, B] (obviously, just random)

Output: [R, R, W, W, B, B, G, G]

I want to do like a "Two-Pass Algorithm".

Something like:

using System;
using System.Collections.Generic;
using System.Drawing;

namespace ConsoleApp5
{
    class Program2
    {
        static void Main(string[] args)
        {
            List<Color> colors = new List<Color>() { Color.White, Color.Red, Color.Green, Color.Blue }; // Random Ordered Array
            int j = 0;
            int k = colors.Count;
            int i = 0;
            while (j < k)
            {
                if (colors[j] == Color.White)
                {
                    j += 1;
                }
                else if (colors[j] == Color.Blue)
                {
                    swap(colors[j], colors[--k]);
                    Console.WriteLine(colors[j]);
                }
                else
                {
                    swap(colors[j++], colors[i++]);
                }
                i += 1;
            }

            void swap(Color a, Color b)
            {
                Color temp = a;
                a = b;
                b = temp;

            }
        }
    }
}

EDIT 1

I was able to print "RRWWGG" from this code:

using System;
using System.Collections.Generic;
using System.Drawing;

namespace ConsoleApp5
{
    class Program2
    {
        static void Main(string[] args)
        {
            List<String> colors = new List<String>() { "W", "R", "G", "W", "R", "G"}; // Random Ordered Array
            int start = 0;
            int end = colors.Count - 1;
            int current = 0;

            while (current <= end && start < end)
            {
                if(colors[current] == "R")
                {
                    swap(colors, current, start);
                    start++;
                    current++;
                }
                else if (colors[current] == "G")
                {
                    swap(colors, current, end);
                    end--;
                }
                else
                {
                    current++;
                }

            }
            for(int i = 0; i < colors.Count; i++)
            {
                Console.WriteLine(i+colors[i]);
            }
        }
        static void swap(List<String> colors, int a, int b)
        {
            String temp = colors[a];
            colors[a] = colors[b];
            colors[b] = temp;

        }
    }
}

Now, I want to do the same algorithm to place W and B in the middle, given that R must be placed on the left and G on the right.

I added B to the array with this code:

using System;
using System.Collections.Generic;
using System.Drawing;

namespace ConsoleApp5
{
    class Program2
    {
        static void Main(string[] args)
        {
            List<String> colors = new List<String>() { "W", "R", "G", "W", "R", "G", "B", "B" }; // Random Ordered Array
            int start = 0;
            int end = colors.Count - 1;
            int current = 0;

            while (current <= end && start < end)
            {
                if(colors[current] == "R")
                {
                    swap(colors, current, start);
                    start++;
                    current++;
                }
                else if (colors[current] == "G")
                {
                    swap(colors, current, end);
                    end--;
                }
                else
                {
                    current++;
                }

            }
            for(int i = 0; i < colors.Count; i++)
            {
                Console.WriteLine(i+colors[i]);
            }
        }
        static void swap(List<String> colors, int a, int b)
        {
            String temp = colors[a];
            colors[a] = colors[b];
            colors[b] = temp;

        }
    }
}

The result of the above code was: [R, R, B, W, W, B, G, G].

I want the result to be [R, R, W, W, B, B, G, G] without "library's sort function" and only with this kind of algorithm.

Do you _have_ to use ArrayList? It hasn't been used by modern C# code in years. — David L, Aug 24 '22 at 17:46
No, it is not required to use ArrayList. I just used it because that's the first I remembered when I'm about to make array/s in C#. — Misanthropia, Aug 24 '22 at 17:48
Generally, to sort a list of `Color` objects you would write a custom [`Comparer`](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.comparer-1?view=net-6.0). See e.g. [Writing a custom comparer for a core class in C#](https://stackoverflow.com/q/14165468). But exactly what comparison logic do you have in mind for `Color` that would result in Red < White < Blue < Green? Is this simply some hardcoded order, or do you have some general rule in mind that would apply if e.g. you added `Color.Yellow`? — dbc, Aug 24 '22 at 17:51
You should always prefer `List` over `ArrayList`, see [c# When should I use List and when should I use arraylist?](https://stackoverflow.com/q/725459). — dbc, Aug 24 '22 at 17:53
Thanks for the suggestion, @dbc . Anyway, about your question, I have no rule in mind or logic to apply; I just want to sort the array values in the given order. Nothing would happen if I added `Color.Yellow` since all I wanted was to sort the given array elements accordingly to what order I wanted them to be sorted. — Misanthropia, Aug 24 '22 at 18:00

Dmitry Bychenko · Accepted Answer · 2022-08-26T15:21:04.373

You can try mapping colors to int and then compare these ints, e.g.

// Map : each Color has its index within order array
// if you want to add Yellow, put it to the right place
Color[] order = new Color[] {
  Color.White, Color.Red, Color.Blue, Color.Green
};

then having

List<Color> colors = new List<Color>() {
  Color.White, Color.Green, Color.Blue, Color.Red
}

you can sort it as follows:

colors.Sort((a, b) => order.IndexOf(a).CompareTo(order.IndexOf(b)));

Edit: Same idea for custom sort algorithm (selection sort):

for (int i = 0; i < colors.Count - 1; ++i) {
  int minIndex = i;
  int min = order.IndexOf(colors[minIndex]); 
  
  for (int j = i + 1; j < colors.Count; ++j) {
    int current = order.IndexOf(colors[j]);

    if (current < min) {
      min = current;
      minIndex = j;
    } 
  }

  (colors[i], colors[minIndex]) = (colors[minIndex], colors[i]);
}

Edit 2: The very same idea for Quicksort:

private static void QuickSort<T>(List<T> items, 
                                 int leftIndex, int rightIndex, List<T> order) {
  var left = leftIndex;
  var right = rightIndex;
  var pivot = items[leftIndex];
     
  while (left <= right) {
    while (order.IndexOf(items[left]) < order.IndexOf(pivot)) 
      left += 1;
        
    while (order.IndexOf(items[right]) > order.IndexOf(pivot)) 
      right -= 1;

    if (left <= right) {
      (items[left], items[right]) = (items[right], items[left]);

      ++left;
      --right;
    }
  }

  if (leftIndex < right)
    QuickSort(items, leftIndex, right, order);

  if (left < rightIndex)
    QuickSort(items, left, rightIndex, order);
}

private static void QuickSort<T>(List<T> items, List<T> order) {
  if (items.Count > 1)
    QuickSort(items, 0, items.Count - 1, order);
}

Usage:

// Desired order
var order = new List<string>() { "R", "W", "B", "G"};

// List to be sorted
List<String> colors = new List<String>() { 
  "W", "R", "G", "W", "R", "G", "B", "B" 
}; 

QuickSort(colors, order);

Thank you sir. Anyway, is this answer similar to this one? https://pastebin.com/6sdJamD6 — Misanthropia, Aug 24 '22 at 18:49
@Misanthropia: I doubt if we should reinvent wheel and implement our own sorting algorithm when we can just call `Sort`; another issue is that when we want to add / remove colors (say, we wamt to add `Yellow`) all we should do is to place `Color`s in the required order; in your solution we have to rewrite the algorithm. — Dmitry Bychenko, Aug 24 '22 at 19:09
can we rewrite this solution into like "Selection Sort" Algorithm? — Misanthropia, Aug 25 '22 at 08:47
hmm. I don't know why I think that this solution is not the solution I need sir. But it works. can we rewrite this into like this https://cheonhyangzhang.gitbooks.io/leetcode-solutions/content/75_sort_colors__medium.html but the difference is i have 4 colors or 4 array elements. — Misanthropia, Aug 25 '22 at 10:34
sir, if you're there. can we rewrite this into quicksort + partition? see my edit sir, thanks! — Misanthropia, Aug 26 '22 at 11:44
@Misanthropia: you can exploit the same idea (mapping) again and again, this time for quick sort: see my Edit 2 — Dmitry Bychenko, Aug 26 '22 at 15:23

How to Sort Array Elements in C# with a given order and not using library's sort function?

1 Answers1