{"id":15614,"date":"2022-10-12T07:59:50","date_gmt":"2022-10-12T02:29:50","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-how-to-sort-using-strand-sort-algorithm-an-array-of-integers-c-closed\/"},"modified":"2022-10-12T07:59:50","modified_gmt":"2022-10-12T02:29:50","slug":"solved-how-to-sort-using-strand-sort-algorithm-an-array-of-integers-c-closed","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-how-to-sort-using-strand-sort-algorithm-an-array-of-integers-c-closed\/","title":{"rendered":"[Solved] How to sort (using strand sort algorithm) an array of integers? C# [closed]"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\n
\n
<\/div>\n
\n
\n

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<\/a> and converted it to C#, but after a bit the user added he cannot use generics…<\/p>\n

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).<\/p>\n

And here it comes!<\/p>\n

public class StrandSort\n{\n    public static int[] SortWithGenerics(int[] Values)\n    {\n\n        List<int> Original = new List<int>();\n        List<int> Result = new List<int>();\n        List<int> Sublist = new List<int>();\n\n        Original.AddRange(Values);\n\n        \/\/While we still have numbers to sort\n        while (Original.Count > 0)\n        {\n\n            \/\/Clear sublist and take first available number from original to the new sublist\n            Sublist.Clear();\n            Sublist.Add(Original[0]);\n            Original.RemoveAt(0);\n\n            \/\/Iterate through original numbers\n            for (int x = 0; x < Original.Count; x++)\n            {\n                \/\/If the number is bigger than the last item in the sublist\n                if (Original[x] > Sublist[Sublist.Count - 1])\n                {\n                    \/\/Add it to the sublist and remove it from original\n                    Sublist.Add(Original[x]);\n                    Original.RemoveAt(x);\n                    \/\/Roll back one position to compensate the removed item\n                    x--;\n\n                }\n\n            }\n\n            \/\/If this is the first sublist\n            if (Result.Count == 0)\n                Result.AddRange(Sublist); \/\/Add all the numbers to the result\n            else\n            {\n                \/\/Iterate through the sublist\n                for (int x = 0; x < Sublist.Count; x++)\n                {\n\n                    bool inserted = false;\n\n                    \/\/Iterate through the current result\n                    for (int y = 0; y < Result.Count; y++)\n                    {\n                        \/\/Is the sublist number lower than the current item from result?\n                        if (Sublist[x] < Result[y])\n                        {\n                            \/\/Yes, insert it at the current Result position\n                            Result.Insert(y, Sublist[x]);\n                            inserted = true;\n                            break;\n\n                        }\n\n                    }\n\n                    \/\/Did we inserted the item because found it was lower than one of the result's number?\n                    if (!inserted)\n                        Result.Add(Sublist[x]);\/\/No, we add it to the end of the results\n\n                }\n\n            }\n\n        }\n\n        \/\/Return the results\n        return Result.ToArray();\n    }\n\n    public static int[] SortWithoutGenerics(int[] Values)\n    {\n\n        IntLinkedList Original = new IntLinkedList();\n        IntLinkedList Result = new IntLinkedList();\n        IntLinkedList Sublist = new IntLinkedList();\n\n        Original.AddRange(Values);\n\n        \/\/While we still have numbers to sort\n        while (Original.Count > 0)\n        {\n\n            \/\/Clear sublist and take first available number from original to the new sublist\n            Sublist.Clear();\n            Sublist.Add(Original.FirstItem.Value);\n            Original.Remove(Original.FirstItem);\n\n            IntLinkedItem currentOriginalItem = Original.FirstItem;\n\n            \/\/Iterate through original numbers\n            while (currentOriginalItem != null)\n            {\n                \/\/If the number is bigger than the last item in the sublist\n                if (currentOriginalItem.Value > Sublist.LastItem.Value)\n                {\n                    \/\/Add it to the sublist and remove it from original\n                    Sublist.Add(currentOriginalItem.Value);\n                    \/\/Store the next item\n                    IntLinkedItem nextItem = currentOriginalItem.NextItem;\n                    \/\/Remove current item from original\n                    Original.Remove(currentOriginalItem);\n                    \/\/Set next item as current item\n                    currentOriginalItem = nextItem;\n\n\n                }\n                else\n                    currentOriginalItem = currentOriginalItem.NextItem;\n\n            }\n\n            \/\/If this is the first sublist\n            if (Result.Count == 0)\n                Result.AddRange(Sublist); \/\/Add all the numbers to the result\n            else\n            {\n\n                IntLinkedItem currentSublistItem = Sublist.FirstItem;\n\n                \/\/Iterate through the sublist\n                while (currentSublistItem != null)\n                {\n\n                    bool inserted = false;\n\n                    IntLinkedItem currentResultItem = Result.FirstItem;\n\n                    \/\/Iterate through the current result\n                    while (currentResultItem != null)\n                    {\n                        \/\/Is the sublist number lower than the current item from result?\n                        if (currentSublistItem.Value < currentResultItem.Value)\n                        {\n                            \/\/Yes, insert it at the current Result position\n                            Result.InsertBefore(currentResultItem, currentSublistItem.Value);\n                            inserted = true;\n                            break;\n\n                        }\n\n                        currentResultItem = currentResultItem.NextItem;\n\n                    }\n\n                    \/\/Did we inserted the item because found it was lower than one of the result's number?\n                    if (!inserted)\n                        Result.Add(currentSublistItem.Value);\/\/No, we add it to the end of the results\n\n                    currentSublistItem = currentSublistItem.NextItem;\n\n                }\n\n            }\n\n        }\n\n        \/\/Return the results\n        return Result.ToArray();\n    }\n\n    public class IntLinkedList\n    {\n\n        public int count = 0;\n        IntLinkedItem firstItem = null;\n        IntLinkedItem lastItem = null;\n\n        public IntLinkedItem FirstItem { get { return firstItem; } }\n        public IntLinkedItem LastItem { get { return lastItem; } }\n        public int Count { get { return count; } }\n\n        public void Add(int Value)\n        {\n\n            if (firstItem == null)\n                firstItem = lastItem = new IntLinkedItem { Value = Value };\n            else\n            { \n\n                IntLinkedItem item = new IntLinkedItem{  PreviousItem = lastItem, Value = Value };\n                lastItem.NextItem = item;\n                lastItem = item;\n\n            }\n\n            count++;\n\n        }\n\n        public void AddRange(int[] Values)\n        {\n\n            for (int buc = 0; buc < Values.Length; buc++)\n                Add(Values[buc]);\n\n        }\n\n        public void AddRange(IntLinkedList Values)\n        {\n\n            IntLinkedItem item = Values.firstItem;\n\n            while (item != null)\n            {\n\n                Add(item.Value);\n                item = item.NextItem;\n\n            }\n\n        }\n\n        public void Remove(IntLinkedItem Item)\n        {\n            if (Item == firstItem)\n                firstItem = Item.NextItem;\n\n            if (Item == lastItem)\n                lastItem = Item.PreviousItem;\n\n            if(Item.PreviousItem != null)\n                Item.PreviousItem.NextItem = Item.NextItem;\n\n            if (Item.NextItem != null)\n                Item.NextItem.PreviousItem = Item.PreviousItem;\n\n            count--;\n\n        }\n\n        public void InsertBefore(IntLinkedItem Item, int Value)\n        {\n\n            IntLinkedItem newItem = new IntLinkedItem { PreviousItem = Item.PreviousItem, NextItem = Item, Value = Value };\n\n            if (Item.PreviousItem != null)\n                Item.PreviousItem.NextItem = newItem;\n\n            Item.PreviousItem = newItem;\n\n            if (Item == firstItem)\n                firstItem = newItem;\n\n            count++;\n        }\n\n        public void Clear()\n        {\n\n            count = 0;\n            firstItem = lastItem = null;\n\n        }\n\n        public int[] ToArray()\n        {\n\n            int[] results = new int[Count];\n            int pos = 0;\n\n            IntLinkedItem item = firstItem;\n\n            while (item != null)\n            {\n                results[pos++] = item.Value;\n                item = item.NextItem;\n            }\n\n            return results;\n\n        }\n    }\n\n    public class IntLinkedItem\n    { \n\n        public int Value;\n        internal IntLinkedItem PreviousItem;\n        internal IntLinkedItem NextItem;\n\n    }\n}\n<\/code><\/pre>\n
EDIT<\/strong>: It’s really not a linked list but a double linked list \ud83d\ude09<\/p>\n
EDIT<\/strong>: Corrected a missing “else” in non-generic implementation<\/p>\n
EDIT<\/strong>: I was really<\/em> bored and created a refactored and corrected version of the user’s code with commented changes so he can learn from it \ud83d\ude09<\/p>\n
Note to user<\/strong>: I recommend you to use more meaningful names for variables, it is a lot easier to understand the code when you read it.<\/p>\n
    static public int[] SortCorrectedUserCode(int[] Source)\n    {\n        int[] Sublist,\n            Results;\n        int ItemsLeft,\n            SublistPos,\n            ResultPos;\/\/new variable to store current pos in results\n        \/\/n; n was useless\n\n        Sublist = new int[Source.Length];\n        Results = new int[Source.Length];\n        \/\/Avoid resets just using an integer to track array lengths\n        \/\/Reset(ref Sublist);\n        \/\/Reset(ref Results);\n        ItemsLeft = Source.Length;\n\n        ResultPos = 0;\n\n        while (ItemsLeft != 0)\n        {\n            \/\/n = int.MinValue;\n            SublistPos = 0;\n\n            for (int currentSourcePos = 0; currentSourcePos < Source.Length; currentSourcePos++)\n            {\n                if (Source[currentSourcePos] != int.MaxValue)\n                {\n                    \/\/Added special treatment for first item in sublist (copy it yes or yes ;D)\n                    if (SublistPos == 0 || Source[currentSourcePos] > Sublist[SublistPos])\n                    {\n\n                        Sublist[SublistPos] = Source[currentSourcePos];\n                        \/\/n = Source[currentSourcePos]; useless\n                        Source[currentSourcePos] = int.MaxValue;\n                        ItemsLeft--;\n                        SublistPos++;\n                    }\n                }\n            }\n\n            \/\/int p3p, zs;\n\n            \/\/pn is never true...\n            \/\/bool pn = false;\n\n            \/\/Sublist was being iterated for all it's length, not only for the current items\n            \/\/for (int currentSublistPos = 0; currentSublistPos < Sublist.Length; currentSublistPos++)\n\n            for (int currentSublistPos = 0; currentSublistPos < SublistPos; currentSublistPos++)\n            {\n                \/\/p3p = int.MinValue;\n\n                bool inserted = false;\n\n                \/\/Results was being iterated for all it's length, not only for current items\n                \/\/for (int currentResultPos = 0; currentResultPos < Results.Length; currentResultPos++)\n\n                for (int currentResultPos = 0; currentResultPos < ResultPos; currentResultPos++)\n                {\n\n                    \/\/This part was never used...\n                    \/\/if (pn)\n                    \/\/{\n                    \/\/    zs = Results[currentResultPos];\n                    \/\/    Results[currentResultPos] = p3p;\n                    \/\/    p3p = zs;\n                    \/\/}\n                    \/\/else\n                    \/\/{\n\n                    \/\/This IF was wrong, when the code entered this piece of code it started\n                    \/\/for subsequent iterations in the current loop to copy data from sublist to list, which is not correct ... I think, not sure \n                    \/\/because it's really confusing\n                    \/\/if (Sublist[currentSublistPos] >= p3p && Sublist[currentSublistPos] <= Results[currentResultPos])\n                    \/\/{\n                    \/\/p3p = Results[currentResultPos];\n                    \/\/Results[currentResultPos] = Sublist[currentSublistPos];\n                    \/\/}\n                    \/\/}\n\n                    \/\/New code, if the item at sublist is lower than the one at results then insert item in current position\n                    if (Sublist[currentSublistPos] < Results[currentResultPos])\n                    {\n\n                        InsertInArray(currentResultPos, Sublist[currentSublistPos], Results);\n                        inserted = true;\n                        break;\n\n                    }\n                }\n                \/\/Did we inserted the item?\n                if (!inserted)\n                    Results[ResultPos] = Sublist[currentSublistPos]; \/\/If no then just add it to the end of the results\n\n                ResultPos++;\n            }\n\n            \/\/Reset(ref Sublist);\n        }\n\n        return Results;\n    }\n\n    \/\/Helper function to insert a value in an array and displace values to the right\n    static void InsertInArray(int Index, int Value, int[] Target)\n    {\n        \/\/Create temp array of right items\n        int[] tempArray = new int[(Target.Length - Index) - 1];\n\n        \/\/Copy items to temp array\n        Array.Copy(Target, Index, tempArray, 0, tempArray.Length);\n\n        \/\/Set value at index\n        Target[Index] = Value;\n\n        \/\/Copy values from temp array to correct position\n        Array.Copy(tempArray, 0, Target, Index + 1, tempArray.Length);\n\n    }\n<\/code><\/pre>\n
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):<\/p>\n