Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Quicksort in 3 lines of shell

github.com

Post reply on HN
Print view View original

11–20 of 20 posts

Re: Quicksort in 3 lines of shell

#13

Post by 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/

Re: Quicksort in 3 lines of shell

#14

Post by zura »

sp332 wrote: post #10
zura wrote: post #4

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

Is it not really a quicksort?

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.

Re: Quicksort in 3 lines of shell

#16

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

Re: Quicksort in 3 lines of shell

#17

Post by [deleted] »

darkstar999 wrote: post #8

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]

Re: Quicksort in 3 lines of shell

#18

Post by kazinator »

darkstar999 wrote: post #8

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.

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

Re: Quicksort in 3 lines of shell

#19

Post by kazinator »

kazinator wrote: post #18
darkstar999 wrote: post #8

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.

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…

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.

Re: Quicksort in 3 lines of shell

#20

Post by wyc »

jmount wrote: post #13

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 assem…

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