Quicksort in 3 lines of shell(github.com)
github.com
Quicksort in 3 lines of shell
https://github.com/wyc/snippets/blob/master/sh/qsort/qsort.sh
10 comments
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
Also, suppose we abstract the operators a little bit:
Change it to "-ot" and we can order paths by modification timestamp.
Set LT to "<" and obtain lexicographic sorting on strings.
if [ $x $LT $y ] ; ...
Change it to "-ot" and we can order paths by modification timestamp.
Set LT to "<" and obtain lexicographic sorting on strings.
[deleted]
Reminds me http://bash.org/?464385
Well do be fair none of the commands in this quicksort require user input at least :)
> L=`qsort $L`
POSIX has standardized $(qsort $L) syntax since 1990. It's okay to use it now.
POSIX has standardized $(qsort $L) syntax since 1990. It's okay to use it now.
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/
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/
Haha, there are few places where this submission would result in such a decent analysis. Thanks.
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 ); }
}
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 ); }
}
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.
It's a bad implementation of it, see jmount's comment.
I guess he meant pseudo 3 lines.
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)
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)
It's not 3 commands so I'm sure you can get it down to 1 line.
Hey, check out this 1-liner HTTP server!
:%s/\n/ /g
:%s/\n/ /g
[deleted]
Looks more like 14 lines to me.