מריה בוטוסוב

יש לך מערך עם כדורים אדומים, צהובים וירוקים. אתה צריך לסדר אותו כך שכל האדומים יהיו בהתחלה וכל הירוקים יהיו בסוף. אין לך שטח זיכרון נוסף להשתמש בו.

אנחנו ננסה לארגן כדורים אדומים מתחילת המערך, כחולים בסוף המערך.

ירוקים יסתדרו לבד באמצע.

סיבוכיות זמן – O(n), סיבוכיות זיכרון – O(1).

public static char[] SortColors(char[] InputArray)
{
    //Error Handler
    if (InputArray == null || InputArray.Length == 0)
        throw new Exception("Input Array Is Null or Empty");
    //Variable Declaration and Initialization
    int ctrRed = 0, ctrBlue = InputArray.Length - 1;
    for (int i = 0; i < ctrBlue; i++)
    {
        if (ctrRed < ctrBlue)
        {
            if (InputArray[i] == 'R')
            {
                Swap(ref InputArray[i], ref InputArray[ctrRed++]);
            }
            else if (InputArray[i] == 'B')
            {
                Swap(ref InputArray[i], ref InputArray[ctrBlue--]);
                i--;
            }
        }
    }
    return InputArray;
}
 
public static void Swap<T>(ref T InputA, ref T InputB)
{
    T temp = InputA;
    InputA = InputB;
    InputB = temp;
}