Analysis of Sorting Problem by Prefix Reversals

Problem sortiranja uz reverzne prefikse kolokvijalno je poznat kao problem palačinki, a primijenjuje se u raspoređivanju procesa u mrežama paralelnih procesora. U radu je matematički analiziran problem, te je prikazana implementacija programske aplikacije koja vizualno prikazuje različite varijante ovakvih sortiranja. Nedavno je dokazano da je problem sortiranja palačinki NP-težak problem te još uvijek nije poznat minimalni broj koraka potrebnih za sortiranje, tek su nađene gornje ograde za taj broj.The problem of sorting with reverse prefixes is colloquially known as the pancake problem, and it is applied in scheduling processes in networks of parallel processors. The paper mathematically analyzes the problem, and presents the implementation of a software application that visually shows different variants of such sorting. It has recently been proven that the problem of sorting pancakes is an NP-difficult problem and the minimum number of steps required for sorting is still unknown, the upper fences for that number have just been found