Here is a video of a fistfight between a quick sort that wants to sort in ascending order and an insertion sort that wants to sort in descending order.
See below for code and live demo.
sort-war (DEMO)
A quick sort program and an insertion sort program sort a same array simultaneously. The quick sort program tries to sort the array in ascending order, and the insertion sort program tries to sort the array in descending order.
Each program is written in JavaScript and interpreted by JS-Interpreter. A step() function of JS-Interpreter is applied to each program alternately.
I created the sort war because I wanted to do some code-battling on sorting algorithms. The left (red) code fights to sort in ascending order, and the right (blue) code fights to sort in descending order. If they are aligned in ascending order, the left side wins. If they are aligned in descending order, the right side wins.
The code is written as ordinary JavaScript. There are two special functions.
-
get(i): get the i-th element from an array -
swap(i, j): swaps the i-th and j-th elements of an array
You can't do set. If you allow set, you can cheat by copying the array into memory in the code, sorting it, and then writing it all at once.
The get instruction in the code on the right descending side returns the negative value of the element, so the code on the right side can also be written to sort the array in ascending order.
The code is executed alternately on the left and the right, using JS-Interpreter's step() to execute the instructions in the code.
NeilFraser
/
JS-Interpreter
A sandboxed JavaScript interpreter in JavaScript.
JS-Interpreter
A sandboxed JavaScript interpreter in JavaScript. Execute arbitrary ES5 JavaScript code line by line in isolation and safety.
Live demo: https://neil.fraser.name/software/JS-Interpreter/
Documentation: https://neil.fraser.name/software/JS-Interpreter/docs.html
Developers using JS-Interpreter should subscribe to the announcement newsgroup. Security issues and major changes will be posted here: https://groups.google.com/g/js-interpreter-announce
Code that is fast to execute and can swap arrays frequently is strong. The speed depends on the execution unit of step() of the JS-Interpreter, but the more compact the code is, the faster it is.
The code size of the insertion sort is significantly more compact than the quick sort. Therefore, when the array's length is about 10, it often overwhelms and wins over quick sort by its execution speed. As arrays get longer, quick sort is considered to win.
The sorting algorithm does not assume that other algorithms will manipulate the array. Therefore, it is assumed that the array is not sorted when the execution finishes. Thus, the code runs again after its execution is completed. Quick sort can also cause errors because the array is manipulated externally, manipulating ranges beyond the array's bounds. In such cases, the code will be re-executed.
But is this a proper code-battling game? It seems to lack interest based on trilemma, such as one particular algorithm being strong against another algorithm but weak against another. It would be interesting to see a special sorting algorithm for battling with a defensive mechanism, such as actively disrupting the array if it seems aligned in the opponent's direction. However, it is doubtful that such a mechanism can be incorporated into the code of sort war.
Top comments (2)
Cool visualization. Your insertion sort isn't actually insertion sort though. It looks like a cross between insertion sort and bubble sort. Insertion sort doesn't do swaps. Instead, just before the inner loop it should store the next element to be inserted in a temporary variable. The inner loop should then shift elements until insertion point found. Then just after inner loop but still inside outer loop, the element saved earlier is inserted.
By shifting rather than swapping, insertion sort does roughly a third of the work that your version does, at least in terms of assignments (same number of comparisons). A swap involves 3 assignments, whereas a shift is just 1 assignment.
As you pointed out, it is not an exact insertion sort. It's a hybrid with bubble sort due to the lack of a 'set' instruction that directly sets the array's value.