0

I need to re-order a list consecutively if it is already not. Can anyone suggest a way to check it so that I can write an extension method to call like this?

var cglist = collectionGroups.OrderBy(x => x.Sequence).ToList();

if (cglist.IsConsecutive)
{
   for (int i = 0; i < cglist.Count(); i++)
   {
      //sorting logic...
    } 
 }

x.Sequence is not an incremented property in the entity and has duplicates and missing values. This data is fed to my context from an outer source which I have no control of. So I need to use it in a reordering method and make it adjacent

I could find the closest solution from this answer here which does not really seem to be checking adjacency.

Community
  • 1
  • 1
G.Anıl Yalçın
  • 188
  • 1
  • 14
  • What's wrong with the linked answer? It appears to do exactly what you want. There is no way to check if it's sorted consecutively without looping through every item and checking it against the previous item. And that's what the linked answer does. – Matt Burland Aug 25 '16 at 15:45
  • I think checking if the list is consecutive will imply checking every element, this is costly. After this you'll need to reorder the list. So worst case scenario is iterating through list 2 times. I would skip checking if it is consecutive. So the worst case will be equal to best case: iterating through list only 1 time – Alex Aug 25 '16 at 15:45
  • And since you've ordered your list with `OrderBy`, why wouldn't it be consecutive? Why would it need to be reordered? Consecutive by what criteria? – Matt Burland Aug 25 '16 at 15:47
  • @MattBurland `x.Sequence` is not an incremented property in the entity and has equal duplicates and missing values. This data is fed to my context from an outer source which I have no control of. So I need to use it in a reordering method and make it adjacent. – G.Anıl Yalçın Aug 25 '16 at 15:56
  • Can you please give an example? I.e. how you expect {1,5,5,5} to be "re-order a list consecutively" – Alexei Levenkov Aug 25 '16 at 16:00
  • Side note: if all you are looking for is making extension callable as property - answer is no, would be duplicate of http://stackoverflow.com/questions/619033/does-c-sharp-have-extension-properties – Alexei Levenkov Aug 25 '16 at 16:02
  • 1
    @AlexeiLevenkov as consecutive like {0,1,2,3} – G.Anıl Yalçın Aug 25 '16 at 16:03
  • @AlexeiLevenkov nope, not looking for that. – G.Anıl Yalçın Aug 25 '16 at 16:04
  • 1
    Can you please [edit] your post and inline " x.Sequence is not an incremented property ... use it in a reordering method and make it adjacent." comment? It is very unclear what you actually have problem with (make sure to remove all unrelated questions/remarks from the post - all "re-order" notes are very confusing) – Alexei Levenkov Aug 25 '16 at 16:07

3 Answers3

2

The only way to check if the list is sorted is to go through every item in the list and compare it to the next item, in which case you might as well just call sort in the first place as that will perform the exact same check and sort anything out of order

Edit: i'm suspicious of the fact that you keep using the word "consecutively"

if you are looking for Missing or Duplicated Values then that is not mentioned in your question at all, but if that is the case a simple left join will do that for you with no need of sorting

var min = collectionGroups.Min(x => x.Sequence);
var deviation = collectionGroups.Max(x => x.Sequence) - min;

var result = from i in Enumerable.Range(min, deviation )
             join c in collectionGroups on i equals c.Sequence into grp;
             from g in grp.DefaultIfEmpty()
             where g.Count() != 1
             select new{ ID=g.Key, Count=g.Count()};

this will then return a list of duplicate or missing values no sorting needed

Edit in reply to comment by juunas

var data = Enumerable.Range(0, 20000000).ToList();
bool sort = false;
for (int i = 0; i < data.Count - 1; i++)
{
    if (data[i] > data[i + 1])
    {
        sort = true;
        break;
    }
}
if (sort) data.Sort();

884 ms

Compared to 

var data = Enumerable.Range(0, 20000000).ToList();
data.Sort();

651ms

MikeT
  • 5,398
  • 3
  • 27
  • 43
  • Except checking is O(n), while sorting is O(n log n). Just checking will take less time. – juunas Aug 25 '16 at 15:53
  • 1
    @juunas you can pick sorting algorithm that is O(n) for already sorted sequence... – Alexei Levenkov Aug 25 '16 at 15:57
  • Well, that is true that if you are possibly going to sort it anyway, might as well just sort it instead of wasting time checking if it's necessary. – juunas Aug 25 '16 at 16:30
  • @MikeT Can this be applied in an object list and committed to the database? – G.Anıl Yalçın Aug 25 '16 at 16:34
  • it can apply to anything, if you are using Linq to sql then the sort performance will be higher as the database will do an optimised sort using indexes to enhance performance – MikeT Aug 25 '16 at 16:38
  • So, how do I sort by `x.Sequence` as in orderby? Sorry... Got that already – G.Anıl Yalçın Aug 25 '16 at 16:41
  • Sort is a function of List you can feed in a custom comparer https://msdn.microsoft.com/en-us/library/w56d4y5z(v=vs.110).aspx but i doubt you'll get much if any improvement on orderby, as you have already sorted by Sequence this has been done already. if you want to find duplicates or missing numbers that's a completely different question to what you asked – MikeT Aug 25 '16 at 16:48
1

You can use the solution included in this answer. You'd only need to change the checks >=0 and <=0 to ==1 and ==-1.

Community
  • 1
  • 1
InBetween
  • 32,319
  • 3
  • 50
  • 90
0

Use following loop to check sorting

bool isSorted = true;

for(int i = 0;i < cglist.Count; i++)
{
   if( i == cglist.Count - 1)
   {
      break;
   }

   if(cglist[i] > cglist[i + 1])
   {
      isSorted = false;
   }

}
Lakhtey
  • 35
  • 1
  • 13