Cóż ... istnieje 59 (obecnie 60) pytań oznaczonych sortowaniem , ale nie ma prostych szybkich sortowań.

To musi zostać naprawione.

Dla tych, którzy nie znają quicksort , oto podział, dzięki uprzejmości Wikipedia-

1. Wybierz element zwany osią przestawną z tablicy.
2. Zmień kolejność tablic, aby wszystkie elementy o wartościach mniejszych niż pivot znajdowały się przed pivotem, a wszystkie elementy o wartościach większych niż pivot pojawiały się po nim (równe wartości mogą iść w obie strony). Po tym podziale punkt obrotu znajduje się w końcowej pozycji. Nazywa się to operacją partycji.
3. Rekurencyjnie zastosuj powyższe kroki do podgrupy elementów o mniejszych wartościach i osobno do podgrupy elementów o większych wartościach.

Zasady

Zasady są proste:

• Zaimplementuj numeryczne szybkie sortowanie w wybranym języku programowania.
• Czop powinien być wybrany losowo lub z medianą trzech (pierwszy, ostatni i środkowy element).
• Twój program może być kompletnym programem lub funkcją.
• Dane wejściowe można uzyskać za pomocą STDIN, argumentów wiersza poleceń lub parametrów funkcji. Jeśli używasz ciągu wejściowego, dane wejściowe są rozdzielane spacjami.
• Dane wejściowe mogą zawierać wartości dziesiętne i ujemne. Jednak nie będzie duplikatów.
• Możesz wyprowadzać dane do STDOUT lub wracając z funkcji.
• Brak wbudowanych funkcji sortowania (lub związanych z sortowaniem) lub standardowych luk.
• Lista może mieć dowolną długość.

Premia # 1: Na listach lub sublistach o długości <= 5 użyj sortowania wstawiania, aby nieco przyspieszyć. Nagroda: -15%.

Premia 2: Jeśli twój język obsługuje współbieżność, posortuj listę równolegle. Jeśli używasz sortowania wstawiania na podlistach, ostateczne sortowanie wstawiania nie musi być równoległe. Dozwolone są wbudowane pule wątków / planowanie wątków. Nagroda: -15%.

Uwaga: Mediana z trzech była myląca dla niektórych osób, więc oto wyjaśnienie, dzięki (ponownie) Wikipedii:

wybór mediany pierwszego, środkowego i ostatniego elementu przegrody dla osi przestawnej

Punktacja

To jest golf golfowy . Podstawowy wynik jest w bajtach. Jeśli masz jeden bonus, weź 15% zniżki na ten numer. Jeśli masz oba, weź 30% zniżki. To naprawdę brzmi jak sprzedaż.

Nie chodzi o to, by znaleźć najkrótszą odpowiedź w ogóle, ale raczej najkrótszą w każdym języku.

A teraz bezwstydna kopia fragmentu tabeli wyników.

Tabela liderów

Fragment kodu na dole tego postu generuje katalog na podstawie odpowiedzi a) jako listy najkrótszych rozwiązań dla każdego języka oraz b) jako ogólnej tabeli wyników.

Aby upewnić się, że Twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:

## Language Name, N bytes

gdzie N jest rozmiarem twojego zgłoszenia. Jeśli poprawisz swój wynik, możesz zachować stare wyniki w nagłówku, przekreślając je. Na przykład:

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

Jeśli chcesz umieścić w nagłówku wiele liczb (np. Ponieważ twój wynik jest sumą dwóch plików lub chcesz osobno wymienić kary za flagi tłumacza), upewnij się, że rzeczywisty wynik jest ostatnią liczbą w nagłówku:

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

Możesz także ustawić nazwę języka jako link, który pojawi się we fragmencie:

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

518 bajtów - 15% premii za sortowanie za wstawienie = 440,3 bajtów

477 bajtów - 15% premii za sortowanie za wstawienie = 405,45 bajtów

