Write the shortest O(n^2) sorting algorithm

-5

1

Write a sorting algorithm for a list of integers that has an average performance of O(n^2).

This is , 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;

Bip

Posted 2019-06-24T18:05:29.443

Reputation: 21

Question was closed 2019-06-25T03:11:31.703

@AdmBorkBork notable difference is disallowing bogosort and not counting the list declaration, whatever that means. – Giuseppe – 2019-06-24T18:15:11.580

3

Welcome to Code Golf Stack Exchange! Since you're new, we do typically recommend using The Sandbox to get feedback on a challenge to make sure it's up to our usual standards or isn't a duplicate of an existing challenge; I think I'd agree with @AdmBorkBork that this really doesn't add much to the existing challenge and should be closed as a duplicate.

– Giuseppe – 2019-06-24T18:18:11.440

Also, for the sake of being self-contained it should probably supply a definition of sorting. – Unrelated String – 2019-06-24T18:19:09.613

4This might be better received if you ask us to golf a specific sorting algorithm. Asking a question of the form "Do this thing but not this way" is generally ill-received (In this case restricting the use of a specific algorithm). Additionally there are other challenges that already ask for a golfed sorting such as the one AdmBorkBork linked. Because of that, this will likely get closed as a duplicate since, as Giuseppe mentioned, this challenge isn't really adding anything interesting over those challenges. – Poke – 2019-06-24T18:19:15.437

1And if bogosort and variants thereof are to be excluded then a rigorous definition of bogosort variant is probably warranted. I feel like p≤₁ in Brachylog is probably not in the spirit of that rule, but it complies with the letter. – Unrelated String – 2019-06-24T18:21:42.123

@AdmBorkBork I edited the question to clarify it. – Bip – 2019-06-24T18:50:34.947

1

Generally on CGCC the code is a full program or function, and input and output are accepted with the default I/O rules.

– lirtosiast – 2019-06-25T01:31:39.800

2This challenge was reopened after Bip edited it the first time. Can the folks who closed it again please at least comment to add more context about why it was put on hold again? – Poke – 2019-06-25T14:08:17.770

1"an average performance of O(n^2)" isn't exactly clear, since big-O refers to worst-case time complexity, not average case. Also, perhaps the question should clarify input methods, because the example one uses variable assignment, which we don't generally allow. – mbomb007 – 2019-06-25T19:17:03.707

Answers

4

Jelly, 5 bytes

ṭ@Ṣ¥/

Try it online!

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.)

Explanation

ṭ@Ṣ¥/
    /  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).

ais523

Posted 2019-06-24T18:05:29.443

Reputation: 11

The asker has specified average complexity, of which Python's is $nlog(n)$ – Jo King – 2019-06-25T03:55:10.700

1@JoKing Do not be confused with Big Theta. Big O only requires a less than relationship. but do not have to be equal. – tsh – 2019-06-25T05:49:03.290

@tsh Ah sorry, I was assuming ais523 was taking the best case O(n) as the average case, though rereading I see this is addressed in the second explanation – Jo King – 2019-06-25T08:28:09.510

Aw come on, @tsh. You knew what he meant. Typically when people talk about big o in programming they mean big theta. It doesn't mean nearly as much when I say my bubble sort has a big o of n^n – Poke – 2019-06-25T18:30:22.703

@Poke But it is hard to say O(n^2) since you can do something like foreach (val1 in arr) foreach (val2 in arr) sleep(1); arr.quickSort();. It do be O(n^2) but meaningless. – tsh – 2019-06-26T01:48:31.203

@Abigail: At the time I wrote this answer, that restriction was worded differently and didn't exclude the first answer here (as it doesn't sort the original list with a builtin). I'll delete the second answer, though, as that pretty clearly violates the requirement of the question. – ais523 – 2019-06-26T15:08:24.367

Asked: 2019-06-24T18:05:29.443

Viewed: 373 times

Active: 2019-06-26T15:10:06.790