HN Explorer

19 comments

[ 3.3 ms ] story [ 42.3 ms ] thread
kazinator
> L=`qsort $L`

POSIX has standardized $(qsort $L) syntax since 1990. It's okay to use it now.

zura
Maybe we should all learn to always prepend "Pseudo" to these "quicksorts"?
sp332
Is it not really a quicksort?
cornewut
I guess he meant pseudo 3 lines.
zura
I meant that the canonical quicksort algorithm which Hoare came up uses in-place partitioning. Probably you can still call "quicksort" to these nice snippets (be it in Prolog, Erlang or Haskell), but mentioning the fact about the deviation from the canonical implementation could be useful for readers.
p4bl0
It's a bad implementation of it, see jmount's comment.
bunfun
Hey, check out this 1-liner HTTP server!

:%s/\n/ /g

readerrrr
A couple of characters less in C ( I didn't count whitespace in both ):

void qs( int* a , int z )

{

if(z > 1){ ; int p = a[z/2], s = 0, e = z-1, t; while(s <= e) {

for(;a[s] < p; s++); for(;a[e] > p; e--); if(s <= e) { t = a[s];

a[s++] = a[e]; a[e--] = t; } } qs( a , e+1 ); qs( a+s , z-s ); }

}

[deleted]
(comment deleted)
darkstar999
Let me fix that for you.

    qsort(){
        local L="";
        local G="";
        [ $# -eq 1 ] && echo $1 && return;
        P=$1; 
        shift; 
        for i in $@; do 
            [ $i -lt $P ] && L="$L $i" || G="$G $i"; 
        done
        [ -z "$L" ] || L=`qsort $L`; 
        [ -z "$G" ] || G=`qsort $G`; 
        echo "$L $P $G"
    }
    qsort $@
Looks more like 14 lines to me.
[deleted]
(comment deleted)
kazinator
Also: what? No median-of-three pivot selection?

  # these lines replace "P=$1" line:

  local first=$1
  eval local last=\${$#}
  eval local mid=\${$((($#+1)/2))}

  if [ $first -le $mid ] ; then
    if [ $mid -le $last ] ; then
      P=$mid
    elif [ $first -le $last ] ; then
      P=$last
    else
      P=$first
    fi
  else
    if [ $first -le $last ] ; then
      P=$first
    elif [ $mid -le $last ] ; then
      P=$last
    else
      P=$mid
    fi
  fi
That little enhancement blows up the LOC quite a bit. :)
kazinator
Also, suppose we abstract the operators a little bit:

  if [ $x $LT $y ] ; ...
If we set LT to "-lt" we get numeric comparison.

Change it to "-ot" and we can order paths by modification timestamp.

Set LT to "<" and obtain lexicographic sorting on strings.

mesozoic
It's not 3 commands so I'm sure you can get it down to 1 line.
jmount
The time complexity looks very bad (assuming I can read shell, which I am not sure about).

First it appears it has the classic bug of passing items equal to the partition to sub-sorts (G in this case). This guarantees N recurses (and at least c N^2 operations) when trying to sort an array that is all duplicates of a single value. Also the list concatenations ( L="$L $i" and G="$G $i") which often make mere list assembly take c N^2 time (pretty much forced by the string representations). So this could be a c N^3 worst-case sorting algorithm (possibly worse than bubble sort).

One of my articles on the pain of quicksort: http://www.win-vector.com/blog/2008/04/sorting-in-anger/

wyc
Haha, there are few places where this submission would result in such a decent analysis. Thanks.
pdkl95
https://gist.github.com/pdkl95/e97749edc3ba58825a16#file-bas...

I what must be a lapse of sanity, I wrote mergesort. It is quite a bit more than 3 - err, 14 - lines, but it does include an option to see view the array nesting.

It uses slightly better array management... and then throws out any gains by rebuilding a new array every time an element is shift off the front.

// for when you really don't want to use sort(1)