Sort this, quick!

Question

Well... there are 59 (now 60) questions tagged sorting, but no simple quicksorts.

That must be fixed.

For those unfamiliar with quicksort, here is a breakdown, courtesy of Wikipedia-

1. Pick an element, called a pivot, from the array.
2. Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Rules

The rules are simple:

• Implement a numerical quicksort in the programming language of your choice.
• The pivot should be chosen at random or with median of three (1st, last, and middle element).
• Your program can be a complete program or function.
• You can get the input using STDIN, command line args, or function parameters. If using a string input, the input is space separated.
• The input may contain decimal and negative values. However, there will be no duplicates.
• You may output to STDOUT or by returning from the function.
• No built-in sorting (or sorting related) functions or standard loopholes.
• The list may be an arbitrary length.

Bonus #1: On lists or sub-lists of length <= 5, use insertion sort to speed things up a bit. Reward: -15%.

Bonus #2: If your language supports concurrency, sort the list in parallel. If you are using an insertion sort on sub-lists, the final insertion sort doesn't need to be in parallel. Built in thread pools/ thread scheduling are allowed. Reward: -15%.

Note: Median of three was confusing some people, so here is an explanation, courtesy of (again) Wikipedia:

choosing the median of the first, middle and last element of the partition for the pivot

Scoring

This is code-golf. Base score is in bytes. If you got one bonus, take 15% off that number. If you got both, take 30% off. That really sounds like a sales pitch.

This isn't about finding the shortest answer overall, but rather the shortest in each language.

And now, a shameless copy of the leaderboard snippet.

The Leaderboard

The Stack Snippet at the bottom of this post generates the catalogue from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

## Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

## Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

## Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the snippet:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

/* Configuration */
var QUESTION_ID = 62476; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 41505; // This should be the user ID of the challenge author.
/* App */
var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;
function answersUrl(index) {
 return "http://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}
function commentUrl(index, answers) {
 return "http://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}
function getAnswers() {
 jQuery.ajax({
 url: answersUrl(answer_page++),
 method: "get",
 dataType: "jsonp",
 crossDomain: true,
 success: function (data) {
 answers.push.apply(answers, data.items);
 answers_hash = [];
 answer_ids = [];
 data.items.forEach(function(a) {
 a.comments = [];
 var id = +a.share_link.match(/\d+/);
 answer_ids.push(id);
 answers_hash[id] = a;
 });
 if (!data.has_more) more_answers = false;
 comment_page = 1;
 getComments();
 }
 });
}
function getComments() {
 jQuery.ajax({
 url: commentUrl(comment_page++, answer_ids),
 method: "get",
 dataType: "jsonp",
 crossDomain: true,
 success: function (data) {
 data.items.forEach(function(c) {
 if (c.owner.user_id === OVERRIDE_USER)
 answers_hash[c.post_id].comments.push(c);
 });
 if (data.has_more) getComments();
 else if (more_answers) getAnswers();
 else process();
 }
 }); 
}
getAnswers();
var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+(?:.\d+)?)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;
var OVERRIDE_REG = /^Override\s*header:\s*/i;
function getAuthorName(a) {
 return a.owner.display_name;
}
function process() {
 var valid = [];
 
 answers.forEach(function(a) {
 var body = a.body;
 a.comments.forEach(function(c) {
 if(OVERRIDE_REG.test(c.body))
 body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
 });
 
 var match = body.match(SCORE_REG);
 if (match)
 valid.push({
 user: getAuthorName(a),
 size: +match[2],
 language: match[1],
 link: a.share_link,
 });
 else console.log(body);
 });
 
 valid.sort(function (a, b) {
 var aB = a.size,
 bB = b.size;
 return aB - bB
 });
 var languages = {};
 var place = 1;
 var lastSize = null;
 var lastPlace = 1;
 valid.forEach(function (a) {
 if (a.size != lastSize)
 lastPlace = place;
 lastSize = a.size;
 ++place;
 
 var answer = jQuery("#answer-template").html();
 answer = answer.replace("{{PLACE}}", lastPlace + ".")
 .replace("{{NAME}}", a.user)
 .replace("{{LANGUAGE}}", a.language)
 .replace("{{SIZE}}", a.size)
 .replace("{{LINK}}", a.link);
 answer = jQuery(answer);
 jQuery("#answers").append(answer);
 var lang = a.language;
 lang = jQuery('<a>'+lang+'</a>').text();
 
 languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
 });
 var langs = [];
 for (var lang in languages)
 if (languages.hasOwnProperty(lang))
 langs.push(languages[lang]);
 langs.sort(function (a, b) {
 if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
 if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
 return 0;
 });
 for (var i = 0; i < langs.length; ++i)
 {
 var language = jQuery("#language-template").html();
 var lang = langs[i];
 language = language.replace("{{LANGUAGE}}", lang.lang)
 .replace("{{NAME}}", lang.user)
 .replace("{{SIZE}}", lang.size)
 .replace("{{LINK}}", lang.link);
 language = jQuery(language);
 jQuery("#languages").append(language);
 }
}

body { text-align: left !important}
#answer-list {
 padding: 10px;
 width: 290px;
 float: left;
}
#language-list {
 padding: 10px;
 width: 290px;
 float: left;
}
table thead {
 font-weight: bold;
}
table td {
 padding: 5px;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="language-list">
 <h2>Shortest Solution by Language</h2>
 <table class="language-list">
 <thead>
 <tr><td>Language</td><td>User</td><td>Score</td></tr>
 </thead>
 <tbody id="languages">
 </tbody>
 </table>
</div>
<div id="answer-list">
 <h2>Leaderboard</h2>
 <table class="answer-list">
 <thead>
 <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
 </thead>
 <tbody id="answers">
 </tbody>
 </table>
</div>
<table style="display: none">
 <tbody id="answer-template">
 <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
 </tbody>
</table>
<table style="display: none">
 <tbody id="language-template">
 <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
 </tbody>
</table>

• msh210: "The pivot should be chosen at random or with median of three (1st, last, and middle element)." What does this mean? You previously said only one element is chosen.
• Daniel M.: @daniero Snippet is fixed now
• John Dvorak: Is the median choice algorithm a hard requirement? It is impractical (as in, it tanks the performance) in languages that use a linked list as their primary array type (Haskell, LISP) and there is already at least one answer that ignores the rule.
• John Dvorak: Both random pivot and median of three are problematic in list-based languages. Both require random access into the array and accessing the end of a linked list is O(n). Taking Taking the median of the first three elements doesn't quite do the same kind of job (also because you'll grab the same pivot within three splits anyways) and only complicates the code for no good reason.
• John Dvorak: Random pivot is problematic in Haskell for another reason, too - once you start rolling dice, you're no longer writing a function. You're defining an I/O action that produces an array. You could define a function that takes a RNG state as an argument, but it isn't too great either.

