# Stable custom alphabetical order using List<T>.Sort

## Background

This is a problem from a programming contest.

The Sharonians of planet Sharon, at the far end of our galaxy, have discovered various samples of English text from our electronic transmissions, but they did not find the order of our alphabet. Being a very organized and orderly species, they want to have a way of ordering words, even in the strange symbols of English. Hence they must determine their own order.

For instance, if they agree on the alphabetical order: UVWXYZNOPQRSTHIJKLMABCDEFG

Then the following words would be in sorted order based on the above alphabet order:

WHATEVER
ZONE
HOW
HOWEVER
HILL
ANY
ANTLER
COW


The input format is:

<N - number of words> <alphabet order>
<0>
..
<N>


## What I Did

I intended to use List<T>.Sort and use a custom Comparator so I don't have to implement a sorting algorithm from scratch. However, the alphabet input and the order is case insensitive and since List<T>.Sort uses an unstable QuickSort, words like "go" and "Go" would be swapped.

My workaround is so dirty but it works by making a copy of the word list to serve as a look-up to preserve the order of equal words.

## The Code As Is

using System;
using System.Collections.Generic;

class Program
{
static void Main(string[] args)
{
List<string> words = new List<string>();
List<string> wordsCopy = new List<string>();

//assume correct input
int numOfWords = int.Parse(firstLine.Split(" ".ToCharArray())[0]);
string alphabet = firstLine.Split(" ".ToCharArray())[1].ToUpper();

for (int i = 1; i <= numOfWords; i++)
{
}

Console.WriteLine();

//Quicksort is unstable (meaning "equal" elements will still be swapped, e.g. "go" and "Go")
words.Sort(delegate(String x, String y)
{
int max = (x.Length > y.Length) ? y.Length : x.Length;

if (x.ToUpper().Equals(y.ToUpper()))
{
//dirty work-around to stablize the sort
return wordsCopy.IndexOf(x) < wordsCopy.IndexOf(y) ? -1 : 1;
}

for (int i = 0; i < max; i++)
{
int indexX = alphabet.IndexOf(x[i].ToString(), StringComparison.InvariantCultureIgnoreCase);
int indexY = alphabet.IndexOf(y[i].ToString(), StringComparison.InvariantCultureIgnoreCase);

if (indexX > indexY)
{
return 1;
}
else if (indexX < indexY)
{
return -1;
}
}

return 0;
});

Console.Write(String.Join("\n", words));
}
}


This code was good enough to win, but what could I have done better?

-
Is stability actual requirement of the problem? I don't see it in the (partial?) problem statement you gave us. –  svick May 7 at 10:24
@svick I think I implied it since the code's output should match each sample output. Consider the word list: "good, Good, horse..". The correct output should be as is. However, if the sorting is unstable, the output would be: "Good, good, horse...". –  helix May 7 at 10:29

First of all, I would take advantage of the fact that the other commonly used implementation of sorting in .Net is stable: the OrderBy() extension method from LINQ. Though it requires IComparer interface for custom sorting, it won't accept the Comparer delegate you're using.

If you wanted to keep using List.Sort(), then I think your implementation is mostly okay, with the following caveats:

• It has the potential to balloon the time complexity of the sort from $\mathcal{O}(n \log n)$ to $\mathcal{O}(n^2 \log n)$. This is becuse every call to your comparison delegate can take $\mathcal{O}(n)$ time, due to the calls to IndexOf().
• It doesn't work correctly if some words in the list repeat themselves. For example “Good, good, Good” would be sorted as “Good, Good, good”.

Neither of these might matter to you, but I think it's good to be aware of them.

Your comparison doesn't work correctly for pairs where one word is the start of another (like “HOW” and “HOWEVER” from the sample list), it returns 0 for those, even though the words are not the same.

All your code is inside a single method. That's usually frowned upon, but I think it's probably okay when you have this little code. The same goes for separation of concerns.

int numOfWords = int.Parse(firstLine.Split(" ".ToCharArray())[0]);
string alphabet = firstLine.Split(" ".ToCharArray())[1].ToUpper();


I would avoid the repetition of firstLine.Split(" ".ToCharArray()) by extracting its result to a separate variable.

