Given an array of numbers, it is required to sort ascending odd numbers but even numbers must be on their places.
ex:
{ 5, 3, 2, 8, 1, 4 } should give { 1, 3, 2, 8, 5, 4 }
{ 5, 3, 1, 8, 0 } should give { 1, 3, 5, 8, 0 }
Algorithm:
define sorted list
define another list to save the odd number indexes
Iterate through the array for each item
if item is even skip it
if item is odd:
add it to the sorted list
add the item index to indexes list
loop through the indexes list, for each index
save the item from the sorted list into the the numbers array at the that index
Note: the sorted list should support duplicate items
Example implementations
Using a list
using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace sortOdd
{
public class Program
{
static void Main(string[] args)
{
CollectionAssert.AreEqual(new int[] { 1, 3, 2, 8, 5, 4 }, Program.SortArray(new int[] { 5, 3, 2, 8, 1, 4 }));
CollectionAssert.AreEqual(new int[] { 1, 3, 5, 8, 0 }, Program.SortArray(new int[] { 5, 3, 1, 8, 0 }));
CollectionAssert.AreEqual(new int[] { }, Program.SortArray(new int[] { }));
}
public static int[] SortArray(int[] array)
{
var result = new int[array.Length];
List<int> sortedOdd = new List<int>();
var indexes = new List<int>();
for (int i = 0; i < array.Length; i++)
{
if (array[i]%2 == 0)
result[i] = array[i];
else
{
int index = sortedOdd.BinarySearch(array[i]);
if (index < 0)
sortedOdd.Insert(~index, array[i]);
else
sortedOdd.Insert(index, array[i]);
indexes.Add(i);
}
}
for (int i = 0; i < indexes.Count; i++)
{
result[indexes.ElementAt(i)] = sortedOdd.ElementAt(i);
}
return result;
}
}
}
ex:
{ 5, 3, 2, 8, 1, 4 } should give { 1, 3, 2, 8, 5, 4 }
{ 5, 3, 1, 8, 0 } should give { 1, 3, 5, 8, 0 }
Algorithm:
define sorted list
define another list to save the odd number indexes
Iterate through the array for each item
if item is even skip it
if item is odd:
add it to the sorted list
add the item index to indexes list
loop through the indexes list, for each index
save the item from the sorted list into the the numbers array at the that index
Note: the sorted list should support duplicate items
Example implementations
Using a list
using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace sortOdd
{
public class Program
{
static void Main(string[] args)
{
CollectionAssert.AreEqual(new int[] { 1, 3, 2, 8, 5, 4 }, Program.SortArray(new int[] { 5, 3, 2, 8, 1, 4 }));
CollectionAssert.AreEqual(new int[] { 1, 3, 5, 8, 0 }, Program.SortArray(new int[] { 5, 3, 1, 8, 0 }));
CollectionAssert.AreEqual(new int[] { }, Program.SortArray(new int[] { }));
}
public static int[] SortArray(int[] array)
{
var result = new int[array.Length];
List<int> sortedOdd = new List<int>();
var indexes = new List<int>();
for (int i = 0; i < array.Length; i++)
{
if (array[i]%2 == 0)
result[i] = array[i];
else
{
int index = sortedOdd.BinarySearch(array[i]);
if (index < 0)
sortedOdd.Insert(~index, array[i]);
else
sortedOdd.Insert(index, array[i]);
indexes.Add(i);
}
}
for (int i = 0; i < indexes.Count; i++)
{
result[indexes.ElementAt(i)] = sortedOdd.ElementAt(i);
}
return result;
}
}
}
Using sorted list
using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace sortOdd
{
public class Program
{
static void Main(string[] args)
{
CollectionAssert.AreEqual(new int[] { 1, 3, 2, 8, 5, 4 }, Program.SortArray(new int[] { 5, 3, 2, 8, 1, 4 }));
CollectionAssert.AreEqual(new int[] { 1, 3, 5, 8, 0 }, Program.SortArray(new int[] { 5, 3, 1, 8, 0 }));
CollectionAssert.AreEqual(new int[] { }, Program.SortArray(new int[] { }));
}
public static int[] SortArray(int[] array)
{
var result = new int[array.Length];
var sortedOdd = new SortedSet<int>(new DuplicateKeyComparer<int>());
var indexes = new List<int>();
for (int i = 0; i < array.Length; i++)
{
if (array[i]%2 == 0)
result[i] = array[i];
else
{
sortedOdd.Add(array[i]);
indexes.Add(i);
}
}
for (int i = 0; i < indexes.Count; i++)
{
result[indexes.ElementAt(i)] = sortedOdd.ElementAt(i);
}
return result;
}
}
public class DuplicateKeyComparer<TKey>:IComparer<TKey> where TKey : IComparable
{
public int Compare(TKey x, TKey y)
{
int result = x.CompareTo(y);
if (result == 0)
return 1;
return result;
}
}
}
No comments:
Post a Comment