4 ms·

Quicksort in 3 lines of shell

31 points by wyc 12y ago

jmount 12y ago
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/ http://www.win-vector.com/blog/2008/04/sorting-in-anger/
- wyc 12y ago
  Haha, there are few places where this submission would result in such a decent analysis. Thanks.
ozcanesen 12y ago
Reminds me http://bash.org/?464385 http://bash.org/?464385
- im2w1l 12y ago
  Well do be fair none of the commands in this quicksort require user input at least :)
kazinator 12y ago
> L=`qsort $L` POSIX has standardized $(qsort $L) syntax since 1990. It's okay to use it now.
zura 12y ago
Maybe we should all learn to always prepend "Pseudo" to these "quicksorts"?
- sp332 12y ago
  Is it not really a quicksort?
  - cornewut 12y ago
    I guess he meant pseudo 3 lines.
  - zura 12y ago
    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 12y ago
    It's a bad implementation of it, see jmount's comment.
bunfun 12y ago
Hey, check out this 1-liner HTTP server! :%s/\n/ /g
readerrrr 12y ago
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 12y ago
[deleted]
darkstar999 12y ago
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 12y ago
  [deleted]
- kazinator 12y ago
  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 12y ago
    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 12y ago
It's not 3 commands so I'm sure you can get it down to 1 line.
pdkl95 12y ago
https://gist.github.com/pdkl95/e97749edc3ba58825a16#file-bash_only_mergesort-bash 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)

31 points by wyc 12y ago

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/ http://www.win-vector.com/blog/2008/04/sorting-in-anger/

wyc 12y ago
Haha, there are few places where this submission would result in such a decent analysis. Thanks.

ozcanesen 12y ago

Reminds me http://bash.org/?464385 http://bash.org/?464385

im2w1l 12y ago
Well do be fair none of the commands in this quicksort require user input at least :)

kazinator 12y ago

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

zura 12y ago

Maybe we should all learn to always prepend "Pseudo" to these "quicksorts"?

sp332 12y ago
Is it not really a quicksort?
- cornewut 12y ago
  I guess he meant pseudo 3 lines.
- zura 12y ago
  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 12y ago
  It's a bad implementation of it, see jmount's comment.

bunfun 12y ago

Hey, check out this 1-liner HTTP server! :%s/\n/ /g

readerrrr 12y ago

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 12y ago

[deleted]

darkstar999 12y ago

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 12y ago
[deleted]
kazinator 12y ago
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 12y ago
  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 12y ago

It's not 3 commands so I'm sure you can get it down to 1 line.

pdkl95 12y ago

https://gist.github.com/pdkl95/e97749edc3ba58825a16#file-bash_only_mergesort-bash 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)