Bueno ... hay 59 (ahora 60) preguntas etiquetadas ordenando , pero no hay respuestas rápidas simples.

Eso debe ser arreglado.

Para aquellos que no están familiarizados con la clasificación rápida , aquí hay un desglose, cortesía de Wikipedia:

1. Elige un elemento, llamado pivote , de la matriz.
2. Reordene la matriz para que todos los elementos con valores menores que el pivote estén antes del pivote, mientras que todos los elementos con valores mayores que el pivote vienen después (los valores iguales pueden ir en cualquier dirección). Después de esta partición, el pivote está en su posición final. Esto se llama la operación de partición.
3. Aplique recursivamente los pasos anteriores a la submatriz de elementos con valores más pequeños y separadamente a la submatriz de elementos con valores más grandes.

Reglas

Las reglas son simples:

• Implemente una selección rápida numérica en el lenguaje de programación que elija.
• El pivote debe elegirse al azar o con una mediana de tres (1er, último y medio elemento).
• Su programa puede ser un programa o función completa.
• Puede obtener la entrada utilizando STDIN, argumentos de línea de comando o parámetros de función. Si usa una entrada de cadena, la entrada está separada por espacios.
• La entrada puede contener valores decimales y negativos. Sin embargo, no habrá duplicados.
• Puede enviar a STDOUT o regresando de la función.
• Sin funciones de clasificación incorporadas (o relacionadas con la clasificación) o lagunas estándar.
• La lista puede tener una longitud arbitraria.

Bonificación n. ° 1: en las listas o sublistas de longitud <= 5, utilice la ordenación por inserción para acelerar un poco las cosas. Recompensa: -15%.

Bono # 2: si su idioma admite concurrencia, ordene la lista en paralelo. Si está utilizando una ordenación por inserción en sublistas, la ordenación por inserción final no necesita estar en paralelo. Se permiten agrupaciones de subprocesos / programación de subprocesos incorporados. Recompensa: -15%.

Nota: La mediana de tres confundía a algunas personas, así que aquí hay una explicación, cortesía de (nuevamente) Wikipedia:

elegir la mediana del primer, medio y último elemento de la partición para el pivote

Tanteo

Este es el código de golf . La puntuación base está en bytes. Si tienes una bonificación, obtén un 15% de descuento en ese número. Si tiene ambos, obtenga un 30% de descuento. Eso realmente suena como un argumento de venta.

No se trata de encontrar la respuesta más corta en general, sino la más corta en cada idioma.

Y ahora, una copia descarada del fragmento de la tabla de clasificación.

La tabla de posiciones

El Fragmento de pila al final de esta publicación genera el catálogo a partir de las respuestas a) como una lista de la solución más corta por idioma yb) como una tabla de clasificación general.

Para asegurarse de que su respuesta se muestre, comience con un título, utilizando la siguiente plantilla de Markdown:

## Language Name, N bytes

donde N es el tamaño de su envío. Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:

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

Si desea incluir varios números en su encabezado (por ejemplo, porque su puntaje es la suma de dos archivos o desea enumerar las penalizaciones de la bandera del intérprete por separado), asegúrese de que el puntaje real sea el último número en el encabezado:

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

También puede hacer que el nombre del idioma sea un enlace que luego aparecerá en el fragmento:

## [><>](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>

C ++, 440.3 405 388 bytes

518 bytes - 15% de bonificación por clasificación de inserción = 440.3 bytes

477 bytes - 15% de bonificación por clasificación de inserción = 405.45 bytes

474 bytes - 15% de bonificación por clasificación de inserción = 402.9 bytes

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

Gracias a @Luke por guardar 3 bytes (2 realmente).

Gracias a @ Dúthomhas por guardar 18 (15 realmente) bytes.

Tenga en cuenta que soy nuevo aquí y esta es mi primera publicación.

Este es un .harchivo (encabezado).

Código comprimido:

#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);}

Código completo:

#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);
}

APL, 49 42 bytes

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

Esto crea una función monádica recursiva sin nombre que acepta una matriz a la derecha. No califica para el bono.

Explicación:

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

Pruébalo en línea

¡Se solucionó un problema (al costo de 8 bytes) gracias a marinus y se guardaban 7 bytes gracias a Thomas Kwa!

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;}

Con espacios en blanco:

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;
}

Pyth, 25 bytes

L?tbsyMa_,]JObf<TJbf>TJbb

Esto define una función y , que toma una lista de números como entrada.

Pruébalo en línea: demostración

Explicación

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 (probablemente no válido)

Utilizo el método "agrupar por", que internamente utiliza una ordenación. Lo uso para dividir la lista original en tres sublistas (todos los elementos más pequeños que el pivote, el pivote y todos los elementos más grandes que el pivote). Sin la clasificación en "agrupar", podría devolver estas 3 listas en un orden diferente.

Como se dijo, esto probablemente no sea válido. Sin embargo, lo mantendré aquí, porque es una solución interesante.

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

Pruébelo en línea: demostración

Explicación

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

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

