Quicksort in 3 lines of shell(github.com)

31 pointsby wyc12 anni fa17 comments

https://github.com/wyc/snippets/blob/master/sh/qsort/qsort.sh

10 comments

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.

kazinator12 anni fa

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

kazinator12 anni fa

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.

[deleted]12 anni fa

ozcanesen12 anni fa

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

im2w1l12 anni fa

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

kazinator12 anni fa

> L=`qsort $L`

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

jmount12 anni fa

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/

wyc12 anni fa

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

readerrrr12 anni fa

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

}

zura12 anni fa

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

sp33212 anni fa

Is it not really a quicksort?

zura12 anni fa

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.

p4bl012 anni fa

It's a bad implementation of it, see jmount's comment.

cornewut12 anni fa

I guess he meant pseudo 3 lines.

pdkl9512 anni fa

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)

mesozoic12 anni fa

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

bunfun12 anni fa

Hey, check out this 1-liner HTTP server!

:%s/\n/ /g

[deleted]12 anni fa