How to sort (using strand sort algorithm) an array of integers? C#

Question

REGARDING MY QUESTION: I had an assignment in school, which i failed, because my code ran too slow. And now i have to fix and study it, because i will have to explain it how i fixed it and how it works.

My question is: What parts of my code can i fix to archive an average performance of O(n^2)? How can i make it run faster?

What is required:

sort an array of integers in an ascending order,
the algorithm must have an average performance of O(n^2),
the Sort() method of array must not be used,
System.Collections.Generic or other libraries are not allowed (only the system library is allowed),
strand sort algorithm must be used,

This is what i tried so far, but it works way too slow... I have to sort like 200000 numbers:

EDIT: this code doesn't work proper. I posted an updated version below.

static public int[] StrandSortAscending(int[] p1)
{
    int[] p2,
        p3;
    int p1s1,
        p2s1,
        p2s2,
        p3s1,
        p3s2,
        n;

    p2 = new int[p1.Length];
    p3 = new int[p1.Length];
    Reset(ref p2);
    Reset(ref p3);
    p1s1 = p1.Length;
    p3s1 = 0;

    while (p1s1 != 0)
    {
        n = int.MinValue;
        p2s1 = 0;

        for (int i8 = 0; i8 < p1.Length; i8++)
        {
            if (p1[i8] != int.MaxValue)
            {
                if (p1[i8] >= n)
                {
                    p2[p2s1] = p1[i8];
                    n = p1[i8];
                    p1[i8] = int.MaxValue;
                    p1s1--;
                    p2s1++;
                }
            }
        }

        int p3p,
            zs;
        bool pn = false;

        for (int i5 = 0; i5 < p2.Length; i5++)
        {
            p3p = int.MinValue;
            for (int i6 = 0; i6 < p3.Length; i6++)
            {
                if (pn)
                {
                    zs = p3[i6];
                    p3[i6] = p3p;
                    p3p = zs;
                }
                else
                {
                    if (p2[i5] >= p3p && p2[i5] <= p3[i6])
                    {
                        p3p = p3[i6];
                        p3[i6] = p2[i5];
                    }
                }
            }
        }

        Reset(ref p2);
    }

    return p3;
}

static void Reset(ref int[] a)
{
    for (int i = 0; i < a.Length; i++)
        a[i] = int.MaxValue;
}

The wikipedia link to the strand sort algorithm: http://en.wikipedia.org/wiki/Strand_sort

NOTE: My biggest mistake with this algorithm was, that i forgot that an array is a reference data type. And 2 arrays pointed to the same one in memory. I spend most of the time figuring out this problem. I was like... What the hell is wrong here... And then it finally clicked. :)

UPDATE (i have done some upgrades):

i got the merging algorithm idea here: How to merge two sorted arrays into a sorted array?

static public int[] StrandSortAscending2(int[] np)
  {
    int[] up = new int[np.Length]; // sorted array
    int[] zp = new int[np.Length]; // temporary array
    int[] nnp = new int[np.Length]; // new unsorted array
    int[] sp = new int[np.Length]; // merged sorted array

    int dvup = 0; // the length of non-empty elements of the sorted array

    int dvnp = np.Length; // the length of non-empty elements of the unsorted array

    //0. repeat until the unsorted array isn't empty
    while (dvnp > 0)
    {
        //NOTE: reference data type. 2 arrays point to the same array/table in memoty (RAM),
        //from the previous cycle, that's why the values in unsorted array (and temp and merged array) were wrong...
        zp = new int[np.Length];
        nnp = new int[np.Length];
        sp = new int[np.Length];

        //these counters are needed for knowing till which index of an array are the elements not-empty
        //so that i don't need to always increase and decrease the size of an array, but just overwrite the old values
        //the algorithm must not be slow, the higher memory usage is not a problem

        int dvzp = 0; // the length of non-empty elements of the temporary array
        int dvnnp = 0; // the length of non-empty elements of the new unsorted array

        //1.1 fill the temporary and the new unsorted array with values
        //1.2 the unsorted array should point then to the new unsorted array
        int nszp = int.MinValue; // biggest number of the temporary array

        for (int inp = 0; inp < dvnp; inp++) // index of unsorted array
        {
          if (inp == 0 || np[inp] > nszp)
          {
            nszp = np[inp];
            zp[dvzp++] = np[inp];
          }
          else
          {
            nnp[dvnnp++] = np[inp];
          }
        }

        np = nnp;
        dvnp = dvnnp;

        //2. merge temporary and sorted arrays 
        int izp = 0; // index/counter of temporary array
        int iup = 0; // index/counter of sorted array
        int isp = 0; // index/counter of merged array

        if (dvup > 0)
        {
          while (izp < dvzp && iup < dvup)
          {
            if (zp[izp] < up[iup])
                sp[isp++] = zp[izp++];
            else
                sp[isp++] = up[iup++];
          }

          //if there are still numbers left in the temporary array
          //then add then all to the merged array
          //they are all bigger then the ones already in the merged array
          while (izp < dvzp)
            sp[isp++] = zp[izp++];

          //do the same for the sorted array
          while (iup < dvup)
            sp[isp++] = up[iup++];

          // dfdfgdgd
          up = sp;
          dvup = isp;
        }
        else
        {
          up = zp;
          dvup = dvzp;
        }

    }

    return up;
  }

