#!/usr/local/bin/perl
# quick n dirty quicksort implementation
use strict;
use warnings;
use Data::Dumper;

# input data (nested data structure: array of hashes)
our (@Vec);
push @Vec, {'Simpson' => 'Lisa'};
push @Vec, {'Flanders' => 'Ned'};
push @Vec, {'Flanders' => 'Maude'};
push @Vec, {'Simpson' => 'Bart'};
push @Vec, {'Wiggum' => 'Chief'};
push @Vec, {'Simpson' => 'Marge'};
push @Vec, {'Wiggum' => 'Ralph'};
push @Vec, {'Springfield' => 'Jebediah'};
push @Vec, {'Simpson' => 'Homer'};

print "before sorting:\n"; print Dumper @Vec;

quick(0, @Vec-1); #calling quicksort

sub quick {
  my ( $l, $r ) = @_;

  #my $pivot = (keys %{$Vec[ int( ($l+$r)/2 ) ]})[0];
  my $pivot = ( keys %{ $Vec[$r] } )[0];    # last element
  my ( $i, $j ) = ( $l, $r );

  print "[$i\,$j], pivot=$pivot (" . $Vec[$r]->{$pivot} . ")\n";

  do {
    while ( ( keys %{ $Vec[$i] } )[0] lt $pivot ) { $i++ }
    while ( ( keys %{ $Vec[$j] } )[0] gt $pivot ) { $j-- }

    if ( $i <= $j ) {
      # exchange i and j
      my %t = %{ $Vec[$i] };
      %{ $Vec[$i] } = %{ $Vec[$j] };
      %{ $Vec[$j] } = %t;

      $i++;
      $j--;
    }
  } while ( $i <= $j );

  #recursion
  if ( $l < $j ) { quick( $l, $j ) }
  if ( $i < $r ) { quick( $i, $r ) }
}
print "after sorting:\n"; print Dumper @Vec;

















