Sorting algorithms/Strand sort: Difference between revisions

Content added Content deleted

Inline

@@ Line 231: / Line 231: @@
 =={{header|D}}==
+=== Using doubly linked lists ===
 <lang d>import std.stdio, std.container;
@@ Line 253: / Line 255: @@
     while (!list.empty) {
-    	leftover.clear();
+        leftover.clear();
         sorted.clear();
         sorted.insertBack(list.front);
@@ Line 261: / Line 263: @@
                 sorted.insertBack(item);
             else
-	    	leftover.insertBack(item);
+                leftover.insertBack(item);
         }
         result = merge(sorted, result);
-	list = leftover;
+        list = leftover;
     }
@@ Line 273: / Line 275: @@
     auto lst = DList!int([-2,0,-2,5,5,3,-1,-3,5,5,0,2,-4,4,2]);
     foreach (e; strandSort(lst))
+        write(e, " ");
+}</lang>
+{{out}}
+<pre>-4 -3 -2 -2 -1 0 0 2 2 3 4 5 5 5 5 </pre>
+=== Faster version using slices ===
+<lang d>T[] strandSort(T)(T[] list) {
+    T[] merge(T[] left, T[] right) {
+        T[] res;
+        while (!left.empty && !right.empty) {
+            if (left.front <= right.front) {
+                res ~= left.front;
+                left = left[1 .. $];
+            } else {
+                res ~= right.front;
+                right = right[1 .. $];
+            }
+        }
+        return res ~ left ~ right;
+    }
+    T[] result, sorted, leftover;
+    while (!list.empty) {
+        leftover = [];
+        sorted = [list.front];
+        list = list[1 .. $];
+        foreach (item; list) {
+            if (sorted.back <= item) {
+                sorted ~= item;
+            } else {
+                leftover ~= item;
+            }
+        }
+        result = merge(sorted, result);
+        list = leftover;
+    }
+    return result;
+}
+void main() {
+    auto arr = [-2,0,-2,5,5,3,-1,-3,5,5,0,2,-4,4,2];
+    foreach (e; strandSort(arr))
         write(e, " ");
 }</lang>