Write a sorting algorithm for a list of integers that has an average performance of O(n^2).
This is code-golf, so the shortest code in bytes wins.
RULES:
The characters wasted for the declaration of the list are not counted
(e.g. var c = new List<int>() { 4, 2, 1, 3 }; is not counted)
Builtins to sort a list are not allowed.
The best I did in C# is 82 ('c' is the list to be sorted):
var n=c.ToList();for(int i=0;i<n.Count;i++){int x=c.Min();c.Remove(x);n[i]=x;}c=n;
ṭ@Ṣ¥/
Jelly's sort builtin Ṣ is too fast, so we had to slow it down a bit, via using it as part of a slower sorting algorithm rather than using it directly. (This algorithm doesn't sort the original list with a builtin, which is what the question banned at the time this answer was written.)
ṭ@Ṣ¥/
/ One element at a time,
ṭ@ append that element to the list so far
¥ and
Ṣ sort the resulting list
Jelly's sort algorithm (which, behind the scenes, is Python's sort algorithm) is O(n) on lists that have only one element out of place, thus this implements an O(n²) sorting algorithm (specifically insertion sort).
foreach (val1 in arr) foreach (val2 in arr) sleep(1); arr.quickSort();. It do be O(n^2) but meaningless.
\$\endgroup\$
p≤₁in Brachylog is probably not in the spirit of that rule, but it complies with the letter. \$\endgroup\$