Sort int array using linq?

Question

PROBLEM

Write a program to sort any given integer array of positive and negative numbers such that positive numbers follow negative numbers, however relative position of positive and negative numbers remains same. Like in the example below (1), (-7) occurs after (-5) hence in sorted array (-7) follows (-5).

The program should iterate given array only once and should not use temporary array.

Example 1. Given Array: { 2, 4, -5, 0, -7, -2, 2, -5, 1, -9, -7, -1 }

Sorted Array: { -5, -7, -2, -5, -9, -7, -1, 2, 4, 0, 2, 1 }

Example 2. Given Array: { -3, 7, 0, -2, -1, 3, -3, 9, 5, -5, 8}

Sorted Array: { -3, -2, -1, -3, -5, 7, 0, 3, 9, 5 , 8}

MY SOLUTION

class Program
{
    public static void Main(string[] args)
    {
        var intArray = new int[] {  2, 4, -5, 0, -7, -2, 2, -5, 1, -9, -7, -1 };
        var sorted_intArray = SortIntArray(intArray);
        Console.WriteLine(String.Join(",", sorted_intArray));

        intArray = new int[] { -3, -2, -1, -3, -5, 7, 0, 3, 9, 5, 8 };
        sorted_intArray = SortIntArray(intArray);
        Console.WriteLine(String.Join(",", sorted_intArray));
        Console.ReadLine();
    }

    private static int[] SortIntArray(int[] intArray)
    {
        var sorted_intArray = intArray.GroupBy(_int => _int < 0 ? -1 : 1)// Create group of +ve and -ve numbers
                             .OrderBy(group => group.Key)  // Bring group of -ve number first
                             .SelectMany(groupedItems => groupedItems).ToArray(); // Select num from both Group and convert to array
        return sorted_intArray;
    }
}

QUESTION

i) The problem statement says , numbers should be iterated only once and temporary array should not be used. I believe my solution using linq do not meet this requirement. How to solve mentioned problem with linq , if possible?

ii) What could be other possible and efficient ways to solve mentioned problem with or without linq? Solution using C/C++ is also fine.

There is a possible solution creating a temporary data structure in an extension method. I can't see how it can be solved without a temp. data structure storing the positive integers given you want to (input?) numbers to pe iterated once, right ? This way output numbers can be iterated once — Emmanuel DURIN
– Emmanuel DURIN, Commented Oct 24, 2015 at 12:22
You are not in fact iterating the array more than once. You're iterating it exactly once. — Servy
– Servy, Commented Oct 26, 2015 at 16:09

Community · Accepted Answer · 2017-05-23 11:45:36Z

4

According to this OrderBy is stable so:

enumerable.OrderBy(x => x >= 0);

edited May 23, 2017 at 11:45

CommunityBot

11 silver badge

answered Oct 26, 2015 at 15:54

AlexDev

4,8971 gold badge34 silver badges38 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

AlexDev Over a year ago

@Hakam Just tried the code with the examples in linqpad and it worked. Try it.

Hakan Fıstık Over a year ago

Yes you are right. this is must be the accepted answer, becuase it is very very very simple and elegant

Sunny Sharma Over a year ago

You can simply do enumerable.OrderBy(x=>x);

Sunny Sharma · Accepted Answer · 2017-02-16 05:01:43Z

4

I like these one:

For Order By Ascending

enumerable.OrderBy(x => x);

For Order By Descending

enumerable.OrderByDescending(x => x);

answered Feb 16, 2017 at 5:01

Sunny Sharma

5,0045 gold badges41 silver badges76 bronze badges

Comments

Striter Alfa · Accepted Answer · 2015-10-26 15:47:07Z

1

Linq is amazing:

private static int[] SortIntArrayWithDuplicates(IEnumerable<int> intArray)
{
    var enumerable = intArray as int[] ?? intArray.ToArray();

    return enumerable.Where(x => x < 0)
        .Concat(enumerable.Where(x => x >= 0))
        .ToArray();
}

private static int[] SortIntArrayWithoutDuplicates(IEnumerable<int> intArray)
{
    var enumerable = intArray as int[] ?? intArray.ToArray();

    return enumerable.Where(x => x < 0)
        .Union(enumerable.Where(x => x >= 0))
        .ToArray();
}

edited Oct 26, 2015 at 15:47

answered Oct 26, 2015 at 14:18

Striter Alfa

1,5771 gold badge16 silver badges31 bronze badges

Comments

D Stanley · Accepted Answer · 2015-10-26 16:01:34Z

You don't need grouping at all. Linq-to-objects is "stable" (meainig it keeps the original order for "duplicate" objects) when using OrderBy, so you can just order on whether or not the number is less than zero:

private static int[] SortIntArray(int[] intArray)
{
    var sorted_intArray = intArray.OrderBy(i => i < 0 ? 0 : 1).ToArray(); 
    return sorted_intArray;
}

Output:

-5,-7,-2,-5,-9,-7,-1,2,4,0,2,1
-3,-2,-1,-3,-5,7,0,3,9,5,8

Note that if you change your return type to IEnumerable<int> then you can avoid the ToArray call and reduce your memory usage.

Whether or not you count a Linq ordering as "iterated once" is up to whoever gave you that requirement. I don't know of any sorting algorithm that can be done in one pass.

What could be other possible and efficient ways to solve mentioned problem with or without linq?

Well I can see how you'd do it in two passes by scanning all numbers, taking negative ones first, then scan again, taking all non-negative ones. You can simplify this with yield syntax:

private static IEnumerable<int> SortIntArray(int[] intArray)
{
    foreach(var i in intArray)
        if(i < 0) yield return i;
    foreach(var i in intArray)
        if(i >= 0) yield return i;
}

Collectives™ on Stack Overflow

Sort int array using linq?

4 Answers 4

3 Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related