474 bajty - 15% premii za sortowanie za wstawienie = 402,9 bajtów

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

Dzięki @Luke za oszczędność 3 bajtów (naprawdę 2).

Dzięki @ Dúthomhas za uratowanie 18 (15 naprawdę) bajtów.

Pamiętaj, że jestem tu nowy i to jest mój pierwszy post.

To jest plik .h(nagłówek).

Skompresowany kod:

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

Pełny kod:

#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 bajtów

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

Tworzy to bezimienną rekurencyjną funkcję monadyczną, która akceptuje tablicę po prawej stronie. Nie kwalifikuje się do premii.

Wyjaśnienie:

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

Wypróbuj online

Naprawiono problem (kosztem 8 bajtów) dzięki marinus i zapisano 7 bajtów dzięki Thomasowi Kwa!

C ++ 17, 254 199 195 bajtów

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

Z białymi znakami:

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 bajtów

L?tbsyMa_,]JObf<TJbf>TJbb

Definiuje funkcję y, która pobiera listę liczb jako dane wejściowe.

Wypróbuj online: demonstracja

Wyjaśnienie

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 bajtów (prawdopodobnie nieprawidłowy)

Używam metody „grupuj według”, która wewnętrznie używa sortowania. Używam go, aby podzielić oryginalną listę na trzy listy podrzędne (wszystkie elementy mniejsze niż pivot, pivot i wszystkie elementy większe niż pivot). Bez sortowania według „grupowania według” mogłoby zwrócić te 3 listy w innej kolejności.

Jak powiedziano, jest to prawdopodobnie nieprawidłowa. Niemniej jednak zatrzymam go tutaj, ponieważ jest to interesujące rozwiązanie.

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

Wypróbuj online: demonstracja

Wyjaśnienie

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

> <> (Ryba), 313 309 bajtów

!;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.

Pisanie zajęło mi bardzo dużo czasu. Możesz spróbować tutaj , po prostu umieść listę, którą należy posortować, na początkowym stosie, oddzielając ją przecinkami, przed uruchomieniem programu.

Jak to działa

Program pobiera pierwszy, środkowy i ostatni element ze stosu początkowego i oblicza medianę tych trzech.
Następnie zmienia stos na:

[lista 1] element [lista 2]

gdzie wszystko na liście 1 jest mniejsze lub równe elementowi, a wszystko na liście 2 jest większe.
Rekurencyjnie powtarza ten proces na liście 1 i liście 2, dopóki cała lista nie zostanie posortowana.

CJam, 40 bajtów

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

Jest to nazwana funkcja, która oczekuje tablicy na stosie i wypycha ją w zamian.

Wypróbuj online w interpretatorze CJam .

Powyższy kod jest zgodny ze specyfikacją tak dokładnie, jak to możliwe. Jeśli nie jest to wymagane, można zapisać 12 bajtów:

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

Python 3, 123 , 122.

Zaoszczędził 1 bajt dzięki Aaronowi.

To pierwszy raz, kiedy tak naprawdę zadałem sobie trud napisania algorytmu sortowania. To jest trochę łatwiejsze, niż się spodziewałem.

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

Nie golfowany:

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

Wyjaśnienie

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

Rubin, 87 60 bajtów

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

Nie golfowany:

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]

Oktawa, 76 75 bajtów

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

Wersja wieloliniowa:

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 bajty

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

Tworzy to funkcję rekurencyjną, Qktóra akceptuje tablicę i zwraca tablicę. Nie korzysta z warunkowego sortowania, więc nie obowiązuje żadna premia.

Nie golfowany:

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

Naprawiono problem i zapisywano niektóre bajty dzięki Glen O!

R, 78 bajtów

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

Tworzy to funkcję rekurencyjną, Qktóra akceptuje wektor i zwraca wektor. Nie warunkowo stosuje sortowania wstawiania, więc nie ma premii.

Nie golfowany:

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

