-5
\$\begingroup\$

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;
\$\endgroup\$

closed as too broad by Xcali, Suever, Jonah, Jo King, HyperNeutrino Jun 25 at 3:11

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Giuseppe Jun 24 at 18:18
  • 4
    \$\begingroup\$ This 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. \$\endgroup\$ – Poke Jun 24 at 18:19
  • 1
    \$\begingroup\$ And 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. \$\endgroup\$ – Unrelated String Jun 24 at 18:21
  • 1
    \$\begingroup\$ Generally on CGCC the code is a full program or function, and input and output are accepted with the default I/O rules. \$\endgroup\$ – lirtosiast Jun 25 at 1:31
  • 2
    \$\begingroup\$ This 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? \$\endgroup\$ – Poke Jun 25 at 14:08
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ The asker has specified average complexity, of which Python's is \$nlog(n)\$ \$\endgroup\$ – Jo King Jun 25 at 3:55
  • 1
    \$\begingroup\$ @JoKing Do not be confused with Big Theta. Big O only requires a less than relationship. but do not have to be equal. \$\endgroup\$ – tsh Jun 25 at 5:49
  • \$\begingroup\$ @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 \$\endgroup\$ – Jo King Jun 25 at 8:28
  • \$\begingroup\$ 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 \$\endgroup\$ – Poke Jun 25 at 18:30
  • \$\begingroup\$ @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. \$\endgroup\$ – tsh Jun 26 at 1:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.