Esoteric Algorithms

A collection of esoteric algorithms and data structures.

Note

All algorithms marked with a dagger (†) are my original creations, so you won't find them elsewhere, unless someone has decided to copy them from here or came up with them independently. Feel free to create your own implementation of these if you feel inspired!

Esoteric Data Structures

• Zero Ended Heap† (unimplemented)
  A self-balancing median heap that lets you only take from the edges instead of the middle.

Esoteric Sorts

• Badsort
  Creates all permutations of an array, sorts them lexicographically with Badsort, and returns the first permutations. After doing this recursively for k steps, it uses another algorithm to sort the final permutation list.

  • Worstsort
    Like Badsort, but squares the array length to obtain k

• Bogosort
  Shuffles the array until it's sorted.

  • Bogobogosort
    Like bogosort, but checks whether the list is sorted recursively by using bogosort.

• Bozosort
  Swaps random elements until the list is sorted.

• I Can't Believe It Can Sort
  A simple sorting algorithm but with the comparison inverted and the inner loop counts from 0 instead of from the index the outer loop is at. Somehow two wrongs make a right.

• Miracle Sort
  Repeatedly checks the array to see whether it's sorted. Returns the array once it's sorted. And does nothing else.

• Sleep Sort
  A non-comparison sort that schedules collecting the elements in the list based on their magnitude using an external scheduler.

• Window Sort†
  Selects a random unsorted window in the array, then rotates the array (by popping values on one end and pushing them onto the other) until the window becomes sorted. If a full rotation is completed without obtaining a sorted window, it picks a new window. If a sorted window is found, it undoes the last rotation but keeps the window elements frozen in place.
  Needs a backup sort because it can't sort 50% of arrays of length 3.

Joke Sorts

Joke sorts are a subcategory of esoteric sorts. Joke sorts are sorts that return a result that's not ordinarily admissible when trying to sort an array. This can happen in various ways, but the algorithms in question mostly explain themselves.

• Atomic Sort
  Sets all elements to be equal to the first element.

• Divine Sort
  Defines the list it received as sorted, even if it remains unsorted by other (blasphemous) metrics.

• Procrastination Sort†
  Wraps the array in a proxy to be notified of element access. When an element access occurs, it uses a poor implementation of Heap Select to place that element in its proper place before returning it, that accidentally disturbs the remainder of the array. This means it never actually converges on a sorted state. This is listed as a joke sort despite working "correctly" because it returns a proxy rather than a real array.
  This sort is a commentary on how procrastination can cause you to make costly mistakes that result in needing to do more work than was initially required.

• Stalin Sort
  Deletes any elements found to be out of order.

Esoteric Searches

• Bogosearch†
  Repeatedly shuffles a list of all vertices in the graph until they contain a sequence of nodes that are a valid path from A to B. Returns that path.
  Characteristics: will never fail to return a path when one exists. Will never terminate when no path exists. The returned path is not guaranteed to be optimal.

• Wander Search†
  Performs a random walk until it reaches the goal and returns that path.
  Characteristics: may fail to return a path on directed graphs when one exists. The returned path is not guaranteed to be optimal.

• Z*†
  A* with a max-heap.
  Characteristics: unsure (TODO)

• Lover Search† (unimplemented)
  A bidirectional search that updates the heuristic to point at the most recently expanded node of its counterpart search instead of the original target.
  Characteristics: unsure (TODO)

Joke Searches

Joke searches are a subcategory of esoteric searches. Joke searches are searches that return a result that's not ordinarily admissible when trying to find a path.

• Desire Search†
  Defines the source and the goal to be adjacent, resulting in a path of length 1. Inspired by "desire paths".

• Divine Search† Defines the goal to be equal to the source, resulting in a path of length 0.

Making Contributions

I'm happy to accept contributions if you have your own idea for an esoteric algorithm, data structure, or similar.

Some important notes:

• Be sure to use the utilities provided in the utils folder, or define your own if they're insufficient.
• Use JSDoc to annotate the types correctly (e.g. Sort<T> or Search).