CODEWITHSUNDEEP
c#sorting
Manish Basantani
Manish Basantani

Reputation: 17509

Merging two lists into one and sorting the items

Is there a way to merge(union without dupes) two given lists into one and store the items in sorted way by using ONE for loop?

Also, i am looking for a solution which does not makes use of API methods ( like, union, sort etc).

Sample Code.

private static void MergeAndOrder() 
{
var listOne = new List<int> {3, 4, 1, 2, 7, 6, 9, 11}; 
var listTwo = new List<int> {1, 7, 8, 3, 5, 10, 15, 12}; 

//Without Using C# helper methods...
//ToDo.............................

//Using C# APi.
var expectedResult = listOne.Union(listTwo).ToList(); 
expectedResult.Sort();//Output: 1,2,3,4,5,6,7,8,9,10,11,12,15
//I need the same result without using API methods, and that too by iterating over items only once.


}

PS: I have been asked this question in an interview, but couldn't find answer as yet.

Upvotes: 4

Views: 21364

Answers (11)

Alireza
Alireza

Reputation: 11

you can also do this, (I have considered numbers to be in arrays, but the overall logic doesn't differ).

int[] A = new int[] { 3, 4, 1, 2, 7, 6, 9, 11 };
int[] B = new int[] { 1, 7, 8, 3, 5, 10, 15, 12 };
int[] mainArr = MergeArrays(A, B);

int[] orderedArr = Sort(mainArr);
for (int i = 0; i < 6; i++)
{
    Console.WriteLine(orderedArr[i]);

}

int[] MergeArrays(int[] arr1, int[] arr2)
{
    int total = arr1.Length + arr2.Length;
    int[] arr = new int[total];
    for (int i = 0; i < total; i++)
    {
        if (i >= arr1.Length)
        {
            arr.SetValue(arr2[i - arr1.Length], i);
        }
        else
        {
            arr.SetValue(arr1[i], i);
        }
    }
    return arr;
}

int GetLargest(int[] array, int[] exceptions)
{

    int i = 0;

    while (Contains(exceptions, array[i]))
    {
        i++;
    }
    int a = array[i++];
    i = 0;
    do
    {
        if (Contains(exceptions, array[i + 1])) { i++; continue; }

        if (a < array[i + 1])
            a = array[i + 1];
        i++;
    }
    while (i != array.Length - 1);
    return a;
}

bool Contains(int[] array, int num)
{
    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] == num)
            return true;
    }
    return false;
}

int[] Sort(int[] array)
{
    int[] finallArr = new int[array.Length];
    for (int i = array.Length; i > 0; i--)
    {
        finallArr[array.Length - i] = GetLargest(array, finallArr);
    }enter code here
    return finallArr;
}

Upvotes: 1

m-ringler
m-ringler

Reputation: 1

This is a solution if the two collections are already sorted (the only scenario where the question makes sense):

/// <summary>
/// Efficiently merges two *sorted* collections in O(n) time, so that the result is again sorted.
/// </summary>
/// <remarks>
/// This method uses <see cref="Comparer{T}.Default"/>.
/// <para/>
/// When two items compare equal, the item from <paramref name="sorted1"/>
/// is sorted before the item from <paramref name="sorted2"/>.
/// </remarks>
/// <typeparam name="T">The type of the items in the collections.</typeparam>
/// <param name="sorted1">The first collection.</param>
/// <param name="sorted2">The second collection.</param>
/// <returns>The merged sorted collection.</returns>
/// <exception cref="ArgumentNullException">Thrown when any argument is <c>null</c>.</exception>
public static IEnumerable<T> MergeTwoSortedCollections<T>(IEnumerable<T> sorted1, IEnumerable<T> sorted2)
{
    return MergeTwoSortedCollections<T>(sorted1, sorted2, Comparer<T>.Default.Compare);
}