Answer 1

C++, (削除) 440.3 (削除ここまで) (削除) 405 (削除ここまで) 388 bytes

(削除) 518 bytes - 15% bonus for insertion sort = 440.3 bytes (削除ここまで)

(削除) 477 bytes - 15% bonus for insertion sort = 405.45 bytes (削除ここまで)

(削除) 474 bytes - 15% bonus for insertion sort = 402.9 bytes (削除ここまで)

456 bytes - 15% bonus for insertion sort = 387.6 bytes

Thanks to @Luke for saving 3 bytes (2 really).

Thanks to @Dúthomhas for saving 18 (15 really) bytes.

Note that I am new here and this is my first post.

This is a .h (header) file.

Compressed Code:

#include<iostream>
#include<ctime>
#include<cstdlib>
void s(int a[],int i,int j){int t=a[i];a[i]=a[j];a[j]=t;}int z(int a[],int b,int e){int p=a[(rand()%(e-b+1))+b];b--;while(b<e){do{b++;}while(a[b]<p);do{e--;}while(a[e]>p);if(b<e){s(a, b, e)}}return b;}void q(int a[],int b,int e){if(e-b<=5){for(int i=b;i<e;i++){for(int j=i;j>0;j--){if(a[j]<a[j-1]){s(a,j,j-1);}else{break;}}}return;}int x=z(a,b,e);q(a,b,x);q(a,x,e);}void q(int a[],int l){q(a,0,l);}

Full Code:

#include <iostream>
#include <ctime>
#include <cstdlib>
void swapElements(int toSort[], int i, int j) {
 int temp = toSort[i];
 toSort[i] = toSort[j];
 toSort[j] = temp;
}
int partitionElements(int toSort[], int beginPtr, int endPtr)
{
 int pivot = toSort[(rand() % endPtr - beginPtr + 1) + beginPtr];
 beginPtr--;
 while (beginPtr < endPtr) {
 do {
 beginPtr++;
 } while (toSort[beginPtr] < pivot);
 do {
 endPtr--;
 } while (toSort[endPtr] > pivot);
 if (beginPtr < endPtr) {
 // Make sure they haven't crossed yet
 swapElements(toSort, beginPtr, endPtr);
 }
 }
 return beginPtr;
}
void quickSort(int toSort[], int beginPtr, int endPtr)
{
 if (endPtr - beginPtr <= 5) { // Less than 5: insertion sort
 for (int i = beginPtr; i < endPtr; i++) {
 for (int j = i; j > 0; j--) {
 if (toSort[j] < toSort[j - 1]) {
 swapElements(toSort, j, j - 1);
 } else {
 break;
 }
 }
 }
 return;
 }
 int splitIndex = partitionElements(toSort, beginPtr, endPtr);
 quickSort(toSort, beginPtr, splitIndex );
 quickSort(toSort, splitIndex, endPtr);
}
void quickSort(int toSort[], int length)
{
 quickSort(toSort, 0, length);
}

