0

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.

Improve this question
5
  • 2
    Do you have to use ArrayList? It hasn't been used by modern C# code in years. Commented Aug 24, 2022 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#. Commented Aug 24, 2022 at 17:48
  • Generally, to sort a list of Color objects you would write a custom Comparer<Color>. See e.g. Writing a custom comparer for a core class in C#. 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? Commented Aug 24, 2022 at 17:51
  • 1
    You should always prefer List<T> over ArrayList, see c# When should I use List and when should I use arraylist?. Commented Aug 24, 2022 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. Commented Aug 24, 2022 at 18:00

1 Answer 1

Reset to default
3

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);
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Thank you sir. Anyway, is this answer similar to this one? pastebin.com/6sdJamD6
@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 Colors in the required order; in your solution we have to rewrite the algorithm.
can we rewrite this solution into like "Selection Sort" Algorithm?
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 cheonhyangzhang.gitbooks.io/leetcode-solutions/content/… but the difference is i have 4 colors or 4 array elements.
@Misanthropia: you can exploit the same idea (mapping) again and again, this time for quick sort: see my Edit 2
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.