#!/usr/bin/env perl
use utf8;
###############################################################################
# This program demonstrates the Quicksort.
# 
# Copyright © 2021 Richard Lesh.  All rights reserved.
###############################################################################

use Utils;
use strict;
use warnings;

sub partition {
    my ($list, $low, $high) = @_;
    my $PIVOT = $list->[int(($high + $low) / 2)];
    my $i = $low - 1;
    my $j = $high + 1;
    while (1) {
        do {
            ++$i;
        } while ($list->[$i] < $PIVOT);
        do {
            --$j;
        } while ($list->[$j] > $PIVOT);
        if ($i >= $j) {
            return $j;
        }
        my $TEMP = $list->[$j];
        $list->[$j] = $list->[$i];
        $list->[$i] = $TEMP;
    }
}

sub quicksort0 {
    my ($list, $low, $high) = @_;
    if ($low < $high) {
        my $p = partition($list, $low, $high);
        quicksort0($list, $low, $p);
        quicksort0($list, $p + 1, $high);
    }
}

sub quicksort {
    my ($list) = @_;
    quicksort0($list, 0, scalar(@{$list}) - 1);
}

MAIN:
{
    if (scalar(@ARGV) != 2) {
        print "Syntax: ", "Quicksort", " list_size max_int\n";
        exit 1;
    }
    my $LIST_SIZE = Utils::stoiWithDefault($ARGV[0], 10);
    my $MAX_INT = Utils::stoiWithDefault($ARGV[1], 100);

    my $list_to_sort = [];
    print "Random List\n";
    for (my $i = 0; $i < $LIST_SIZE; ++$i) {
        push(@{$list_to_sort}, int(rand($MAX_INT)));
    }
    print Utils::listToString($list_to_sort), "\n";

    quicksort($list_to_sort);

    print "Sorted List\n";
    print Utils::listToString($list_to_sort), "\n";
}