hektor.espinosa
BAN USERThis is the output every time I perform a swap
-1 5 3 -2 0 3 -7 4 -6
-1 5 -2 3 0 3 -7 4 -6
-1 -2 5 3 0 3 -7 4 -6
-1 -2 5 3 0 -7 3 4 -6
-1 -2 5 3 -7 0 3 4 -6
-1 -2 5 -7 3 0 3 4 -6
-1 -2 -7 5 3 0 3 4 -6
-1 -2 -7 5 3 0 3 -6 4
-1 -2 -7 5 3 0 -6 3 4
-1 -2 -7 5 3 -6 0 3 4
-1 -2 -7 5 -6 3 0 3 4
-1 -2 -7 -6 5 3 0 3 4
-1 -2 -7 -6 5 3 0 3 4
How about this approch in C#? Is not O(n) exactly but neither O(n^2)
class Program
{
static void Main(string[] args)
{
//int[] input = { 1, 7, -5, 9, -12, 15 };
int[] input = { 5, -1, 3, -2, 0, 3, -7, 4, -6 };
int[] result = OrderByOrderApperance(input);
Display(result);
Console.Read();
}
public static int[] OrderByOrderApperance(int[] input)
{
int p = 0;
int q = 0;
int i = 0;
int count = 0;
while (i < input.Length)
{
if (input[i] < 0)
{
if (q <= i)
{
Swap(input, i, p);
if (p == q)
q++;
if (p > 1)
{
i = p--;
}
//Display(input);
}
else
{
i = q;
p = 0;
}
}
else
{
if (p > 0)
p++;
else
p = i;
i++;
}
count++;
}
return input;
}
private static int[] Swap(int[] input, int a, int b)
{
if (a != b)
{
input[a] ^= input[b];
input[b] ^= input[a];
input[a] ^= input[b];
}
return input;
}
private static void Display(int[] input)
{
for (int i = 0; i < input.Length; i++)
{
Console.Write(" {0} ", input[i]);
}
Console.WriteLine();
}
}
How about this approch in C#? Is not O(n) exactly but neither O(n^2)
class Program
{
static void Main(string[] args)
{
//int[] input = { 1, 7, -5, 9, -12, 15 };
int[] input = { 5, -1, 3, -2, 0, 3, -7, 4, -6 };
int[] result = OrderByOrderApperance(input);
Display(result);
Console.Read();
}
public static int[] OrderByOrderApperance(int[] input)
{
int p = 0;
int q = 0;
int i = 0;
int count = 0;
while (i < input.Length)
{
if (input[i] < 0)
{
if (q <= i)
{
Swap(input, i, p);
if (p == q)
q++;
if (p > 1)
{
i = p--;
}
//Display(input);
}
else
{
i = q;
p = 0;
}
}
else
{
if (p > 0)
p++;
else
p = i;
i++;
}
count++;
}
return input;
}
private static int[] Swap(int[] input, int a, int b)
{
if (a != b)
{
input[a] ^= input[b];
input[b] ^= input[a];
input[a] ^= input[b];
}
return input;
}
private static void Display(int[] input)
{
for (int i = 0; i < input.Length; i++)
{
Console.Write(" {0} ", input[i]);
}
Console.WriteLine();
}
}
Using recursion and Permutations
- hektor.espinosa October 24, 2013