/* Author: LukArToDo Created: 16.feb 2020 (some bugs) Updated: 18.feb 2020 (not optimized) Updated: 20.feb 2020 (optimized) Description: The code sorts the given list with the minimum number of moves, with only two possible actions: move one element to the tail or to the head of the list. Solution to the task -> https://www.sololearn.com/post/240018/?ref=app */ import java.util.*; public class OmasSort { public static void main(String...a){ int[][] cases ={{1,5,2,4}, {1,2,8,7,6,7,6,5,7,3,4,6,4,6,8}, {4,3,1,2,8,8,5,6,4,5,3}, {2,1,8,9,7,3,4,3,5}, {4,44,444,111,99}, {1,2,3,4,5,6}, {2,3,1,4}, {1,2,4,2,1}, {24,33,42,18,34,14,1,14}, {2,3,3,1,2}, {2,1,2,4,2,1}, {6,5,4,3,2,1}, {3,4,9,2,3,5}, {5,9,2,4,1}, {9,8,6,4,6,5,6}, {9,8,7,7,7,6,8,1}, {5,1,2,3,4,3,2,1}, {4,6,1,7,8,5,4,1}}; for(int[]input:cases) solve(input); } static void solve(int[] arr) { int i, j, k, lenSEQ, arrLen=arr.length, moves=0, startPos=0; // target array: int[]sorted=Arrays.stream(arr).boxed().sorted(Collections.reverseOrder()).mapToInt(e->e).toArray(); List temp,FRONT,END,SEQ = new ArrayList(); // create longest sequence, SEQ for(i=0;i(); for(j=0;jSEQ.size()) { SEQ=new ArrayList(temp); startPos=startJ; } } // edit non-SEQ elements: // larger than seqMAX goes to FRONT list // and smaller than seqMIN goes to END list FRONT = new ArrayList(); END = new ArrayList(); lenSEQ=SEQ.size() ; for( i=0, j=0; i=SEQ.get(0)) FRONT.add(arr[i]); else END.add(arr[i]); // FRONT list: the smallest element comes out first FRONT.sort(Comparator.naturalOrder()); // END list: the largest element comes out first END.sort(Comparator.reverseOrder()); System.out.println("START: "+Arrays.toString(arr)); // display the sorting process: while(!FRONT.isEmpty()||!END.isEmpty()) { for(i=0, j=0; i0;k--) arr[k]=arr[k-1]; arr[0]=cand; // if the element is already in the right place, skip sorting // otherwise, count the move and display the current array if(i>startPos) { moves++; System.out.println(cand+" to the front:"+ Arrays.toString(arr)); } } } } System.out.println("Total moves: "+moves+"\n"); } } /*********************************/ /* OLD VERSION 2 (not optimized) */ /* static void solve(int[] arr) { List seq=optimalDS(arr), front = new ArrayList(), end = new ArrayList(); int len=seq.size(), arrLen=arr.length; for(int i=0, j=0; i=seq.get(0)) front.add(arr[i]); else end.add(arr[i]); } System.out.println("START:"+Arrays.toString(arr)); //front.stream().sorted().forEach(i-> System.out.println(i+" to the front")); //end.stream().sorted(Comparator.reverseOrder()).forEach(i->System.out.println(i+" to the end")); // to display process: int[]sorted=arr.clone(); front.sort(Comparator.naturalOrder()); end.sort(Comparator.reverseOrder()); while(!front.isEmpty()||!end.isEmpty()) { for(int i=0, j=0, k=0; i0) { int cand=sorted[i]; for(k=i;k>0;k--) sorted[k]=sorted[k-1]; sorted[0]=cand; front.remove(0); System.out.println(cand+" to the front:"+ Arrays.toString(sorted)); } } } System.out.println("Total moves: "+(arrLen-len)+"\n"); } static List optimalDS(int[]arr) { List> allDS = allDS(arr); LDS: for(List longest:allDS) { int len=longest.size(); for(int i=0, j=0; ilongest.get(len-1)&&arr[i]> allDS (int[]input){ List> tempALL,ALL = new ArrayList>(); for (int i = 0; i < input.length; ++i){ tempALL = new ArrayList>(); for(List j : ALL){ if (j.get(j.size() - 1) >= input[i]){ List temp = new ArrayList(); temp.addAll(j); temp.add(input[i]); tempALL.add(temp); } } ALL.addAll(tempALL); ALL.add(Arrays.asList(input[i])); } ALL.sort((l1,l2)-> Integer.valueOf(l2.size()).compareTo(Integer.valueOf(l1.size()))); return ALL; } } */ /*********************************/ /*** OLD VERSION 1 (some bugs) ***/ /* static void solve(int[]arr) { int i, j, k, arrSize,moves=0,length = 0, length_start=0; arrSize=arr.length; int [] pos = new int[arrSize]; Arrays.fill(pos,arrSize-1); for(i=0;ij) pos[j]--; int[]target = new int[arrSize]; for(i=0; i< arrSize;i++) target[pos[i]]=arr[i]; System.out.print("Start: "); printArr(target,pos); for(i=0; i=length){ length_start=pos[i]; length = k; } } while(length=0) { if(target[pos[i]]>target[pos[d]]) break; d--; } if(d==-1) skip=true; k=pos[i]; for(j=i;j>0;j--) pos[j]=pos[j-1]; pos[0]=k; length_start--; length++; if(!skip) { moves++; System.out.printf("Move %d to the front: ", target[k]); printArr(target,pos); } } else if(pos[i] == length_start+length) { while(d

Oma's sort