TheDeveloperBlog.com


C# Sorted Array Examples

Sorted arrays. An array may be already sorted. We can avoid sorting it again in this case. This is useful when accepting input that needs to be presorted, or for certain algorithms. We apply this to int and string arrays.

Int Array
Example arrays and IsSorted result

Array example: 1, 4, 6, 8
IsSorted:      True

Array example: 5, 2, 7, 6
IsSorted:      False

Array example: cat, man, zebra
IsSorted:      True

Array example: soda, pop, coke, tonic
IsSorted:      False


Example. When determining if an array is already sorted, you could call Sort on a copy of the array and then compare both arrays for equality. But this is much slower than simply iterating through the array and using CompareTo on each element.

Here: We loop over arrays, comparing adjacent elements for the correct ordering. This is a faster approach.

C# program that tests sorted arrays

using System;

class Program
{
    static void Main()
    {
	int[] sortedInts = new int[]
	{
	    1,
	    4,
	    6,
	    8
	};
	int[] unsortedInts = new int[]
	{
	    5,
	    2,
	    7,
	    6
	};
	int[] reversedInts = new int[]
	{
	    9,
	    8,
	    5,
	    1
	};
	string[] sortedStrings = new string[]
	{
	    "cat",
	    "man",
	    "zebra"
	};
	string[] unsortedStrings = new string[]
	{
	    "soda",
	    "pop",
	    "coke",
	    "tonic"
	};
	string[] reversedStrings = new string[]
	{
	    "zebra",
	    "partridge",
	    "apple"
	};
	Console.WriteLine(SortTools.IsSorted(sortedInts));                // True
	Console.WriteLine(SortTools.IsSortedDescending(sortedInts));      // False
	Console.WriteLine(SortTools.IsSorted(unsortedInts));              // False
	Console.WriteLine(SortTools.IsSortedDescending(unsortedInts));    // False
	Console.WriteLine(SortTools.IsSorted(reversedInts));              // False
	Console.WriteLine(SortTools.IsSortedDescending(reversedInts));    // True
	Console.WriteLine(SortTools.IsSorted(sortedStrings));             // True
	Console.WriteLine(SortTools.IsSortedDescending(sortedStrings));   // False
	Console.WriteLine(SortTools.IsSorted(unsortedStrings));           // False
	Console.WriteLine(SortTools.IsSortedDescending(unsortedStrings)); // False
	Console.WriteLine(SortTools.IsSorted(reversedStrings));           // False
	Console.WriteLine(SortTools.IsSortedDescending(reversedStrings)); // True
    }
}

/// <summary>
/// Methods for determining if arrays are sorted.
/// </summary>
public static class SortTools
{
    /// <summary>
    /// Determines if int array is sorted from 0 -> Max
    /// </summary>
    public static bool IsSorted(int[] arr)
    {
	for (int i = 1; i < arr.Length; i++)
	{
	    if (arr[i - 1] > arr[i])
	    {
		return false;
	    }
	}
	return true;
    }

    /// <summary>
    /// Determines if string array is sorted from A -> Z
    /// </summary>
    public static bool IsSorted(string[] arr)
    {
	for (int i = 1; i < arr.Length; i++)
	{
	    if (arr[i - 1].CompareTo(arr[i]) > 0) // If previous is bigger, return false
	    {
		return false;
	    }
	}
	return true;
    }

    /// <summary>
    /// Determines if int array is sorted from Max -> 0
    /// </summary>
    public static bool IsSortedDescending(int[] arr)
    {
	for (int i = arr.Length - 2; i >= 0; i--)
	{
	    if (arr[i] < arr[i + 1])
	    {
		return false;
	    }
	}
	return true;
    }

    /// <summary>
    /// Determines if string array is sorted from Z -> A
    /// </summary>
    public static bool IsSortedDescending(string[] arr)
    {
	for (int i = arr.Length - 2; i >= 0; i--)
	{
	    if (arr[i].CompareTo(arr[i + 1]) < 0) // If previous is smaller, return false
	    {
		return false;
	    }
	}
	return true;
    }
}

Output

True
False
False
False
False
True
True
False
False
False
False
True

The Main method tests the SortTools static class for accuracy. It declares six arrays, three for ints and three for strings. Each trio contains one ascending array, one unsorted array, and one descending array.

Arrays

The SortTools class is a public static class that you can put in an external file, called "SortTools.cs". You can access the member methods in this class with dot notation, as shown in Main.

Static Class

IsSorted int: IsSorted checks that the int array specified is sorted in ascending order.

IsSorted string: This method works the same as its int equivalent. It calls CompareTo on strings.

IsSortedDescending int: This method checks that the array is sorted from high to low, descending order.

IsSortedDescending string: This method scans the array to see if it is sorted from "biggest" to "smallest", descending order.


Summary. We saw methods for determining if arrays are already sorted. They are fast, with optimal time complexity. No extra memory is allocated. You could adapt the approach in these methods to char or object arrays.