Skip to content

Instantly share code, notes, and snippets.

@unilecs

unilecs/DNF.cs Secret

Created July 26, 2019 04:38
Show Gist options
  • Save unilecs/20efb90650b4da83363cd4eb1e00ff27 to your computer and use it in GitHub Desktop.
Save unilecs/20efb90650b4da83363cd4eb1e00ff27 to your computer and use it in GitHub Desktop.
Задача флага Нидерладндов
using System;
public class Program
{
private static void Swap(ref int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static void DnfSort(ref int[] arr)
{
int start = 0, mid = 0, end = arr.Length - 1;
int point = 1; // опорная точка
while (mid <= end)
{
if (arr[mid] < point) // элемент равен нулю
{
Swap(ref arr, start, mid);
start++;
mid++;
}
else if (arr[mid] > point) // элемент равен 2
{
Swap(ref arr, mid, end);
end--;
}
else // элемент равен 1
{
mid++;
}
}
}
private static void DnfSortByDescending(ref int[] arr)
{
int start = 0, mid = 0, end = arr.Length - 1;
int point = 1; // опорная точка
while (mid <= end)
{
if (arr[mid] < point) // элемент равен нулю
{
Swap(ref arr, mid, end);
end--;
}
else if (arr[mid] > point) // элемент равен 2
{
Swap(ref arr, start, mid);
start++;
mid++;
}
else // элемент равен 1
{
mid++;
}
}
}
public static void Main()
{
Console.WriteLine("UniLecs");
// sort by ascending
int[] arr = new int[] { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 };
DnfSort(ref arr);
Console.WriteLine("Answer = " + string.Join(", ", arr));
// sort by descending
arr = new int[] { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 };
DnfSortByDescending(ref arr);
Console.WriteLine("Answer = " + string.Join(", ", arr));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment