Reply to thread

Message: [QUOTE="anno4000, post: 4823429"] [snipped, revised version below] It is also the part that has a serious design flaw. Two, really. It takes an arbitrary number for the pivot, but quicksort only works when the pivot is a known element of the unsorted array. Also, the code in qs_recurs() relies on the fact that the pivot element won't change its position at the beginning of the array during partitioning. That's difficult to grant in general and also nails the choice of the pivot to being the first element. Here is a revised version. The pivot *index* can now be chosen arbitrarily in the call to partition(), at the cost of an additional exchange. All moving-about of elements happens in partition(), qs_recurs() only organizes the calls by choosing the pivot index and the sub-array limits. sub qs { my @a = @_; qs_recurs( \ @a, 0, $#_); @a; } sub qs_recurs { my ( $a, $from, $to) = @_; return unless $from < $to; my $i_pivot = ($from + $to)/2; # anything between $from and $to my $mid = partition( $a, $from, $i_pivot, $to); qs_recurs( $a, $from, $mid - 1); qs_recurs( $a, $mid + 1, $to); } sub partition { my ( $a, $from, $i_pivot, $to) = @_; # put pivot in first position (it will remain there) @$a[ $from, $i_pivot] = @$a[ $i_pivot, $from]; $i_pivot = $from; # save for later my $pivot = $a->[ $i_pivot]; while ( $from <= $to ) { if ( $a->[ $from] > $pivot ) { @$a[ $from, $to] = @$a[ $to, $from]; -- $to; } else { ++ $from; } } # move pivot element in the middle @$a[ $i_pivot, $to] = @$a[ $to, $i_pivot]; return $to; } As mentioned, this isn't particularly optimized, and the change doesn't make it faster. Obvious micro-optimizations are -- avoid unnecessary recursive calls: qs_recurs( $a, $from, $mid - 1) if $from < $mid - 1; # etc -- avoid unnecessary exchange operations @$a[ $from, $to] = @$a[ $to, $from] if $from != $to; # etc __ inline partition() into qs_recurs() None of these will make a dramatic difference, and each should be tried and benchmarked individually. The second one in particular could be counter-productive. Anno [/QUOTE]

Verification