God Tier algorithms thread

I'll start.

> Quicksort

Other urls found in this thread:

en.wikipedia.org/wiki/Rolling_hash
twitter.com/NSFWRedditGif

>quicksort

man that's some fucking good bait right there man lemme tell you wut

C++

>uds with path compression and rank heuristic
>reverse Ackerman function complexity

bogosort :^)

I don't remember the name, but that string sub-pattern matching algorithm where the comparisons are all done by realizing a string is just a representation of a number, and comparing numbers and removing digits is much easier. It's a fantastic example of thinking outside the box.

The best algorithm is the reduction used in cook's theorem: A polynomial-time transformation of any algorithm into boolean satisfiability. Naming any sorting algorithm as "god-tier" marks you as an undergrad who never learned any actual computer science.

>the virgin quicksort
depended on choice of pivot
cannot be easily implemented outside arrays
smelly
worst case of n^2

>the CHAD heapsort
gives a shit about your data
can easily extend itself over all data structures
clean
always n*log(n)

Sleepsort

>Only works for numbers

A*

radix

>not define your own mapping of countable set to naturual

Boosting in general.

obsolete

Fast Fourier Transform

bubble sort

What's better (while being equally accurate)? Actually curious.

I like suffix tries.
I know they're simple, but they're cool.
KMP is fancy too.

Simplex algorithm and polyhedron theory.

Naming off impractical algorithms for academic cred won't make you popular with the girls, user. Not to mention any decent undergrad program will familiarize students with it by their third year.

my nigga.

printf and scanf

D*

all the probabilistic algorithms with good expected error bounds, e.g. hyperloglog

unironically probably the most important algorithm ever invented (not including the more basic ones, like addition algorithms, which it relies on).

I want to kill myself because I forgot all of this shit

dumbsort.
It is just superior.

quicksort is faster though.
heapsort is ok if memory is an issue

backpropagation

Not a long algorithm per se but dot product is so fucking useful. Wish I'd known about it years ago. It would have saved me a lot of pain. Actually I'm pretty sure they would have covered this in high school but I'd completely forgotten.

Bootstrapping

A*

Push–relabel maximum flow algorithm

x264

Rabin-karb with rolling hashfunction

>rolling hashfunction
any examples? I remember the first thing that came to my mind was just xor but that's prone to false positives

Viterbi

This was fixed in the 90s by adding an equal to check or a second pivot, making quicksort nlogn worst case

itt first year cs

So does every single sort, dumb-dumb. The notion of sorting implies an order, and the only thing that has an explicit order are numbers. Everything else has to be mapped to a number.

counting sort

D* is obsolete as well, D*-lite is better.
And if you don't need to calculate it multiple times (i.e. static environment), there's no reason not to use A*.
t. writing master's thesis on robot navigation

Incrementation.

en.wikipedia.org/wiki/Rolling_hash

a xor b
b xor a
a xor b
[|/code]
Truly the best swapping algorithme

> Bootstrapping
As in non-parametric statistics? If so, I'm with you.

Bootstrapping a self-hosting compiler isn't really an algorithm unless you have a really broad definition.

You forget about the superior mergesort, assuming memory isn't an issue. It's stable whereas heapsort isn't.