Also, you don't actually need that ToCharArray(), since Split() is a params method.

string[] firstLineParts = firstLine.Split(' ');

int numOfWords = int.Parse(firstLineParts[0]);
string alphabet = firstLineParts[1].ToUpper();


wordsCopy.Add(words[words.Count - 1]);


I think creating wordsCopy would be simpler if you used the constructor of List that can copy existing collection:

List<string> wordsCopy = new List<string>(words);


words.Sort(delegate(String x, String y)


You can use the lambda syntax here. That way, you don't have to (but can, if you want) specify the types of parameters:

words.Sort((x, y) =>


x.ToUpper().Equals(y.ToUpper())


ToUpper() is culture-specific, which can cause problems in some cultures (particularly Turkish).

But you probably don't need to care about that if you only ever expect to run this program on your computer.

-
In programming contests, the contestants are racing each other and a clock to solve the problems as quickly as possible, with solutions posted sometimes 5-10 minutes after the problem is shown. Your code style advice does apply to production code, but is wholly inappropriate for this one specific instance. –  insta May 7 at 13:52

By implementing anonymous types, you could add an index for the original list order, without having to lookup afterwards, and at the same time getting the index inside the alphabet.

All at once:

    var indexed = words.Select( (w,li) => new { word = w, ListIndex = li, Len = w.Length}).ToArray();
//at this point, each element in indexed containts word, ListIndex and string length.

//sorting
Array.Sort(indexed, (wi1, wi2) =>
{
int min = (wi1.Len < wi2.Len) ? wi1.Len : wi2.Len;

for (int i = 0; i < min; i++)
{
char c1 =char.ToUpper(wi1.word[i]), c2 = char.ToUpper(wi2.word[i]);
if (c1 != c2) //only bother going for the alphabet index if the chars differ
return alphabet.IndexOf(c1) - alphabet.IndexOf(c2);
}

if(wi1.Len == wi2.Len)
return wi1.ListIndex - wi2.ListIndex; //if equal, use original list index

return wi1.Len - wi2.Len; //prefer shortest first
});

//resetting the words list
words = indexed.Select(w => w.word).ToList();


What happens in the anonymous type, is that all original listindexes are stored beforehand, preventing having to lookup in each compare.

wordsCopy.IndexOf(x) inside the compare is replaced by setting ListIndex = li++

edit As you stated correctly I was sloppy enough to only sort on the first character in the first version. Besides the ListIndex Storage, this isn't too different from your own code.

One notable difference is that instead of always searching for the alphabet index, it is only searched once per comparison, when the characters do not match. e.g. for "HOWG" and "HOWU" only the indices for U and G are obtained. For "Cow" and "COW", no char differences are found and no alphabet indices are searched for. Their length is the same, so listindex is compared.

Another performance difference, the ToUpper isn't compared beforehand, preventing having to do an uppercase first, and ordinalcompare later on for non matching words, with that also preventing the ToString() call on char (x[i].ToString()) in the current implementation (which could be replaced by an indexof(char.ToUpper(x[i]) ) . For example, comparing "ARelativelyLongStringA" and "ARelativelyLongStringB", would do a ToUpper first, find no match, and do a case insensitve alphabet index for each char in "ARelativelyLongString" until the difference is found, having compared those chars twice.

-
Clarification: I'm not too familiar with lambda expressions so correct me if I'm wrong but to my understanding, AlphabetIndex only stores info on the first character of every word. So if the first character is equal, why should we switch to the default Comparator instead of looking at the 2nd character and so on? (e.g. "HOWU" and "HOWG" will be sorted alphabetically instead of custom-alphabetically) –  helix May 7 at 14:36
Oops, spoke to soon, will update the anwer –  Me.Name May 7 at 14:46
@helix, sorry for the misinterpretation and the delay, was focusing to much at the buffering within the anonymous type. Please see the updated answer. thanks –  Me.Name May 7 at 15:34
Side effects in LINQ lambdas (like your li++) should be avoided. And in this case, there is a better solution: use the overload of Select() that also gives you the index. –  svick May 7 at 16:43
True enough, altered it, thanks. Although don't think there would have been side effects without parallelism. –  Me.Name May 8 at 8:16