Alister West

home is where your code is ...

Algorithms Sorting

These algorithms were written as reminders.

Quick Sort

Divide into (less, pivot, more) then recurse.

sub quick_sort {

    my @unsorted = @_;

    return @unsorted if @unsorted <= 1;

    my $pivot_index = int $#unsorted/2;
    my $pivot = $unsorted[$pivot_index];

    my (@left,@right);

    for my $i (0..$#unsorted) {
        next if $i == $pivot_index;
        if ($unsorted[$i] <= $pivot) {
            push @left, $unsorted[$i];
        } else {
            push @right, $unsorted[$i];
        }
    }
    say "@left | $pivot | @right";
    return (quick_sort(@left), $pivot, quick_sort(@right));
}

Merge Sort

Split-up into smallest unit then merge (left, right) with sort when combining the arrays.

sub merge_sort {
    my @unsorted = @_;
    my $size = @unsorted;

    return @unsorted if @unsorted <= 1;

    # divide ..
    my @left  = splice @unsorted, 0, $size/2;
    my @right = @unsorted;

    # say "@left || @right";

    @left = merge_sort(@left);
    @right = merge_sort(@right);

    # .. and conqure with merge!
    my @sorted;
    while (@left || @right) {
        my $a = $left[0]; my $b = $right[0];
        if (!$b) { push @sorted, @left; last; }
        if (!$a) { push @sorted, @right; last; }
        if ($a <= $b) { push @sorted, shift(@left); next; }
        if ($b < $a)  { push @sorted, shift(@right); next; }
    }

    return @sorted;
}

Insertion Sort

Inplace naive sort. Process left-to-right moving the working value into the previously sorted part of the list.

sub insertion_sort {

    my @unsorted = @_;
    $DEBUG and say "insertion_sort(@unsorted)";

    # for every element in turn
    for my $i (0 .. $#unsorted) {
        say "@unsorted";
        say "---" x ($i) . "^";

        # go back over each elem we've past,
        for (my $j = $i-1; $j >= 0; $j--) {

            # STOP:  $i gt all previous array elems.
            last if $unsorted[$i] >= $unsorted[$j];

            # SWAP: if $j > $i
            if ($unsorted[$j] > $unsorted[$i]) {
                # say "swapping to be: $unsorted[$i] with $unsorted[$j]";
                my $a = $unsorted[$i];
                $unsorted[$i] = $unsorted[$j];
                $unsorted[$j] = $a;
                $i = $j; # update index pointer
            }
        }
    }

    # Unsorted is now Sorted!
    return @unsorted;
}

Testing Sorts

A starting wrapper for the above sorts.

#!/usr/bin/env perl
use strict;
use warnings;
use feature qw/say/;

local $" = ', ';
my $DEBUG = 0;

my @unsorted = ( 9,3,1,4,6,2,-2,4, 12 );
say "unsorted: @unsorted";
say "---------------------";
my @sorted_quick  = quick_sort( @unsorted );
my @sorted_merge  = merge_sort( @unsorted );
my @sorted_insert = insertion_sort( @unsorted );
say "@sorted_quick\n@sorted_merge\n@sorted_insert";

# include sort code here ...
By Alister West