3

I have a string, simplified "12345" which is sorted. The string couild contain Digits (0-9) or letters (a-z). In case of a mixed use the natural sort order. I need a method to verify if this is true.

Attempt with linq technique:

string items1 = "2349"; //sorted
string items2 = "2476"; //not sorted, 6<>7

bool sorted1 = Enumerable.SequenceEqual(items1.OrderBy(x => x), items1); //true
bool sorted2 = Enumerable.SequenceEqual(items2.OrderBy(x => x), items2); //false

but there could be also a descending sort order.

Is there a better way then

string items3 = "4321";
bool sorted3 = Enumerable.SequenceEqual(items3.OrderBy(x => x), items3) || Enumerable.SequenceEqual(items3.OrderByDescending(x => x), items3);

to check if a string is sorted? Maybe some built in solution?

Tamir Vered
  • 10,187
  • 5
  • 45
  • 57
c0rd
  • 1,329
  • 1
  • 13
  • 20

6 Answers6

6

Your solution in fine and very readable. One problem with it is that it requires ordering the string which is O(n * log(n)), this can be solved by iterating the string without sorting it.

For example:

var firstDifs = items1.Zip(items1.Skip(1), (x, y) => y - x);

This Linq projects every 2 items in the first string to a number which indicates their difference, So if you have items1 = "1245" the output will be:

firstDifs: {1, 2, 1}

Now all you need to do is to validate that firstDifs is either ascending or descending:

bool firstSorted = firstDifs.All(x => x > 0) || firstDifs.All(x => x < 0); //true

Now:

  • Skip is O(1) since the amount of actions required to skip 1 cell is constant.
  • Zip is O(n).
  • All is O(n).

So the whole solution is O(n).

Note that it will be more efficient with a simple loop, also if the first All has returned false because the 3487th item changes its direction (for example: 1234567891), the second All will run for no reason with the Zip running twice as well (Until where All require) - since there are two iterations of All and Linq evaluates them lazily.

Tamir Vered
  • 10,187
  • 5
  • 45
  • 57
  • Are you sure about iterating multiple times? Isn't it so that ZIP only iterates through the really needed elements, so if I find at the third iteration of the ALL that the result is false, and thus the rest of ALL is not iterated, that the rest is also not zipped? – Harald Coppoolse Aug 25 '16 at 06:52
  • @HaraldDutch The zipping will be done twice since there are two iterations of `All` and `Linq` evaluates them lazily. – Tamir Vered Aug 25 '16 at 06:56
  • @TamirVered `All()` stops processing if one invalid character was found so ist up to **O(n)** right? – c0rd Aug 25 '16 at 07:08
  • @c0rd if you have any repeating characters, change to `x >= 0` and `x <= 0` – Slai Aug 25 '16 at 07:54
3

It requires a reducer. In C#, it's Enumerable.Aggregate. It's O(n) algorithm.

var query = "123abc".Aggregate(new { asceding = true, descending = true, prev = (char?)null }, 
(result, currentChar) =>
    new 
    { 
       asceding = result.prev == null || result.asceding && currentChar >= result.prev, 
       descending = result.prev == null || result.descending && currentChar <= result.prev, 
       prev = (char?)currentChar 
    }
);
Console.WriteLine(query.asceding || query.descending );
qxg
  • 6,955
  • 1
  • 28
  • 36
2

I once had to check something similar to your case but with huge data streams, so performance was important. I came up with this small extension class which performs very well:

public static bool IsOrdered<T>(this IEnumerable<T> enumerable) where T: IComparable<T>
{
    using (var enumerator = enumerable.GetEnumerator())
    {
        if (!enumerator.MoveNext())
            return true; //empty enumeration is ordered

        var left = enumerator.Current;
        int previousUnequalComparison = 0;

        while (enumerator.MoveNext())
        {
            var right = enumerator.Current;
            var currentComparison = left.CompareTo(right);

            if (currentComparison != 0)
            {
                if (previousUnequalComparison != 0
                    && currentComparison != previousUnequalComparison)
                    return false;

                previousUnequalComparison = currentComparison;
                left = right;
            }
        }
    }

    return true;
}

Using it is obviously very simple:

var items1 = "2349";
var items2 = "2476"; //not sorted, 6<>7
items1.IsOrdered(); //true
items2.IsOrdered(); //false
InBetween
  • 32,319
  • 3
  • 50
  • 90
  • 1
    This is indeed the right way. Much better than any of the "concise" pure LINQ attempts. DRY and the **usage** is much more concise and readable. – Ivan Stoev Aug 25 '16 at 09:05
1

You can do much better than the accepted answer by not having to compare all of the elements:

var s = "2349"; 
var r = Enumerable.Range(1, s.Length - 1);
//var isAscending = r.All(i => s[i - 1] <= s[i]);
//var isDescending = r.All(i => s[i - 1] >= s[i]);
var isOrdered = r.All(i => s[i - 1] <= s[i]) || r.All(i => s[i - 1] >= s[i]);
Slai
  • 22,144
  • 5
  • 45
  • 53
0
var items = "4321";
var sortedItems = items.OrderBy(i => i); // Process the order once only
var sorted = sortedItems.SequenceEqual(items) || sortedItems.SequenceEqual(items.Reverse()); // Reverse using yield return
Eric
  • 5,675
  • 16
  • 24
0

I would go for simple iteration over all elements:

string str = "whatever123";
Func<char, char, bool> pred;
bool? asc = str.TakeWhile((q, i) => i < str.Length - 1)
               .Select((q, i) => str[i] == str[i+1] ? (bool?)null : str[i] < str[i+1])
               .FirstOrDefault(q => q.HasValue);
if (!asc.HasValue)
    return true; //all chars are the same
if (asc.Value)
    pred = (c1, c2) => c1 <= c2;
else
    pred = (c1, c2) => c1 >= c2;

for (int i = 0; i < str.Length - 1; ++i)
{
    if (!pred(str[i], str[i + 1]))
        return false;
}
return true;
slawekwin
  • 6,270
  • 1
  • 44
  • 57