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, Oct 24 '15 at 12:22
Looks like a duplicate of [this question](http://stackoverflow.com/questions/5347616/how-to-sort-an-integer-array-into-negative-zero-positive-part-without-changing) — jmik, Oct 24 '15 at 12:49
You are not in fact iterating the array more than once. You're iterating it exactly once. — Servy, Oct 26 '15 at 16:09

score 4 · Accepted Answer · edited May 23 '17 at 11:45

4

According to this OrderBy is stable so:

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

edited May 23 '17 at 11:45

Community

1
1

answered Oct 26 '15 at 15:54

AlexDev

4,049
31
36

@Hakam Just tried the code with the examples in linqpad and it worked. Try it. – AlexDev Oct 26 '15 at 15:58
Yes you are right. this is must be the accepted answer, becuase it is very very very simple and elegant – Hakan Fıstık Oct 26 '15 at 16:05
2

You can simply do enumerable.OrderBy(x=>x); – Sunny Sharma Feb 16 '17 at 04:59

score 3 · Answer 2 · answered Feb 16 '17 at 05:01

3

I like these one:

For Order By Ascending

enumerable.OrderBy(x => x);

For Order By Descending

enumerable.OrderByDescending(x => x);

answered Feb 16 '17 at 05:01

Sunny Sharma

4,688
5
35
73

Striter Alfa · Answer 3 · 2015-10-26T15:47:07.723

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();
}

D Stanley · Answer 4 · 2015-10-26T16:01:34.263

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;
}

Sort int array using linq?

4 Answers4