// Write a program that rearranges the elements in integer array of size N so that all

// negative elements go first, then all zeroes, then all positives. 

using System;

public class Program

{

    public static void Main()

    {

        // Test

        int[] a = {1, -3, 5, 7, -9, 0, 2, -4, 6, 8, 0};

        partitioning(a, 0);

        printArray(a);

    }

    public static void partitioning(int[] a, int mid)

    {

        int s = 0, m = 0, b = 0;

        // invariant: first s elements of array (a[0..s-1]) are smaller than mid and 

        //            next  m elements of array (a[s..s+m-1]) are equal mid and  

        //            last  b elements of array (a[a.Length - b .. a.Length - 1]) are equal or bigger than mid and

        //            s + m + b <= a.Length

        // limiter: s + m + b increases by 1 on each iteration and cannot exceed a.Length

        while (s + m + b != a.Length)

        {

            // s + m + b < a.Length

            if(a[s + m] == mid)

                m++;

            else if(a[s + m] < mid)

            {

                // a[s] == mid

                swap(ref a[s + m], ref a[s]);

                // a[s] < mid and a[s+m] == mid

                s++;

            }

            else

            {   // a[s + m] > mid 

                swap(ref a[s + m], ref a[a.Length - 1 - b]);

                // a[a.Length - 1 - b] > mid

                b++;

            }

        }

        // post-condition: invariant and s + m + b = a.Length => all array is partitioned

    }

    public static void printArray(int[] a)

    {

        for(int i = 0; i <a.Length; ++i)

        {

            Console.Write(" " + a[i]);

        }

        Console.WriteLine();

    }

    public static void swap(ref int a, ref int b)

    {

        int temp = a;

        a = b;

        b = temp;

    }

}