27
\$\begingroup\$

Well... there are 59 (now 60) questions tagged , 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 . 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>

\$\endgroup\$
  • 4
    \$\begingroup\$ "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. \$\endgroup\$ – msh210 Nov 1 '15 at 14:51
  • 2
    \$\begingroup\$ @daniero Snippet is fixed now \$\endgroup\$ – Daniel M. Nov 1 '15 at 19:15
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – John Dvorak Nov 2 '15 at 8:57
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – John Dvorak Nov 2 '15 at 12:05
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – John Dvorak Nov 2 '15 at 12:16

24 Answers 24

10
\$\begingroup\$

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);
}
\$\endgroup\$
  • 5
    \$\begingroup\$ 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) \$\endgroup\$ – edc65 Nov 1 '15 at 11:01
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – cadaniluk Nov 1 '15 at 15:32
  • 2
    \$\begingroup\$ You don't need a space after #include. \$\endgroup\$ – Luke Nov 2 '15 at 15:56
  • \$\begingroup\$ Get rid of 34 bytes by removing the call to srand(time(NULL)); You'll still get pseudo-random numbers from rand(). \$\endgroup\$ – Dúthomhas Mar 28 '16 at 2:47
9
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ The question specifies there will be no duplicates. (Don't know how it took me so long to see that...) \$\endgroup\$ – lirtosiast Nov 8 '15 at 20:01
5
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ 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)'. \$\endgroup\$ – Chris Jefferson Nov 2 '15 at 9:23
  • \$\begingroup\$ Eliminating the erase allowed me to save a lot of bytes. Thank you! \$\endgroup\$ – Lynn Nov 2 '15 at 12:11
  • \$\begingroup\$ One other tiny one: No need to assign 'r=q(r)', just use 'for(y:q(r))', but that's all I can see! \$\endgroup\$ – Chris Jefferson Nov 2 '15 at 12:19
  • \$\begingroup\$ Just out of curiosity: where is C++17 in particular used here? \$\endgroup\$ – kirbyfan64sos Nov 2 '15 at 22:55
  • 1
    \$\begingroup\$ 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.) \$\endgroup\$ – Lynn Nov 2 '15 at 22:59
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ 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). \$\endgroup\$ – VisualMelon Nov 16 '15 at 14:03
  • \$\begingroup\$ @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. \$\endgroup\$ – Morgan Thrapp Nov 16 '15 at 14:04
  • \$\begingroup\$ 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. \$\endgroup\$ – VisualMelon Nov 16 '15 at 14:05
  • \$\begingroup\$ @VisualMelon Well, sure, but it then recursively sorts again. \$\endgroup\$ – Morgan Thrapp Nov 16 '15 at 14:06
  • \$\begingroup\$ Ah, sorry, missed that completely, not quite how I would expect a Quicksort to be implemented - have an upvote for confusing me \$\endgroup\$ – VisualMelon Nov 16 '15 at 14:08
2
\$\begingroup\$

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)));
}
\$\endgroup\$
  • \$\begingroup\$ ES6 could probably shorten this. \$\endgroup\$ – Nissa May 3 '18 at 19:24
1
\$\begingroup\$

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]
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 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))]) \$\endgroup\$ – Glen O Nov 1 '15 at 8:58
  • \$\begingroup\$ @GlenO Thanks for the suggestion. I've implemented that and fixed the issue with repeated elements. \$\endgroup\$ – Alex A. Nov 3 '15 at 0:04
  • \$\begingroup\$ 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" \$\endgroup\$ – Glen O Nov 3 '15 at 5:22
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 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, \$\endgroup\$ – Miff Nov 2 '15 at 10:25
  • \$\begingroup\$ @Miff Thanks for your input but I tried that and it doesn't produce the expected result for me. \$\endgroup\$ – Alex A. Nov 2 '15 at 15:48
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ f=filter might shave off some bytes. \$\endgroup\$ – RobAu Feb 26 '16 at 14:46
  • \$\begingroup\$ 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? \$\endgroup\$ – Cyoce Mar 28 '16 at 18:47
1
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ You can save bytes replacing foreach by lmap \$\endgroup\$ – sergiol Apr 30 '17 at 12:00
1
\$\begingroup\$

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>

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Interesting, never heard of AutoIt before \$\endgroup\$ – Daniel M. Nov 1 '15 at 2:04
0
\$\begingroup\$

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

}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Blue Mar 28 '16 at 1:10
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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                                                         #
\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 20 bytes \$\endgroup\$ – Shaggy May 14 '18 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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