Could i improve the performance even more? So that it would be run even faster?

[Array.Sort](http://msdn.microsoft.com/en-us/library/system.array.sort.aspx)? — crashmstr, Jun 25 '14 at 16:55
If you don't want to use Array.Sort, search for [sort algorithm](http://en.wikipedia.org/wiki/Sorting_algorithm) and implement one of those. — crashmstr, Jun 25 '14 at 16:57
Use your favourite search engine and look for an implementation of the sort algorithm of your likes — Steve, Jun 25 '14 at 16:57
Is there a whole problem you're trying to solve? It's kind of confusing to say "I want to sort this using only the system library... oh yea but not any of THESE system libraries." — cost, Jun 25 '14 at 16:58
I promise you Wikipedia is not relying on the .Net implementation of `Array.Sort` to document the concepts of sort algorithms. — Preston Guillot, Jun 25 '14 at 16:59
Man, you are VERY lazy, at least search in stackoverflow, this is the first hit I got: http://stackoverflow.com/questions/14768010/simple-bubble-sort-c-sharp — Gusman, Jun 25 '14 at 16:59
@tastro no, that link talks about algorithms. i.e. how to implement a sort. How else would you do this without using the built in functionality? Also, why would you want to do this without using the built in functionality? — crashmstr, Jun 25 '14 at 16:59
You'll be much more likely to receive help if you've already attempted it and failed and show you've made the effort. Too many people on here searching for someone to do the work for them. — Dom, Jun 25 '14 at 16:59
Since you're saying it's too slow, you should look up Quicksort, Merge sort, or Heap Sort. — user1071777, Jun 25 '14 at 17:04
Strand sort has an average performance of n^2, it is *expected* to be slow for most inputs. — Preston Guillot, Jun 25 '14 at 17:07
Ok, NOW it has the true structure of a question, now I can remove that -1 with peace of mind. — Gusman, Jun 25 '14 at 17:07
In the worst case Strand Sort is O(n^2). Your n is 200000, so you'd have to do on the order of 40,000,000,000 comparisons (which is quite alot). If you used an n log n algorithm instead, you'd need only ~1,000,000 comparisons — user1071777, Jun 25 '14 at 17:10
Wikipedia's article on Strand Sort even gives you pseudocode: http://en.wikipedia.org/wiki/Strand_sort — user1071777, Jun 25 '14 at 17:11
What makes you think that your code is "slower than O(n^2)?" What do you think O(n^2) means? — Jim Mischel, Jun 25 '14 at 17:14
@tastro I have my doubts that you have a complete understanding of big O time complexity, your code seems to be more complicated than really necessary, but sure looks like it's in O(n^2). Check the Wikipedia article that user1071777 linked, it describes the algorithm and provides both pseudo-code and example code. — Preston Guillot, Jun 25 '14 at 17:17
It sounds like your grader was telling you to use a different sort algorithm entirely. As in, one with a better average case run time. — Preston Guillot, Jun 25 '14 at 17:22
@tastro, I'm preparing an answer, but you added "Without using System.Collections.Generic", that is nearly impossible, this algorithm needs the use of list's to behave as they should, are you sure about that? System.Collections.Generic is not a library but a namespace... — Gusman, Jun 25 '14 at 17:59
So, can you implement your own linked list or it is disallowed too? — Gusman, Jun 25 '14 at 18:06

Gusman · Accepted Answer · 2014-06-25T20:25:22.793

Ok, I got bored and wanted to help (also, a question with that quantity of comments cannot be left without an answer :D), so took the Wikipedia PHP implementation and converted it to C#, but after a bit the user added he cannot use generics...

So, I'm posting a full implementation, one with generics and another with it's own LinkedList, it's a bit longer but it works (took the Wikipedia example, followed step by step and it behaves exactly as the example table) and it's also commented so it's easy to understand (the linked list code is not commented).

And here it comes!

public class StrandSort
{
    public static int[] SortWithGenerics(int[] Values)
    {

        List<int> Original = new List<int>();
        List<int> Result = new List<int>();
        List<int> Sublist = new List<int>();

        Original.AddRange(Values);

        //While we still have numbers to sort
        while (Original.Count > 0)
        {

            //Clear sublist and take first available number from original to the new sublist
            Sublist.Clear();
            Sublist.Add(Original[0]);
            Original.RemoveAt(0);

            //Iterate through original numbers
            for (int x = 0; x < Original.Count; x++)
            {
                //If the number is bigger than the last item in the sublist
                if (Original[x] > Sublist[Sublist.Count - 1])
                {
                    //Add it to the sublist and remove it from original
                    Sublist.Add(Original[x]);
                    Original.RemoveAt(x);
                    //Roll back one position to compensate the removed item
                    x--;

                }

            }

            //If this is the first sublist
            if (Result.Count == 0)
                Result.AddRange(Sublist); //Add all the numbers to the result
            else
            {
                //Iterate through the sublist
                for (int x = 0; x < Sublist.Count; x++)
                {

                    bool inserted = false;

                    //Iterate through the current result
                    for (int y = 0; y < Result.Count; y++)
                    {
                        //Is the sublist number lower than the current item from result?
                        if (Sublist[x] < Result[y])
                        {
                            //Yes, insert it at the current Result position
                            Result.Insert(y, Sublist[x]);
                            inserted = true;
                            break;

                        }

                    }

                    //Did we inserted the item because found it was lower than one of the result's number?
                    if (!inserted)
                        Result.Add(Sublist[x]);//No, we add it to the end of the results

                }

            }

        }

        //Return the results
        return Result.ToArray();
    }

    public static int[] SortWithoutGenerics(int[] Values)
    {

        IntLinkedList Original = new IntLinkedList();
        IntLinkedList Result = new IntLinkedList();
        IntLinkedList Sublist = new IntLinkedList();

        Original.AddRange(Values);

        //While we still have numbers to sort
        while (Original.Count > 0)
        {

            //Clear sublist and take first available number from original to the new sublist
            Sublist.Clear();
            Sublist.Add(Original.FirstItem.Value);
            Original.Remove(Original.FirstItem);

            IntLinkedItem currentOriginalItem = Original.FirstItem;

            //Iterate through original numbers
            while (currentOriginalItem != null)
            {
                //If the number is bigger than the last item in the sublist
                if (currentOriginalItem.Value > Sublist.LastItem.Value)
                {
                    //Add it to the sublist and remove it from original
                    Sublist.Add(currentOriginalItem.Value);
                    //Store the next item
                    IntLinkedItem nextItem = currentOriginalItem.NextItem;
                    //Remove current item from original
                    Original.Remove(currentOriginalItem);
                    //Set next item as current item
                    currentOriginalItem = nextItem;


                }
                else
                    currentOriginalItem = currentOriginalItem.NextItem;

            }

            //If this is the first sublist
            if (Result.Count == 0)
                Result.AddRange(Sublist); //Add all the numbers to the result
            else
            {

                IntLinkedItem currentSublistItem = Sublist.FirstItem;

                //Iterate through the sublist
                while (currentSublistItem != null)
                {

                    bool inserted = false;

                    IntLinkedItem currentResultItem = Result.FirstItem;

                    //Iterate through the current result
                    while (currentResultItem != null)
                    {
                        //Is the sublist number lower than the current item from result?
                        if (currentSublistItem.Value < currentResultItem.Value)
                        {
                            //Yes, insert it at the current Result position
                            Result.InsertBefore(currentResultItem, currentSublistItem.Value);
                            inserted = true;
                            break;

                        }

                        currentResultItem = currentResultItem.NextItem;

                    }

                    //Did we inserted the item because found it was lower than one of the result's number?
                    if (!inserted)
                        Result.Add(currentSublistItem.Value);//No, we add it to the end of the results

                    currentSublistItem = currentSublistItem.NextItem;

                }

            }

        }

        //Return the results
        return Result.ToArray();
    }

    public class IntLinkedList
    {

        public int count = 0;
        IntLinkedItem firstItem = null;
        IntLinkedItem lastItem = null;

        public IntLinkedItem FirstItem { get { return firstItem; } }
        public IntLinkedItem LastItem { get { return lastItem; } }
        public int Count { get { return count; } }

        public void Add(int Value)
        {

            if (firstItem == null)
                firstItem = lastItem = new IntLinkedItem { Value = Value };
            else
            { 

                IntLinkedItem item = new IntLinkedItem{  PreviousItem = lastItem, Value = Value };
                lastItem.NextItem = item;
                lastItem = item;

            }

            count++;

        }

        public void AddRange(int[] Values)
        {

            for (int buc = 0; buc < Values.Length; buc++)
                Add(Values[buc]);

        }

        public void AddRange(IntLinkedList Values)
        {

            IntLinkedItem item = Values.firstItem;

            while (item != null)
            {

                Add(item.Value);
                item = item.NextItem;

            }

        }

        public void Remove(IntLinkedItem Item)
        {
            if (Item == firstItem)
                firstItem = Item.NextItem;

            if (Item == lastItem)
                lastItem = Item.PreviousItem;

            if(Item.PreviousItem != null)
                Item.PreviousItem.NextItem = Item.NextItem;

            if (Item.NextItem != null)
                Item.NextItem.PreviousItem = Item.PreviousItem;

            count--;

        }

        public void InsertBefore(IntLinkedItem Item, int Value)
        {

            IntLinkedItem newItem = new IntLinkedItem { PreviousItem = Item.PreviousItem, NextItem = Item, Value = Value };

            if (Item.PreviousItem != null)
                Item.PreviousItem.NextItem = newItem;

            Item.PreviousItem = newItem;

            if (Item == firstItem)
                firstItem = newItem;

            count++;
        }

        public void Clear()
        {

            count = 0;
            firstItem = lastItem = null;

        }

        public int[] ToArray()
        {

            int[] results = new int[Count];
            int pos = 0;

            IntLinkedItem item = firstItem;

            while (item != null)
            {
                results[pos++] = item.Value;
                item = item.NextItem;
            }

            return results;

        }
    }

    public class IntLinkedItem
    { 

        public int Value;
        internal IntLinkedItem PreviousItem;
        internal IntLinkedItem NextItem;

    }
}

EDIT: It's really not a linked list but a double linked list ;)

EDIT: Corrected a missing "else" in non-generic implementation

EDIT: I was really bored and created a refactored and corrected version of the user's code with commented changes so he can learn from it ;)

Note to user: I recommend you to use more meaningful names for variables, it is a lot easier to understand the code when you read it.

    static public int[] SortCorrectedUserCode(int[] Source)
    {
        int[] Sublist,
            Results;
        int ItemsLeft,
            SublistPos,
            ResultPos;//new variable to store current pos in results
        //n; n was useless

        Sublist = new int[Source.Length];
        Results = new int[Source.Length];
        //Avoid resets just using an integer to track array lengths
        //Reset(ref Sublist);
        //Reset(ref Results);
        ItemsLeft = Source.Length;

        ResultPos = 0;

        while (ItemsLeft != 0)
        {
            //n = int.MinValue;
            SublistPos = 0;

            for (int currentSourcePos = 0; currentSourcePos < Source.Length; currentSourcePos++)
            {
                if (Source[currentSourcePos] != int.MaxValue)
                {
                    //Added special treatment for first item in sublist (copy it yes or yes ;D)
                    if (SublistPos == 0 || Source[currentSourcePos] > Sublist[SublistPos])
                    {

                        Sublist[SublistPos] = Source[currentSourcePos];
                        //n = Source[currentSourcePos]; useless
                        Source[currentSourcePos] = int.MaxValue;
                        ItemsLeft--;
                        SublistPos++;
                    }
                }
            }

            //int p3p, zs;

            //pn is never true...
            //bool pn = false;

            //Sublist was being iterated for all it's length, not only for the current items
            //for (int currentSublistPos = 0; currentSublistPos < Sublist.Length; currentSublistPos++)

            for (int currentSublistPos = 0; currentSublistPos < SublistPos; currentSublistPos++)
            {
                //p3p = int.MinValue;

                bool inserted = false;

                //Results was being iterated for all it's length, not only for current items
                //for (int currentResultPos = 0; currentResultPos < Results.Length; currentResultPos++)

                for (int currentResultPos = 0; currentResultPos < ResultPos; currentResultPos++)
                {

                    //This part was never used...
                    //if (pn)
                    //{
                    //    zs = Results[currentResultPos];
                    //    Results[currentResultPos] = p3p;
                    //    p3p = zs;
                    //}
                    //else
                    //{

                    //This IF was wrong, when the code entered this piece of code it started
                    //for subsequent iterations in the current loop to copy data from sublist to list, which is not correct ... I think, not sure 
                    //because it's really confusing
                    //if (Sublist[currentSublistPos] >= p3p && Sublist[currentSublistPos] <= Results[currentResultPos])
                    //{
                    //p3p = Results[currentResultPos];
                    //Results[currentResultPos] = Sublist[currentSublistPos];
                    //}
                    //}

                    //New code, if the item at sublist is lower than the one at results then insert item in current position
                    if (Sublist[currentSublistPos] < Results[currentResultPos])
                    {

                        InsertInArray(currentResultPos, Sublist[currentSublistPos], Results);
                        inserted = true;
                        break;

                    }
                }
                //Did we inserted the item?
                if (!inserted)
                    Results[ResultPos] = Sublist[currentSublistPos]; //If no then just add it to the end of the results

                ResultPos++;
            }

            //Reset(ref Sublist);
        }

        return Results;
    }

    //Helper function to insert a value in an array and displace values to the right
    static void InsertInArray(int Index, int Value, int[] Target)
    {
        //Create temp array of right items
        int[] tempArray = new int[(Target.Length - Index) - 1];

        //Copy items to temp array
        Array.Copy(Target, Index, tempArray, 0, tempArray.Length);

        //Set value at index
        Target[Index] = Value;

        //Copy values from temp array to correct position
        Array.Copy(tempArray, 0, Target, Index + 1, tempArray.Length);

    }

Also did some benchmarking on the functions (because the user was concerned about speed) and those are the results running on my machoine in debug mode (for 5000 items, did not have patience to test longer arrays because old code was very slow):

Generics: 36ms
Non-generics: 21ms
User original code 23248ms
Corrected code: 34ms

score 2 · Answer 2 · answered Jun 25 '14 at 18:40

Probably most importantly, the Wikipedia article says about strand sort:

Using another data structure, such as an array, would greatly increase the running time and complexity of the algorithm due to lengthy insertions and deletions.

A quick glance at your code indicates that it might indeed be O(n^3) because you're clearing that p2 array every time through the main while loop.

I must be missing something, because I don't see how your algorithm can ever terminate. You have this at the beginning of your main loop:

while (p1s1 != 0)
{
    n = int.MinValue;
    p2s1 = 0;

    for (int i8 = 0; i8 < p1.Length; i8++)
    {
        if (p1[i8] != int.MaxValue)
        {
            if (p1[i8] >= n)
            {
                p2[p2s1] = p1[i8];
                n = p1[i8];
                p1[i8] = int.MaxValue;
                p1s1--;
                p2s1++;
            }
        }
    }

Let's look at those two if statements:

        if (p1[i8] != int.MaxValue)
        {
            if (p1[i8] >= n)

You set n equal to int.MaxValue at the beginning of the loop. Your second conditional here is checking to see if p1[i8] is greater than or equal to n. But it can't be greater than int.MaxValue, and it can't be equal to int.MaxValue because if it were than it wouldn't have made it past the first conditional.

I don't see anywhere else that n is assigned a value. And since the only place that p1s1 ever gets changed is if that second conditional evaluates to true (and we know that it can't), the while loop will go forever because p1s1 never equals 0.

How to sort (using strand sort algorithm) an array of integers? C#

2 Answers2