Backshift
Backshift is another sorting algorithm that aims to implement sorting in clean code invented by User:A. It is less efficient than any other sorting algorithm; in its worst case, its algorithmic complexity is O(∞). However, it was best known as an esoteric programming language after people started to abuse the buggy algorithm to write useful programs.
Algorithm
Take 4321 as an example.
# This is in pseudo-code and can definitely not run. Refer to the talk page.
# The talk page presents an elegant version that is equivalent to this.
while move_left_number != 0:
move_left_number=len(unsorted)-rightmost_number
move_left(move_left_number)
So, 1 will be moved left 4-1=3 times, which makes the item list 1432.
Then, 2 will be moved left 4-2=2 times, which makes the item list 1243.
Finally, 3 will be moved left 4-3=1 times, which makes the item list 1234.
4 cannot be moved, so the sorting halts.
Note that negative moving left results in moving right.
Backshift in other bases
Since Backshift struggles with sorting some digits in base 10, it was possible it did better in sorting lower bases. Unfortunately not.
Unary
Backshift is able to successfully sort the digits of a unary number N iff the unary unit symbol itself is N. However, in the (9) cases where it is successful, it is still less effective than wikipedia:Bogosort by a factor of two in terms of end condition checks using the specified algorithm. Backshift performs twice as many end condition checks before successful termination than Bogosort.
Binary
Backshift can successfully sort 0b1 in binary. Every other number (including 0) results in an non-terminating state where the final number may or may not be sorted. Obviously Backshift is just as capable of sorting these digits interpreted as base 10, so, as you would expect, Backshift-sorting the digits of 100 gives the same result whether interpreted as base 2 or 10. As with unary sorts, Bogosort is more effective at sorting 0b1.
Hexadecimal
Treating the name of this language as hex digits (ignoring those that aren't), backshift('backshift') => 'fbackshit' as backshift(0xbacf) => 0xfbac. Backshift seems about as capable of sorting digits in this base as base10, but there are more digits, so
Backshift provides an example to computer scientists of a sort algorithm less effective than wikipedia:Bogosort. However, in some cases (first example on this page), in some bases, Backshift outperforms wikipedia:Bogosort considerably, so a thorough analysis of the specific conditions where and why this occurs could conceivably be undertaken.
Examples
Perhaps ironically Backshift is as computationally capable as many other entries on this wiki (which is not necessarily very capable at all), and could be considered a language that takes a program as a string representation of a number, the digits of which are in a radix greater than the program length if the program is to ever terminate.
Infinite loop
In base 36:
Hello, World
or simply(under base 0):
0
Hello, World!
In base 36:
Hello, World
where the d represents 13 and is at position 13 to cleanly terminate.
ello WrledoH
is slightly more interesting, but outputs Hello Worlde. Note the whitespace padding and non-digit characters are significant in these examples for setting the length of the string.
Inverse Truth-machine
x
1 = 0 , 0 = 1
Here is a slightly more elegant version:
1x
Where x is the input; 2=0, 1=1.
Cat program
Ql
Here, Q is the input for the cat program, and l is the length of Q plus 1.
Quine
1
99 bottles of beer
100-len(a) bottles of beer on the wall, 100-len(*) bottles of beer. Take one down and pass it around, 100-len(**) bottles of beer on the wall.Ȏ𝝤𝖭ƋʢaƉʡaƇʠaƅʟaƃʞaƁʝaſʜaŽʛaŻʚaŹʙaŷʘaŵʗaųʖaűʕaůʔaŭʓaūʒaũʑaŧʐaťʏaţʎašʍaşʌaŝʋaśʊařʉaŗʈaŕʇaœʆaőʅaŏʄaōʃaŋʂaʼnʁaŇʀaŅɿaŃɾaŁɽaĿɼaĽɻaĻɺaĹɹaķɸaĵɷaijɶaıɵaįɴaĭɳaīɲaĩɱaħɰaĥɯaģɮaġɭağɬaĝɫaěɪaęɩaėɨaĕɧaēɦađɥaďɤačɣaċɢaĉɡaćɠaąɟaăɞaāɝaÿɜaýɛaûɚaùəa÷ɘaõɗaóɖañɕaïɔaíɓaëɒaéɑaçɐaåɏaãɎaáɍaßɌaÝɋaÛɊaÙɉa×ɈaÕɇaÓɆaÑɅaÏɄaÍɃaËɂaÉɁa
Steps through the verses of the song, with final output on iteration 297:
100-len(aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa) bottles of beer on the wall, 100-len(*ʢʡʠʟʞʝʜʛʚʙʘʗʖʕʔʓʒʑʐʏʎʍʌʋʊʉʈʇʆʅʄʃʂʁʀɿɾɽɼɻɺɹɸɷɶɵɴɳɲɱɰɯɮɭɬɫɪɩɨɧɦɥɤɣɢɡɠɟɞɝɜɛɚəɘɗɖɕɔɓɒɑɐɏɎɍɌɋɊɉɈɇɆɅɄɃɂɁ) bottles of beer. Take one down and pass it around, 100-len(**ƋƉƇƅƃƁſŽŻŹŷŵųűůŭūũŧťţšşŝśřŗŕœőŏōŋʼnŇŅŃŁĿĽĻĹķĵijıįĭīĩħĥģġğĝěęėĕēđďčċĉćąăāÿýûù÷õóñïíëéçåãáßÝÛÙ×ÕÓÑÏÍËÉ) 𝖭𝝤 bottles of beer on the wall.Ȏ
The program is to be interpreted as digits extending base 36 to all following Unicode characters as an open-ended base, which works because Backshift only cares about assigning values to each symbol. Any character following 'z'(=36) is a converted to a value by subtracting 86 from its code point. '{' = 37, and so on. Numbers in the lyrics are to be read by subtracting unary values from 100.
External resources
- Possibly related computational model
- Bogobogosort Another sort algorithm than sometimes outperforms, and sometimes doesn't, Backshift