Insert multiple items into List or Array (no Linq and not quite CodeGolf)

Question

No matter how I try, I can't seem to create a nice and clean algorithm for doing the following:

1. System.Array (or generic List) data of System.Object
2. System.Array (or generic List) xval of System.Object
3. System.Array (or generic List) idxs of System.Int32

xval and idxs contain the same number of elements and idxs contains no values less than zero or larger than data.Length

I need to insert all elements in xval into the data array, where the associated integer in idxs represents the insertion index in the original, unmolested data.

For example:

*data* = {A, B, C, D, E, F, G, H}
*xval* = {U, V, W, X, Y, Z}
*idxs* = {5, 0, 0, 0, 1, 1}

*output* = {V, W, X, A, Y, Z, B, C, D, E, U, F, G, H}

It's easy enough to do, but I always end up with icky code. My best attempt so far (but I'm worried about rounding errors):

  idxs.Reverse()
  xval.Reverse()

  Dim N As Int32 = data.Count + xval.Count
  Dim map(N - 1) As Double
  Dim output(N - 1) As Object

  Dim k As Int32 = -1
  For i As Int32 = 0 To data.Count - 1
    k += 1
    map(k) = i
    output(k) = data(i)
  Next
  For i As Int32 = 0 To xval.Count - 1
    k += 1
    map(k) = idxs(i) - ((i + 1) * 1e-8)
    output(k) = xval(i)
  Next

  Array.Sort(map, output)

Answer 1

I'd go for something like this (replace 'char' with 'object')

char[] data = new char[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
char[] xval = new char[] { 'U', 'V', 'W', 'X', 'Y', 'Z' };
int[] idxs = new int[] { 5, 0, 0, 0, 1, 1 };
List<char> output = data.ToList();

Dictionary<int, List<char>> dict = new Dictionary<int, List<char>>();
for (int i = 0; i < idxs.Length; i++)
{
    if (!dict.ContainsKey(idxs[i]))
        dict.Add(idxs[i], new List<char>());
    dict[idxs[i]].Add(xval[i]);
}
List<int> keys = dict.Keys.ToList();
keys.Sort();
keys.Reverse();
foreach (int key in keys)
    output.InsertRange(key,dict[key]);

Answer 2

Note that there's no inversion of the lists.

    IList<Object> data = new Object[] { "A", "B", "C", "D", "E", "F", "G", "H" };
    IList<Object> xval = new Object[] { "U", "V", "W", "X", "Y", "Z" };
    IList<int> idxs = new int[] { 5, 0, 0, 0, 1, 1 };

    List<Object> output = new List<object>(data);

    for (int i = 0; i < xval.Count; i++)
    {
        int currentIndex = idxs[i];
        Object dataElement= data[currentIndex]; // We should insert the new element before this element.
        int elementsIndex = output.IndexOf(dataElement);
        output.Insert(elementsIndex, xval[i]);
    }
    return output;

Answer 3

Here is my attempt, which doesn’t use IndexOf, Sort, Reverse, dictionaries, or doubles.

// input data
char[] data = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
char[] xval = { 'U', 'V', 'W', 'X', 'Y', 'Z' };
int[] idxs = { 5, 0, 0, 0, 1, 1 };

// algorithm starts here
var output = new List<char>(data);
for (int i = 0; i < idxs.Length; i++)
{
    // Insert the i’th item in the right place
    output.Insert(idxs[i], xval[i]);

    // Increment all the following indexes so that they
    // will insert in the right place
    for (int j = i + 1; j < idxs.Length; j++)
        if (idxs[j] >= idxs[i])
            idxs[j]++;
}

// outputs V, W, X, A, Y, Z, B, C, D, E, U, F, G, H
Console.WriteLine(string.Join(", ", output));

Of course, if you don’t want the algorithm to modify the idxs array, then simply make a copy of it first.

Answer 4

'*data* = {A, B, C, D, E, F, G, H}
'*xval* = {U, V, W, X, Y, Z}
'*idxs* = {5, 0, 0, 0, 1, 1}
'*output* = {V, W, X, A, Y, Z, B, C, D, E, U, F, G, H}
    Dim data As New List(Of String)
    Dim xval As New List(Of String)
    Dim idxs As New List(Of Integer)
    Dim output As New List(Of String)

    data.AddRange(New String() {"A", "B", "C", "D", "E", "F", "G", "H"})
    xval.AddRange(New String() {"U", "V", "W", "X", "Y", "Z"})
    idxs.AddRange(New Integer() {5, 0, 0, 0, 1, 1})

    For x As Integer = 0 To data.Count - 1 'for each item in the data
        Dim idx As Integer = idxs.IndexOf(x)
        Do While idx <> -1 'do we have xval's for this index
            output.Add(xval(idx)) 'yes add it
            xval.RemoveAt(idx) 'remove the items from xval
            idxs.RemoveAt(idx) 'and idxs
            idx = idxs.IndexOf(x)
        Loop
        output.Add(data(x)) 'add data item to list
    Next