daily pastebin goal
7%
SHARE
TWEET

Stalin-Sort using Divide&Conquer

DulcetAirman Nov 4th, 2018 (edited) 34 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;
  5. import java.util.LinkedList;
  6. import java.util.List;
  7.  
  8. /**
  9.  * Stalin-Sort is a weird 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
  29.  * implementation using a {@link LinkedList}.
  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>
  37.  * <li>{@link #inplace(LinkedList)} implementation of the original idea</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);
  143.     result.add(previous);
  144.     for (var i = 1; i < size; i++) {
  145.       final var value = input.get(i);
  146.       if (previous.compareTo(value) < 0) {
  147.         result.add(previous = value);
  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])
  164.         result.add(input.get(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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top