/// <summary>
/// Efficiently merges two *sorted* collections in O(n) time, so that the result is again sorted.
/// </summary>
/// <remarks>
/// When <paramref name="compareItems"/> returns 0 for two items, the item from <paramref name="sorted1"/>
/// is sorted before the item from <paramref name="sorted2"/>.
/// </remarks>
/// <typeparam name="T">The type of the items in the collections.</typeparam>
/// <param name="sorted1">The first collection.</param>
/// <param name="sorted2">The second collection.</param>
/// <param name="compareItems">The function used to compare items.</param>
/// <returns>The merged sorted collection.</returns>
/// <exception cref="ArgumentNullException">Thrown when any argument is <c>null</c>.</exception>
public static IEnumerable<T> MergeTwoSortedCollections<T>(IEnumerable<T> sorted1, IEnumerable<T> sorted2, Comparison<T> compareItems)
{
    _ = sorted1 ?? throw new ArgumentNullException(nameof(sorted1));
    _ = sorted2 ?? throw new ArgumentNullException(nameof(sorted2));
    _ = compareItems ?? throw new ArgumentNullException(nameof(compareItems));

    return Core();

    IEnumerable<T> Core()
    {
        using var e1 = sorted1.GetEnumerator();
        using var e2 = sorted2.GetEnumerator();

        bool valid1 = e1.MoveNext();
        bool valid2 = e2.MoveNext();

        while (valid1 || valid2)
        {
            if (valid1 && (!valid2 || compareItems(e1.Current, e2.Current) <= 0))
            {
                yield return e1.Current;
                valid1 = e1.MoveNext();
            }
            else
            {
                yield return e2.Current;
                valid2 = e2.MoveNext();
            }
        }
    }
}

Upvotes: 0

Joel Coehoorn
Joel Coehoorn

Reputation: 415931

Why can't you use the api methods? Re-inventing the wheel is dumb. Also, it's the .ToList() call that's killing you. Never call .ToList() or .ToArray() until you absolutely have to, because they break your lazy evaluation.

Do it like this and you'll enumerate the lists with the minimum amount necessary:

var expectedResult = listOne.Union(listTwo).OrderBy(i => i);

This will do the union in one loop using a hashset, and lazy execution means the base-pass for the sort will piggyback on the union. But I don't think it's possible finish the sort in a single iteration, because sorting is not a O(n) operation.

Upvotes: 13

Maksym Tatsenko
Maksym Tatsenko

Reputation: 151

Try this:

      public static IEnumerable<T> MergeWith<T>(IEnumerable<T> collection1, IEnumerable<T> collection2,
            IComparer<T> comparer)
        {
            using (var enumerator1 = collection1.GetEnumerator())
            using (var enumerator2 = collection2.GetEnumerator())
            {
                var isMoveNext1 = enumerator1.MoveNext();
                var isMoveNext2 = enumerator2.MoveNext();

                do
                {
                    while (comparer.Compare(enumerator1.Current, enumerator2.Current) < 0 || !isMoveNext2)
                    {
                        if (isMoveNext1)
                            yield return enumerator1.Current;
                        else
                            break;

                        isMoveNext1 = enumerator1.MoveNext();
                    }

                    if (isMoveNext2)
                        yield return enumerator2.Current;

                    isMoveNext2 = enumerator2.MoveNext();
                } while (isMoveNext1 || isMoveNext2);
            }
        }

Upvotes: 1

Bartek
Bartek

Reputation: 97

Using iterators and streaming interface the task is not that complicated:

class MergeTwoSortedLists { static void Main(string[] args) {

        var list1 = new List<int?>() {
            1,3,5,9,11
        };

        var list2 = new List<int?>() {
            2,5,6,11,15,17,19,29
        };

        foreach (var c in SortedAndMerged(list1.GetEnumerator(), list2.GetEnumerator())) {
            Console.Write(c+" ");
        }

        Console.ReadKey();
    }

    private static IEnumerable<int> SortedAndMerged(IEnumerator<int?> e1, IEnumerator<int?> e2) {
        e2.MoveNext();
        e1.MoveNext();

        do {
            while (e1.Current < e2.Current) {
                if (e1.Current != null) yield return e1.Current.Value;
                e1.MoveNext();
            }

            if (e2.Current != null) yield return e2.Current.Value;
            e2.MoveNext();
        } while (!(e1.Current == null && e2.Current == null));
    }
}