• edc65: You can save 10 bytes using a single letter name instead of quickSort and removing spaces in the last function call. And I bet that you can get a better score avoiding the bonus (15% is not enough)
• cadaniluk: You can save another 5 bytes by replacing the square brackets of the arguments by single asterisks. Some macro magic could shave off some more bytes, I guess.
• Luke: You don't need a space after #include.
• Dúthomhas: Get rid of 34 bytes by removing the call to srand(time(NULL)); You'll still get pseudo-random numbers from rand().

Answer 2

APL, (削除) 49 (削除ここまで) 42 bytes

{1≥⍴⍵:⍵⋄(∇⍵/⍨⍵<p),(⍵/⍨⍵=p),∇⍵/⍨⍵>p←⍵[?⍴⍵]}

This creates an unnamed recursive monadic function that accepts an array on the right. It does not qualify for the bonus.

Explanation:

{1≥⍴⍵:⍵⋄ ⍝ If length(⍵) ≤ 1, return ⍵
 p←⍵[?⍴⍵]} ⍝ Choose a random pivot
 ∇⍵/⍨⍵> ⍝ Recurse on >p
 (⍵/⍨⍵=p), ⍝ Concatenate with =p
 (∇⍵/⍨⍵<p), ⍝ Recurse on <p

Try it online

Fixed an issue (at the cost of 8 bytes) thanks to marinus and saved 7 bytes thanks to Thomas Kwa!

• lirtosiast: The question specifies there will be no duplicates. (Don't know how it took me so long to see that...)

Answer 3

C++17, (削除) 254 (削除ここまで) (削除) 199 (削除ここまで) 195 bytes

#include<vector>
#include<cstdlib>
#define P push_back(y)
using V=std::vector<int>;V q(V a){int p=a.size();if(p<2)return a;p=rand()%p;V l,r;for(y:a)(y<a[p]?l:r).P;l=q(l);for(y:q(r))l.P;return l;}

With whitespace:

V q(V a) {
 int p = a.size();
 if (p < 2)
 return a;
 p = rand() % p;
 V l,r;
 for (y : a)
 (y < a[p] ? l : r).P;
 l=q(l);
 for (y : q(r))
 l.P;
 return l;
}

• Chris Jefferson: No need for srand(time(NULL)). No need for the erase, just let the value get partitioned, then change the 'if (a.empty())' to 'if(a.size()<2)' and remove 'l.P(x)'.
• lynn: Eliminating the erase allowed me to save a lot of bytes. Thank you!
• Chris Jefferson: One other tiny one: No need to assign 'r=q(r)', just use 'for(y:q(r))', but that's all I can see!
• kirbyfan64sos: Just out of curiosity: where is C++17 in particular used here?
• lynn: for (y : a) would otherwise need to be for (auto y : a) or for (int y : a). (Actually, clang++ calls this a C++1z extension, but it doesn't really seem to be C++17? I don't know and it's too late at night to go look it up.)

Answer 4

Pyth, 25 bytes

L?tbsyMa_,]JObf<TJbf>TJbb

This defines a function y, that takes a list of numbers as input.

Try it online: Demonstration

Explanation

L?tbsyMa_,]JObf<TJbf>TJbb
L define function y(b), that returns: 
 ?tb if t[1:] (if the list has more than one element):
 Ob choose a random element of b
 J save it in J
 ] put J in a list
 , f<TJb create a pair, that contains ^ and a list of 
 all numbers smaller than J: [[J], [smaller than J]] 
 _ reverse this list: [[smaller than J], [J]]
 a f>TJb append a list with all elements bigger than J: 
 [[smaller than J], [J], [bigger than J]]
 yM call y recursively for each sublist
 s combine the results and return it
 b else: simply return b

Pyth, 21 bytes (probably invalid)