Esto me llevó mucho tiempo escribir. Puedes probarlo aquí , simplemente coloque la lista que debe clasificarse en la pila inicial, separada por comas, antes de ejecutar el programa.

Cómo funciona

El programa toma el primer, medio y último elemento en la pila inicial y calcula la mediana de estos tres.
Luego cambia la pila a:

Elemento [lista 1] [lista 2]

donde todo en la lista 1 es más pequeño o igual al elemento y todo en la lista 2 es más grande.
Repite este proceso de forma recursiva en la lista 1 y la lista 2 hasta que toda la lista esté ordenada.

CJam, 40 bytes

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

Esta es una función con nombre que espera una matriz en la pila y empuja una a cambio.

Pruébelo en línea en el intérprete de CJam .

El código anterior sigue la especificación lo más cerca posible. Si eso no es necesario, se pueden guardar 12 bytes:

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

Python 3, 123 , 122.

Guardado 1 byte gracias a Aaron.

Esta es la primera vez que me he molestado en escribir un algoritmo de clasificación. En realidad es un poco más fácil de lo que pensé que sería.

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

Sin golf:

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)

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)));}

Explicación

//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)));
}

Rubí, 87 60 bytes

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

Sin golf:

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

Prueba:

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]

Octava, 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

Versión multilínea:

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

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

Esto crea una función recursiva Q que acepta una matriz y devuelve una matriz. No utiliza condicionalmente el orden de inserción, por lo que no se aplica ninguna bonificación.

Sin golf:

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

Se solucionó un problema y se guardaban algunos bytes gracias a Glen O!

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

Esto crea una función recursiva Qque acepta un vector y devuelve un vector. No aplica condicionalmente el orden de inserción, por lo que no hay bonificación.

Sin golf:

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
    }
}

Pruébalo en línea

¡Guardado 4 bytes gracias a flodel!

K, 41 bytes

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

TOMA ESO, APL !!! No hace ninguna de las bonificaciones.

Haskell 137136 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))

A continuación se incluye la versión no protegida, con nombres de variables y funciones expandidos y algunos resultados intermedios agregados:

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

Aprovecho el hecho de que no hay duplicados para usar dos comparaciones estrictas. Sin Data.List.partitionembargo, tendré que verificar si no acorta las cosas, incluso teniendo en cuenta que tendría que agregar una declaración de importación. No estoy tomando el bono de clasificación de inserción porque lo considero Data.List.insertcomo una función relacionada con la clasificación, por lo tanto prohibido, y si no lo uso, agregar el orden de inserción empuja el código a 246 bytes, 209.1 con el bono, por lo que no vale la pena.

Editar: Gracias a RobAu por su sugerencia de crear un alias para usar f=filter. Puede guardar solo un byte, pero todo ayuda.

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]}

Este es un quicksort extremadamente estándar.

El pivote es simplemente el primer elemento de cada subconjunto (sostengo que este es un número aleatorio. Https://xkcd.com/221/ )

No es particularmente eficiente en términos de uso de memoria, aunque podría mejorarse algunos con tailcall la segunda recursión y un caso base de n <1 elementos.

Aquí está la versión legible:

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]
}

Funciona en todas las entradas y permite duplicados. Oh, también es estable . Puedes probarlo con algo simple, como:

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

¡Disfrutar! : O)

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>

Ceilán (solo JVM), 183 170

No se aplican bonificaciones.

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[];

Parece que no hay una forma multiplataforma para producir un número aleatorio en Ceilán, por lo que esto es solo para JVM. (Al final tengo una versión no aleatoria que también funciona en JS y es más pequeña).

Esto define una función que toma un iterativo de flotantes y devuelve una versión ordenada de la misma.

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 [];
    }
}

Si (contra la especificación) se pasan entradas duplicadas, se filtrarán.

Estos son 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[];}}

Podemos mejorar un poco usando la nueva ifexpresión (Ceylon 1.2) :

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 [];

Esto es 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[];

Aquí hay una versión no aleatoria:

{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 [];

Sin espacios esto sería 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[];

AutoIt , 320.45 304.3 bytes

Esto es bastante rápido (para AutoIt de todos modos). Califica para la bonificación por clasificación de inserción. Agregará una explicación después de que ocurrió el golf final.

Entrada es 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

Prueba aleatoria entrada + salida:

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

Java, 346 bytes

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

Código comprimido:

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;}}

Código completo:

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;
    }

}

Mathematica, 93 90 bytes

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

Sin bonificación, todavía no tengo una forma mínima de ordenar la inserción. Cuando estaba aprendiendo C ++ recientemente, hice una comparación de varios algoritmos de clasificación aquí .

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:]es exactamente tan largo como if len(a)>2pero parece más golfizado.

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

Sin Golf y Explicación

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                                                         #

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

Sin golf (l = lista, h = cabeza (primer elemento), t = cola (resto o elementos restantes)):

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

Pruebas:

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

Salida:

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

Japt , 23 bytes

Cada bono tendría que ser de tres bytes o menos para pagar el puntaje total, por lo que no tomé ningún bono.

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.

Pruébalo en línea!