# 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; my \$b = \$right;
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