I use the "group-by" method, which internally uses a sort. I use it to split the original list into three sublists (all element smaller than the pivot, the pivot, and all elements bigger than the pivot). Without the sort in "group-by", it could return these 3 lists in a different order.

As said, this is probably invalid. Nevertheless I'll keep it here, because it's an interesting solution.

L?tb&]JObsyM.g._-kJbb

Try it online: Demonstration

Explanation

L?tb&]JObsyM.g._-kJbb
L def y(b): return
 ?tb if t[1:] (if the list has more than one element):
 Ob choose a random element of b
 J save it in J
 &] put it in an array and call "and" 
 (hack which allows to call 2 functions in one statement)
 .g b group the elements in b by:
 ._-kJ the sign of (k - J)
 this generates three lists
 - all the elements smaller than J
 - J
 - all the elements bigger than J
 yM call y recursively for all three lists
 s and combine them
 b else: return b

Answer 5

><> (Fish), (削除) 313 (削除ここまで) 309 bytes

!;00l[l2-[b1.
>:0)?v~$:@&vl2,$:&${:}$
^-1@{< ]]. >055[3[5b.
?v~~@~ v:}@:}@:}:}@:}@}}}(}(}({{:@=
.>=$~?$>~]]
.001-}}d6.{$}1+}d6
?v:{:}@{(?v08.}:01-=
 >{$~~{09.>95.v-1@{< v-1}$<
.:@}:@{=${::&@>:0)?^~}&>:0)?^~+}d6
 1-:0a.{{$&l&1+-: >:0)?v~:1)?!v62fb.
