# Stalin-Sort using Divide&Conquer

Nov 4th, 2018 (edited)
626
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. package stalin;
2.
3. import java.util.ArrayList;
4. import java.util.Arrays;
6. import java.util.List;
7.
8. /**
9.  * Stalin-Sort is an impractical algorithm for bringing data structures into order.
10.  *
11.  * <p>
12.  * Idea by: <code>@mathew@mastodon.social</code>.
13.  *
14.  * <p>
15.  * <img src="https://i.redd.it/x9triplll1v11.jpg" width=360 height=198 alt="I
16.  * came up with a single pass O(n) sort algorithm I call Stalin-Sort. U iterate
17.  * down the list of elements checking if they are in order. Any element which is
18.  * out of order is eliminated. At the end u have a sorted list"/>
19.  *
20.  * <p>
21.  * However, this does not specify how exactly the elements are chosen. For
22.  * example for the input <code>[42,1,2,3,4,5,6]</code> you just get
23.  * <code>[42]</code> instead of <code>[1,2,3,4,5,6]</code>. You can get a better
24.  * result if you use <i>divide and conquer</i>. And that is something Stalin
25.  * would do, don't you think? So this is the recursive solution, implemented in
26.  * Java. It tries all possible results, which is not a single pass and therefore
27.  * defeats the purpose of having a fast algorithm. And none of these are
28.  * in-place, so a new data structure has to be created. That's why I added an
30.  * <p>
31.  * There are 5 public static methods:
32.  * <ul>
33.  * <li>{@link #sort(int[])}: sort integers in <code>O(n)</code>
34.  * <li>{@link #sortDC(int[])} sort integers using <i>divide and conquer</i>
35.  * <li>{@link #sort(List)}: sort any List in <code>O(n)</code>
36.  * <li>{@link #sortDC(List)} sort any List using <i>divide and conquer</i>
38.  * </ul>
39.  *
40.  * @author Claude Martin
41.  *
42.  */
43. public class StalinSort {
44.   /**
45.    * Naive implementation of Stalin-Sort for integers. It works but it does not
46.    * return the longest possible array. It's not exactly in <code>O(n)</code>
47.    * because the resulting array has to be created.
48.    */
49.   public static int[] sort(final int[] integers) {
50.     var previous = Integer.MIN_VALUE;
51.     final var accepted = new boolean[integers.length];
52.     var newLen = 0;
53.     for (var i = 0; i < integers.length; i++) {
54.       final var value = integers[i];
55.       if (previous < value) {
56.         final var next = i + 1 < integers.length ? integers[i + 1] : Integer.MAX_VALUE;
57.         if (next > previous && next < value) {
58.           // Eliminate this one and keep the next one instead.
59.         } else {
60.           accepted[i] = true;
61.           newLen++;
62.           previous = value;
63.         }
64.       } // else: Eliminate (not accepted)
65.     }
66.     final var result = new int[newLen];
67.     for (int i = 0, j = 0; i < accepted.length; i++) {
68.       if (accepted[i])
69.         result[j++] = integers[i];
70.     }
71.     return result;
72.   }
73.
74.   /**
75.    * Improved implementation of Stalin-Sort for integers to find the best
76.    * solution. Uses <i>divide and conquer</i> to solve this problem. This is not
77.    * in <code>O(n)</code>. More like <code>O(n log<sub>n</sub>)</code>.
78.    */
79.   public static int[] sortDC(final int[] input) {
80.     final boolean[] accepted = new boolean[input.length];
81.     final int newLen = _sortDC(input, 0, accepted, 0, Integer.MIN_VALUE);
82.     final var result = new int[newLen];
83.     for (int i = 0, j = 0; i < input.length; i++) {
84.       if (accepted[i])
85.         result[j++] = input[i];
86.     }
87.     return result;
88.   }
89.
90.   /**
91.    * Recursive Stalin-Sort with <i>divide and conquer</i>.
92.    *
93.    * @param input
94.    *          the original input (never changes)
95.    * @param position
96.    *          the position of the value to be accepted or eliminated
97.    * @param accepted
98.    *          bit set of already accepted values, which will be updated.
99.    * @return the length of the result. the longer one always wins.
100.    */
101.   private static int _sortDC(final int[] input, final int position, final boolean[] accepted, final int count,
102.       final int lastAccepted) {
103.     final var len = input.length;
104.     // System.out.println(String.format("%s = %d", Arrays.toString(accepted),
105.     // count));
106.     if (len == position)
107.       return count;
108.
109.     if (position > 0 && input[position] < lastAccepted) {
110.       // input[position] has to be eliminated.
111.       return _sortDC(input, 1 + position, accepted, count, lastAccepted);
112.     }
113.     // First try: eliminate the value
114.     final var accepted1 = Arrays.copyOf(accepted, len);
115.     // accepted1[position] = false;
116.     final int result1 = _sortDC(input, 1 + position, accepted1, count, lastAccepted);
117.     // Second try: accept the value
118.     final var accepted2 = Arrays.copyOf(accepted, len);
119.     accepted2[position] = true;
120.     final int result2 = _sortDC(input, 1 + position, accepted2, 1 + count, input[position]);
121.
122.     // Which one is better?
123.     if (result2 > result1) {
124.       System.arraycopy(accepted2, 0, accepted, 0, len);
125.       return result2;
126.     } else {
127.       System.arraycopy(accepted1, 0, accepted, 0, len);
128.       return result1;
129.     }
130.   }
131.
132.   /**
133.    * Naive implementation of Stalin-Sort. This always creates a new list (not
134.    * in-place!). It works but it does not return the longest possible list. Works
135.    * great with linked lists. But no support for <code>null</code>.
136.    */
137.   public static <T extends Comparable<? super T>> List<T> sort(final List<T> input) {
138.     final int size = input.size();
139.     if (size < 2)
140.       return new ArrayList<>(input);
141.     T previous = input.get(0);
142.     final var result = new ArrayList<T>(size);
144.     for (var i = 1; i < size; i++) {
145.       final var value = input.get(i);
146.       if (previous.compareTo(value) < 0) {
148.       }
149.     }
150.     return result;
151.   }
152.
153.   /**
154.    * Improved implementation of Stalin-Sort to find the best solution. Uses
155.    * <i>divide and conquer</i> to solve this problem. This is not in
156.    * <code>O(n)</code>. More like <code>O(n log<sub>n</sub>)</code>.
157.    */
158.   public static <T extends Comparable<? super T>> List<T> sortDC(final List<T> input) {
159.     final boolean[] accepted = new boolean[input.size()];
160.     final int newLen = _sortDC(input, 0, accepted, 0, null);
161.     final var result = new ArrayList<T>(newLen);
162.     for (int i = 0; i < input.size(); i++) {
163.       if (accepted[i])
165.     }
166.     return result;
167.   }
168.
169.   /**
170.    * Recursive Stalin-Sort with <i>divide and conquer</i>. Does not support
171.    * <code>null</code>.
172.    *
173.    * @param input
174.    *          the original input (never changes)
175.    * @param position
176.    *          the position of the value to be accepted or eliminated
177.    * @param accepted
178.    *          bit set of already accepted values, which will be updated.
179.    * @return the length of the result. the longer one always wins.
180.    */
181.   private static <T extends Comparable<? super T>> int _sortDC(final List<T> input, final int position,
182.       final boolean[] accepted, final int count, final T lastAccepted) {
183.     final var len = input.size();
184.     if (len == position)
185.       return count;
186.     if (position > 0 && lastAccepted != null && input.get(position).compareTo(lastAccepted) < 0) {
187.       // input[position] has to be eliminated.
188.       return _sortDC(input, 1 + position, accepted, count, lastAccepted);
189.     }
190.     // First try: eliminate the value
191.     final var accepted1 = Arrays.copyOf(accepted, len);
192.     // accepted1[position] = false;
193.     final int result1 = _sortDC(input, 1 + position, accepted1, count, lastAccepted);
194.     // Second try: accept the value
195.     final var accepted2 = Arrays.copyOf(accepted, len);
196.     accepted2[position] = true;
197.     final int result2 = _sortDC(input, 1 + position, accepted2, 1 + count, input.get(position));
198.
199.     // Which one is better?
200.     if (result2 > result1) {
201.       System.arraycopy(accepted2, position, accepted, position, len - position);
202.       return result2;
203.     } else {
204.       System.arraycopy(accepted1, position, accepted, position, len - position);
205.       return result1;
206.     }
207.   }
208.
209.   /**
210.    * This is the Stalin-Sort as it should be. Use this for best performance. Does
211.    * not support <code>null</code>.
212.    */
213.   public static <T extends Comparable<? super T>> void inplace(LinkedList<T> input) {
214.     final var iterator = input.iterator();
215.     if (!iterator.hasNext())
216.       return;
217.     var previous = iterator.next();
218.     while (iterator.hasNext()) {
219.       var value = iterator.next();
220.       if (value.compareTo(previous) < 0)
221.         iterator.remove();
222.       else
223.         previous = value;
224.     }
225.   }
226.
227.   /**
228.    * Entry point to show that and how it works.
229.    *
230.    * @param args
231.    *          you can give a list of strings to be sorted (optional)
232.    */
233.   public static void main(final String[] args) {
234.     if (args.length > 0) {
235.       System.out.println("Using your input to demonstrate Stalin-Sort.");
236.       final var list = new LinkedList<>(List.of(args));
237.       System.out.println("Input:\t\t" + list);
238.       System.out.println("Naive:\t\t" + sort(list));
239.       System.out.println("Div&Conq:\t" + sortDC(list));
240.       inplace(list);
241.       System.out.println("in-place:\t" + list);
242.     } else {
243.       final int[] array = { 0, 1, 2, -123, 6, 7, 8, 3, 0, 4, 5, 6 };
244.       System.out.println("Demonstration of Stalin-Sort using integers and Strings.");
245.       System.out.println("Input:\t\t" + Arrays.toString(array));
246.       System.out.println("Naive:\t\t" + Arrays.toString(sort(array)));
247.       System.out.println("Div&Conq:\t" + Arrays.toString(sortDC(array)));
248.       System.out.println("========================");
249.       final var list = new LinkedList<>(List.of("A", "B", "x", "Ab", "y", "A", "", "A", "A", "A", "A", "z", "A"));
250.       System.out.println("Input:\t\t" + list);
251.       System.out.println("Naive:\t\t" + sort(list));
252.       System.out.println("Div&Conq:\t" + sortDC(list));
253.       inplace(list);
254.       System.out.println("in-place:\t" + list);
255.     }
256.   }
257. }