Sort the array of 0s, 1s, and 2s in c#

Programming C#
1

To sort an array containing only 0s, 1s, and 2s in C#, you can use the Dutch National Flag algorithm, which is an efficient way to sort this type of array in a single pass with a time complexity of O(n) and a space complexity of O(1). This method involves maintaining three pointers: one for 0s, one for 1s, and one for the current element being examined.

Here’s how you can implement it:

C# Code

using System;

class Program
{
    static void SortArray(int[] nums)
    {
        int low = 0; // Pointer for the next position of 0
        int mid = 0; // Pointer for the current element
        int high = nums.Length - 1; // Pointer for the next position of 2

        while (mid <= high)
        {
            if (nums[mid] == 0)
            {
                // Swap nums[low] and nums[mid], increment both low and mid
                Swap(nums, low, mid);
                low++;
                mid++;
            }
            else if (nums[mid] == 1)
            {
                // If the current element is 1, just move to the next element
                mid++;
            }
            else
            {
                // Swap nums[mid] and nums[high], decrement high
                Swap(nums, mid, high);
                high--;
            }
        }
    }

    static void Swap(int[] nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    static void Main(string[] args)
    {
        int[] nums = { 2, 0, 1, 2, 0, 1, 1, 0 };
        SortArray(nums);
        
        Console.WriteLine(string.Join(", ", nums));
    }
}

Explanation

  1. Initialization: Three pointers (low, mid, and high) are initialized.

    • low starts at the beginning of the array and tracks where the next 0 should go.
    • mid tracks the current element being examined.
    • high starts at the end of the array and tracks where the next 2 should go.

  2. Loop through the array: The loop continues until mid exceeds high.

    • If the current element (nums[mid]) is 0:
      • Swap it with the element at low.
      • Increment both low and mid pointers.
    • If the current element is 1:
      • Just move mid forward since 1s are already in the correct position.
    • If the current element is 2:
      • Swap it with the element at high.
      • Decrement high, but do not increment mid (since we need to examine the swapped value).

  3. Final Output: After the loop, the array will be sorted with all 0s at the beginning, followed by 1s, and then 2s at the end.

Benefits

  • In-Place Sorting: This algorithm does not require additional storage for sorting, making it memory efficient.
  • Single Pass: It only goes through the array once, which is optimal for this problem type.

This approach efficiently sorts the array of 0s, 1s, and 2s while maintaining clarity and simplicity in the implementation.

1 Like