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.

CodePudding user response：

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