>:0)?v~:}:1)?v~69.^@{-1<>.!]]~<
^@{-1<:}@@73.>69@@:3+[{[b1.

This took me very long to write. You can try it here, just put the list that has to be sorted into the initial stack, seperated with commas, before running the program.

How it works

The program grabs the first, middle and last element in the initial stack and calculates the median of these three.
It then changes the stack to:

[list 1] element [list 2]

where everything in list 1 is smaller or equal to the element and everything in list 2 is bigger.
It recursively repeats this process on list 1 and list 2 untill the whole list is sorted.

Answer 6

CJam, 40 bytes

{_1>{_mR:P-PaL@{_P<{+}{@\+\}?}/J\J+}&}:J

This is a named function that expects an array on the stack and pushes one in return.

Try it online in the CJam interpreter.

The above code follows the spec as closely as possible. If that's not required, 12 bytes can be saved:

{_1>{_mR:P;_{P<},J_@^J+}&}:J

Answer 7

Haskell, (削除) 137 (削除ここまで)136 bytes

f=filter
m a b c=max(min a b)(min(max a b)c)
q[]=[]
q l=let{n=m(head l)(head$drop(length l`div`2)l)(last l)}in(q$f(<n)l)++(n:(q$f(>n)l))

The ungolfed version is hereunder, with expanded variable and function names and some intermediate results added:

median a b c = max (min a b) (min (max a b) c)
quicksort [] = []
quicksort l = let mid = median (head l) (middle l) (last l)
 lesser = filter (< mid) l
 greater = filter (> mid) l
 middle l = head $ drop (length l `div` 2) l
 in (quicksort lesser) ++ (mid : (quicksort greater))

I'm taking advantage of the fact that there's no duplicates to use two strict comparisons. I'll have to check if Data.List.partition doesn't makes things shorter though, even considering I would have to add an import statement. I'm not taking the insertion sort bonus because I consider Data.List.insert as a sorting-related function — thus forbidden — and if not using it, adding the insertion sort pushes the code to 246 bytes, 209.1 with the bonus, so it's not worth it.

Edit : Thanks to RobAu for their suggestion to create an alias to use f=filter. It may save only one byte but everything helps.

• Rob Audenaerde: f=filter might shave off some bytes.
• Cyoce: Maybe you can shave a few bytes by making a function to handle the two redundant q$f(>n)l and q$f(<n)l calls?
• stevec: Another haskell example appeared on Computerphile today.

Answer 8

Python 3, (削除) 123 (削除ここまで), 122.

Saved 1 byte thanks to Aaron.

This is the first time I've actually bothered to write a sorting algorithm. It's actually a little easier than I thought it would be.

from random import*
def q(s):
 if len(s)<2:return s
 p=choice(s);return q([d for d in s if d<=p])+q([d for d in s if d>p])

Ungolfed:

from random import choice
def quick_sort(seq):
 if len(seq) < 2:
 return seq
 low = []
 high = []
 pivot = choice(seq)
 for digit in seq:
 if digit > pivot:
 high += [digit]
 else:
 low += [digit]
 return quick_sort(low) + quick_sort(high)

• VisualMelon: This looks like it might not work, due to the <= comparison - it doesn't guarantee that p is in the right place, you probably need to change that to an exclusive inequality, and add p in the middle independently (I havn't tested/can't test the code).
• Morgan Thrapp: @VisualMelon I tested it with a bunch of different cases and never got an incorrect result, but if you can find a test case that breaks it, let me know. Also, it might not work with duplicates, but the challenge specifies that there won't be duplicates.
• VisualMelon: I'd have thought that [2, 1, 3] would break it 1/3 of the time, as when it selects the pivot to be 2, it will have the low list be [2, 1] - I'm sorry I can't test this myself right now.
• Morgan Thrapp: @VisualMelon Well, sure, but it then recursively sorts again.
• VisualMelon: Ah, sorry, missed that completely, not quite how I would expect a Quicksort to be implemented - have an upvote for confusing me

Answer 9

Javascript (ES2015), 112

q=l=>{let p=l[(Math.random()*l.length)|0];return l.length<2?l:q(l.filter(x=>x<=p)).concat(q(l.filter(x=>x>p)));}

Explanation

//Define lambda function q for quicksort
q=l=>{
 //Evaluate the pivot
 let p=l[(Math.random()*l.length)|0];
 //return the list if the length is less than 2
 return l.length < 2 ? l:
 //else return the sorted list of the elements less or equal than 
 the pivot concatenated with the sorted list of the elements 
 greater than the pivot
 q(l.filter(x=>x<=p)).concat(q(l.filter(x=>x>p)));
}

• Nissa: ES6 could probably shorten this.

Answer 10

Ruby, (削除) 87 (削除ここまで) 60 bytes

q=->a,p=a.sample{a[1]?(l,r=a.partition{|e|e<p};q[l]+q[r]):a}

Ungolfed:

def quicksort(a, pivot=a.sample)
 if a.size > 1
 l,r = a.partition { |e| e < pivot}
 quicksort(l) + quicksort(r)
 else
 a
 end
end

Test:

q[[9, 18, 8, 5, 13, 20, 7, 14, 16, 15, 10, 11, 2, 4, 3, 1, 12, 17, 6, 19]]
=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

Answer 11

Octave, (削除) 76 (削除ここまで) 75 bytes

function u=q(u)n=numel(u);if n>1 k=u(randi(n));u=[q(u(u<k)),q(u(u>=k))];end

Multi-line version:

function u=q(u) 
 n=numel(u);
 if n>1 
 k=u(randi(n));
 u=[q(u(u<k)),q(u(u>=k))];
 end

Answer 12

Julia, 83 bytes

Q(x)=endof(x)<2?x:(p=rand(x);[Q((f=filter)(i->i<p,x));f(i->i==p,x);Q(f(i->i>p,x))])

This creates a recursive function Q that accepts an array and returns an array. It does not conditionally use insertion sort, so no bonus applies.

Ungolfed:

function Q(x::AbstractArray)
 if endof(x) ≤ 1
 # Return on empty or 1-element arrays
 x
 else
 # Select a random pivot
 p = rand(x)
 # Return the function applied to the elements less than
 # the pivot concatenated with those equal to the pivot
 # and the function applied to those greater than the pivot
 [Q(filter(i -> i < p, x));
 filter(i -> i == p, x);
 Q(filter(i -> i > p, x))]
 end
end

Fixed an issue and saved some bytes thanks to Glen O!

• Glen O: Possible issues with loss of repeat elements (which already exist in your code) aside, you can save a few bytes here by assigning f when you first use filter, and using endof instead of length. Q(x)=endof(x)<2?x:(p=rand(x);[Q((f=filter)(i->i<p,x));p;Q(f(i->i>p,x))])
• Alex A.: @GlenO Thanks for the suggestion. I've implemented that and fixed the issue with repeated elements.
• Glen O: I said it could be an issue, but I asked the question poster for clarification, and "The input may contain decimal and negative values. However, there will be no duplicates"

Answer 13

R, 78 bytes

Q=function(x)if(length(x)>1)c(Q(x[x<(p=sample(x,1))]),x[x==p],Q(x[x>p]))else x

This creates a recursive function Q that accepts a vector and returns a vector. It does not conditionally apply insertion sort, so no bonus.

Ungolfed:

Q <- function(x) {
 # Check length
 if (length(x) > 1) {
 # Select a random pivot
 p <- sample(x, 1)
 # Recurse on the subarrays consisting of
 # elements greater than and less than p,
 # concatenate with those equal to p
 c(Q(x[x < p]), x[x == p], Q(x[x > p]))
 } else {
 x
 }
}

Try it online

Saved 4 bytes thanks to flodel!

• Miff: You can nibble a couple of bytes off by dropping the ">1" from the length comparison. This implicitly compares it to 0, but an extra layer of recursion isn't a problem,
• Alex A.: @Miff Thanks for your input but I tried that and it doesn't produce the expected result for me.

Answer 14

K, 41 bytes

s:{$[#x;(s@x@&x<p),p,s@x@&x>p:x@*1?#x;x]}

TAKE THAT, APL!!! Doesn't do any of the bonuses.

Answer 15

Tcl, 138 bytes

proc q v {if {$v eq {}} return
lassign {} a b
foreach x [lassign $v p] {if {$x<$p} {lappend a $x} {lappend b $x}}
concat [q $a] $p [q $b]}

This is an exceedingly standard quicksort.

The pivot is simply the first element of each subarray (I contend that this is a random number. https://xkcd.com/221/)

It isn't particularly efficient in terms of memory usage, though it could be improved some with tailcall on the second recursion and a base case of n<1 elements.

Here's the readable version:

proc quicksort xs {
 if {![llength $xs]} return
 set lhs [list]
 set rhs [list]
 foreach x [lassign $xs pivot] {
 if {$x < $pivot} \
 then {lappend lhs $x} \
 else {lappend rhs $x}
 }
 concat [quicksort $lhs] $pivot [quicksort $rhs]
}

Works on all input and permits duplicates. Oh, it's also stable. You can test it with something simple, like:

while 1 {
 puts -nonewline {xs? }
 flush stdout
 gets stdin xs
 if {$xs eq {}} exit
 puts [q $xs] ;# or [quicksort $xs]
 puts {}
}

Enjoy! :O)

• sergiol: You can save bytes replacing foreach by lmap

Answer 16

JavaScript (ES6), 191

Q=(a,l=0,h=a.length-1)=>l<h&&(p=((a,i,j,p=a[i+(0|Math.random()*(j-i))])=>{for(--i,++j;;[a[i],a[j]]=[a[j],a[i]]){while(a[--j]>p);while(a[++i]<p);if(i>=j)return j}})(a,l,h),Q(a,l,p),Q(a,p+1,h))

// More readable
U=(a,l=0,h=a.length-1)=>l<h && 
 (p=( // start of partition function
 (a,i,j,p=a[i+(0|Math.random()*(j-i))])=>
 {
 for(--i,++j;;[a[i],a[j]]=[a[j],a[i]])
 {
 while(a[--j]>p);
 while(a[++i]<p);
 if(i>=j)return j
 }
 } // end of partition function
 )(a,l,h),U(a,l,p),U(a,p+1,h))
// This is the shortest insertion sort that I could code, it's 72 bytes
// The bonus is worth ~30 bytes - so no bonus
I=a=>{for(i=0;++i<a.length;a[j]=x)for(x=a[j=i];j&&a[j-1]>x;)a[j]=a[--j]}
// TEST
z=Array(10000).fill().map(_=>Math.random()*10000|0)
Q(z)
O.innerHTML=z.join(' ')

<div id=O></div>

Answer 17

Ceylon (JVM only), (削除) 183 (削除ここまで) 170

No bonuses apply.

import ceylon.math.float{r=random}{Float*}q({Float*}l)=>if(exists p=l.getFromFirst((r()*l.size).integer))then q(l.filter((e)=>e<p)).chain{p,*q(l.filter((e)=>p<e))}else[];

It seems there is no cross-platform way to produce a random number in Ceylon, so this is JVM-only. (At the end I have a non-random version which works in JS too, and is smaller.)

This defines a function which takes an iterable of floats, and returns a sorted version thereof.

import ceylon.math.float {
 r=random
}
{Float*} q({Float*} l) {
 if (exists p = l.getFromFirst((r() * l.size).integer)) {
 return q(l.filter((e) => e < p)).chain { p, *q(l.filter((e) => p < e)) };
 } else {
 return [];
 }
}

If (against the specification) duplicate entries are passed, those will be filtered out.

This are 183 bytes: import ceylon.math.float{r=random}{Float*}q({Float*}l){if(exists p=l.getFromFirst((r()*l.size).integer)){return q(l.filter((e)=>e<p)).chain{p,*q(l.filter((e)=>p<e))};}else{return[];}}

We can improve a bit by using the new (Ceylon 1.2) if expression:

import ceylon.math.float {
 r=random
}
{Float*} q({Float*} l) =>
 if (exists p = l.getFromFirst((r() * l.size).integer))
 then q(l.filter((e) => e < p)).chain { p, *q(l.filter((e) => p < e)) }
 else [];

This is 170 bytes: import ceylon.math.float{r=random}{Float*}q({Float*}l)=>if(exists p=l.getFromFirst((r()*l.size).integer))then q(l.filter((e)=>e<p)).chain{p,*q(l.filter((e)=>p<e))}else[];

---

Here is a non-random version:

{Float*} r({Float*} l) =>
 if (exists p = l.first)
 then r(l.filter((e) => e < p)).chain { p, *r(l.filter((e) => p < e)) }
 else [];

Without spaces this would be 107 bytes: {Float*}r({Float*}l)=>if(exists p=l.first)then r(l.filter((e)=>e<p)).chain{p,*r(l.filter((e)=>p<e))}else[];

Answer 18

AutoIt, (削除) 320.45 (削除ここまで) 304.3 bytes

This is plenty fast (for AutoIt anyway). Qualifies for insertion sort bonus. Will add explanation after final golfing occurred.

Input is q(Array, StartingElement, EndingElement).

Func q(ByRef 1,ドル2,ドル3ドル)
5ドル=3ドル
$L=2ドル
6ドル=1ドル[(2ドル+3ドル)/2]
If 3ドル-2ドル<6 Then
For $i=2ドル+1 To 3ドル
4ドル=1ドル[$i]
For $j=$i-1 To 2ドル Step -1
5ドル=1ドル[$j]
ExitLoop 4ドル>=5ドル
1ドル[$j+1]=5ドル
Next
1ドル[$j+1]=4ドル
Next
Else
Do
While 1ドル[$L]<6ドル
$L+=1
WEnd
While 1ドル[5ドル]>6ドル
5ドル-=1
WEnd
ContinueLoop $L>5ドル
4ドル=1ドル[$L]
1ドル[$L]=1ドル[5ドル]
1ドル[5ドル]=4ドル
$L+=1
5ドル-=1
Until $L>5ドル
q(1,ドル2,ドル5ドル)
q(1,ドル$L,3ドル)
EndIf
EndFunc

Random test input + output:

862, 543, 765, 577, 325, 664, 503, 524, 192, 904, 143, 483, 146, 794, 201, 511, 199, 876, 918, 416
143, 146, 192, 199, 201, 325, 416, 483, 503, 511, 524, 543, 577, 664, 765, 794, 862, 876, 904, 918

• Daniel M.: Interesting, never heard of AutoIt before

Answer 19

Java, 346 bytes

407 bytes - 15% bonus for insertion sort = 345.95 bytes

Compressed Code:

class z{Random r=new Random();void q(int[] a){q(a,0,a.length);}void q(int[] a,int b,int e){if(e-b<6){for(int i=b;i<e;i++){for(int j=i;j>0&a[j]<a[j-1];j--){s(a,j,j-1);}}return;}int s=p(a,b,e);q(a,b,s);q(a,s,e);}int p(int[] a,int b,int e){int p=a[r.nextInt(e-b)+b--];while(b<e){do{b++;}while(a[b]<p);do{e--;}while(a[e]>p);if(b<e){s(a,b,e);}}return b;}void s(int[] a,int b,int e){int t=a[b];a[b]=a[e];a[e]=t;}}

Full Code:

public class QuickSort {
 private static final Random RANDOM = new Random();
 public static void quickSort(int[] array) {
 quickSort(array, 0, array.length);
 }
 private static void quickSort(int[] array, int begin, int end) {
 if (end - begin <= 5) {
 for (int i = begin; i < end; i++) {
 for (int j = i; j > 0 && array[j] < array[j - 1]; j--) {
 swap(array, j, j - 1);
 }
 }
 return;
 }
 int splitIndex = partition(array, begin, end);
 quickSort(array, begin, splitIndex);
 quickSort(array, splitIndex, end);
 }
 private static int partition(int[] array, int begin, int end) {
 int pivot = array[RANDOM.nextInt(end - begin) + begin];
 begin--;
 while (begin < end) {
 do {
 begin++;
 } while (array[begin] < pivot);
 do {
 end--;
 } while (array[end] > pivot);
 if (begin < end) {
 // Make sure they haven't crossed yet
 swap(array, begin, end);
 }
 }
 return begin;
 }
 private static void swap(int[] array, int begin, int end) {
 int temp = array[begin];
 array[begin] = array[end];
 array[end] = temp;
 }
}

• Blue: Couple improvements: 1. get rid of the spaces between int[] and a in the method header. 2. Make the increment or decrement in a for loop the last place a variable is accessed. 3. Make a class int (or a couple) to save bytes by using it instead of a new int. 4. Using Math.random() and casting might be shorter than making a Random object.

Answer 20

Mathematica, (削除) 93 (削除ここまで) 90 bytes

If[Length@#>1,pv=RandomChoice@#;Join[qs2[#~Select~(#<pv&)],{pv},qs2[#~Select~(#>pv&)]],#]&

No bonus, haven't got a minimal way to do insertion sort yet. When I was learning C++ recently, I did a comparison of various sorting algorithms here.

Answer 21

Python2, 120 bytes

def p(a):
 if[]==a[1:]:return a
 b,c,m=[],[],__import__("random").choice(a)
 for x in a:[b,c][x>m]+=[x];return p(b)+p(c)

if[]==a[1:] is exactly as long as if len(a)>2 but looks more golfed.

Answer 22

Lua, 242 Bytes

function f(t,p)if(#t>0)then local P,l,r,i=math.random(#t),{},{},table.insert p=t[P]for k,v in ipairs(t)do if(k~=P)then i(v<p and l or r,v)end end t={}for k,v in pairs(f(l))do i(t,v)end i(t,p)for k,v in pairs(f(r))do i(t,v)end end return t end

Ungolfed & Explination

function f(t,p) # Assign 'p' here, which saves two bytes, because we can't assign it to t[P] IN the local group.
 if(#t>0)then # Just return 0 length lists...
 local P,l,r,i=math.random(#t),{},{},table.insert # Using local here actually makes the a,b=1,2 method more efficient here. Which is unnormal for Lua
 p = t[P] # P is the index of the pivot, p is the value of the pivot, l and r are the sub-lists around the pivot, and i is table.insert to save bytes.
 for k,v in ipairs(t) do # We use a completely random pivot, because it's cheaper on the bytes.
 if(k~=P)then # Avoid 'sorting' the pivot.
 i(v<p and l or r,v) # If the value is less than the pivot value, push it to the left list, otherwise, push it to the right list.
 end #
 end #
 t = {} # We can re-use t here, because we don't need it anymore, and it's already a local value. Saving bytes!
 for k,v in pairs(f(l)) do # Quick sort the left list, then append it to the new output list.
 i(t,v) #
 end #
 i(t,p) # Append the pivot value.
 for k,v in pairs(f(r)) do # Ditto the right list.
 i(t,v) #
 end #
 end #
 return t # Return...
end #

Answer 23

Racket 121 bytes

(λ(l)(if(null? l)l(let((h(car l))(t(cdr l)))(append(qs (filter(λ(x)(< x h))t))(list h)(qs (filter(λ(x)(>= x h))t))))))

Ungolfed (l=list, h=head (first element), t=tail (rest or remaining elements)):

(define qs
 (λ(l)
 (if (null? l) l
 (let ((h (first l))
 (t (rest l)))
 (append (qs (filter (λ(x) (< x h) ) t))
 (list h) 
 (qs (filter (λ(x) (>= x h)) t)) )))))

Testing:

(qs (list 5 8 6 8 9 1 2 4 9 3 5 7 2 5))

Output:

'(1 2 2 3 4 5 5 5 6 7 8 8 9 9)

Answer 24

Japt, 23 bytes

Each bonus would need to be three bytes or less to pay off in the total score, so I didn't take any bonuses.

Z=Uö;Ê<2?U:ßUf<Z)cßUf ̈Z
Z=Uö; // Take a random element from the input for partitioning.
 Ê<2 // If the input is shorter than two elements,
 ?U // return it.
 : // Otherwise
 ß ß // recursively run again
 Uf<Z // with both items that are smaller than the partition
 Uf ̈Z // and those that are larger or equal,
 )c // returning the combined result.

Try it online!

• Shaggy: 20 bytes

Answer 25

JavaScript (ES6), 96 bytes

const q=([p,...r])=>typeof p==='undefined'?[]:[...q(r.filter(e=>e<p)),p,...q(r.filter(e=>e>=p))]

If you consider that taking the first element of an unsorted array is exactly the same as choosing an element at random.

• Weird Glyphs: Hi there, and welcome to Code Golf Stack Exchange! Not bad for a first answer, but I'm pretty sure that the challenge does not allow to always use the first element as pivot: The pivot should be chosen at random or with median of three (1st, last, and middle element).. You can look at other answers that could have been shorter if this was allowed.