Wypróbuj online

Zaoszczędź 4 bajty dzięki flodel!

K, 41 bajtów

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

ZRÓB TO, APL !!! Nie robi żadnej z premii.

Haskell, 137136 bajtów

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

Wersja bez golfa jest poniżej, z rozszerzonymi nazwami zmiennych i funkcji oraz dodanymi niektórymi wynikami pośrednimi:

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

Korzystam z faktu, że nie ma duplikatów, aby użyć dwóch ścisłych porównań. Będę musiał sprawdzić, czy Data.List.partitionto nie skraca rzeczy, nawet biorąc pod uwagę, że musiałbym dodać instrukcję importu. Nie biorę premii za Data.List.insertsortowanie za wstawianie, ponieważ uważam ją za funkcję związaną z sortowaniem - w związku z tym jest zabroniona - a jeśli jej nie używam, dodanie sortowania za wstawianie przesuwa kod do 246 bajtów, 209,1 z premią, więc nie jest tego warte.

Edycja: Podziękowania dla RobAu za sugestię utworzenia aliasu do użycia f=filter. Może zaoszczędzić tylko jeden bajt, ale wszystko pomaga.

Tcl, 138 bajtów

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

Jest to niezwykle standardowy Quicksort.

Oś jest po prostu pierwszym elementem każdej podtablicy (twierdzę, że jest to liczba losowa. Https://xkcd.com/221/ )

Nie jest szczególnie wydajny pod względem wykorzystania pamięci, chociaż można go poprawić dzięki tailcalldrugiej rekurencji i przypadkowi podstawowemu elementów n <1.

Oto czytelna wersja:

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

Działa na wszystkich danych wejściowych i zezwala na duplikaty. Och, to także stabilne . Możesz to przetestować za pomocą czegoś prostego, na przykład:

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

Cieszyć się! : 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>

Ceylon (tylko JVM), 183 170

Nie obowiązują żadne bonusy.

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

Wygląda na to, że nie ma wieloplatformowego sposobu generowania losowej liczby na Cejlonie, więc jest to tylko JVM. (Na koniec mam nieprzypadkową wersję, która działa również w JS i jest mniejsza.)

Definiuje funkcję, która pobiera iterowalną liczbę zmiennoprzecinkową i zwraca jej posortowaną wersję.

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

Jeśli (zgodnie ze specyfikacją) zduplikowane wpisy zostaną przekazane, zostaną one odfiltrowane.

Są to 183 bajty: 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[];}}

Możemy nieco poprawić, używając nowego ifwyrażenia (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 [];

To jest 170 bajtów: 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[];

Oto wersja nieprzypadkowa:

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

Bez spacji byłoby to 107 bajtów: {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 bajtów

To dość szybko (w każdym razie dla AutoIt). Kwalifikuje się do premii za sortowanie za wstawianie. Dodam wyjaśnienie po zakończeniu gry w golfa.

Dane wejściowe to 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

Losowe wejście testowe + wyjście:

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 bajtów

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

Skompresowany kod:

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

Pełny kod:

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 bajtów

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

Brak premii, nie mam jeszcze minimalnego sposobu na sortowanie przez wstawianie. Kiedy uczyłem się C ++ niedawno zrobiłem porównanie różnych algorytmów sortowania tutaj .

Python2, 120 bajtów

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:]jest dokładnie tak długi, if len(a)>2ale wygląda bardziej golfowo.

Lua, 242 bajtów

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

Niegolfowane i wyjaśnienia

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                                                         #

Rakieta 121 bajtów

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

Niegolfowany (l = lista, h = głowa (pierwszy element), t = ogon (reszta lub pozostałe elementy)):

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

Testowanie:

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

Wydajność:

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

Japt , 23 bajty

Każdy bonus musiałby mieć trzy bajty lub mniej, aby spłacić całkowity wynik, więc nie wziąłem żadnych bonusów.

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.

Wypróbuj online!