Upvotes: 1

Sailaja V
Sailaja V

Reputation: 11

    private static void MergeTwoSortedArray(int[] first, int[] second)
    {
        //throw new NotImplementedException();

        int[] result = new int[first.Length + second.Length];

        int i=0 , j=0 , k=0;

        while(i < first.Length && j <second.Length)
        {
            if(first[i] < second[j])
            {
                result[k++] = first[i++];
            }
            else
            {
                result[k++] = second[j++];
            }
        }

        if (i < first.Length)
        {
            for (int a = i; a < first.Length; a++)
                result[k] = first[a];
        }

        if (j < second.Length)
        {
            for (int a = j; a < second.Length; a++)
                result[k++] = second[a];
        }

        foreach (int a in result)
            Console.Write(a + " ");

        Console.WriteLine();
    }

Upvotes: 1

paulH
paulH

Reputation: 1132

This will only work for lists of integers, but happily that is what you have!

List<int> sortedList = new List<int>();
foreach (int x in listOne)
{
    sortedList<x> = x;
}
foreach (int x in listTwo)
{
    sortedList<x> = x;
}

This is using the values in each list as the index position at which to store the value. Any duplicate values will overwrite the previous entry at that index position. It meets the requirement of only one iteration over the values.

It does of course mean that there will be 'empty' positions in the list.

I suspect the job position has been filled by now though.... :-)

Upvotes: 0

ewernli
ewernli

Reputation: 38615

The closest solution I see would be to allocate an array knowing that integers are bounded to some value.

int[] values = new int[ Integer.MAX ]; // initialize with 0
int size1 = list1.size();
int size2 = list2.size();

for( int pos = 0; pos < size1 + size2 ; pos++ )
{
     int val =  pos > size1 ? list2[ pos-size1 ] : list1[ pos ] ;
     values[ val ]++;
}

Then you can argue that you have the sorted array in a "special" form :-) To get a clean sorted array, you need to traverse the values array, skip all position with 0 count, and build the final list.

Upvotes: 0

Jonathon Faust
Jonathon Faust

Reputation: 12545

Without the precondition that both lists are sorted before the merge + sort operation, you can't do this in O(n) time (or "using one loop").

Add that precondition and the problem is very easy.

Keep two iterators, one for each list. On each loop, compare the element from each list and choose the smaller. Increment that list's iterator. If the element you are about to insert in the final list is already the last element in that list, skip the insert.

In pseudocode:

List a = { 1, 3, 5, 7, 9 }
List b = { 2, 4, 6, 8, 10 }
List result = { }
int i=0, j=0, lastIndex=0
while(i < a.length || j < b.length)
    // If we're done with a, just gobble up b (but don't add duplicates)
    if(i >= a.length)
        if(result[lastIndex] != b[j])
            result[++lastIndex] = b[j]
        j++
        continue

    // If we're done with b, just gobble up a (but don't add duplicates)
    if(j >= b.length)
        if(result[lastIndex] != a[i])
            result[++lastIndex] = a[i]
        i++
        continue

    int smallestVal

    // Choose the smaller of a or b
    if(a[i] < b[j])
        smallestVal = a[i++]
    else
        smallestVal = b[j++]

    // Don't insert duplicates
    if(result[lastIndex] != smallestVal)
        result[++lastIndex] = smallestVal
end while

Upvotes: 11

Chris R. Timmons
Chris R. Timmons

Reputation: 2197

var listOne = new List<int> { 3, 4, 1, 2, 7, 6, 9, 11 };
var listTwo = new List<int> { 1, 7, 8, 3, 5, 10, 15, 12 };
var result = listOne.ToList();

foreach (var n in listTwo)
{
  if (result.IndexOf(n) == -1)
    result.Add(n);
}

Upvotes: 0

LBushkin
LBushkin

Reputation: 131726

You could write a loop that merges and de-dups the lists and uses a binary-search approach to insert new values into the destination list.

Upvotes: 0

Related Questions